среда, 22 июня 2011 г.

Lambda: the Gathering - поиграть штангой в карты

На прошедшем ICFPC авторы предложили мозговыносящую задачу, впрочем, как и в прошлые годы. Хотя, в этом году неплохое преимущество было у штангистов.

По формату этот ICFPC напоминал Google AI Challenge (вероятно, оттуда они и потырили часть идеи).

Описание задачи.

Предлагается написать бота, который будет сражаться с другими ботами турнирным методом. Боты играют попарно и ходят по-очереди. У каждого игрока имеется 256 слотов и фиксированный набор карт. Каждый слот имеет поле и очки жизней (хит-поинты). Поле слота может содержать либо целое число от 0 до 65535, либо функцию. Хит-поинты слота могут иметь значение от -1 до 65535. Слот считается живым, если его хит-поинты больше нуля. В начале матча каждый слот инициализируется тождественной функцией и 10 000 хит-поинтами.

На каждом ходу игрок может выполнить одно из двух действий: 'левое' либо 'правое'. Левое действие применяет заданную карту (функцию) к полю заданного слота. Правое применяет поле слота (содержащее функцию) к карте. Действие завершается ошибкой, если применяемая карта или поле не являются функцей, или заданный слот мертв.

Ход завершается, если происходит ошибка, если количество применений функций в результате левых или правых действий (включая их самих) превысит 1000 (фактически, это ограничение глубины стека виртуальной машины), или если применение завершается корректно без превышения этого лимита. В последнем случае полю слота присваивается полученное значение, а во всех других случаях оно перезаписывается в тождественную функцию. Все побочные эффекты, произведенные применениями функций, не откатываются, даже если применение завершилось аварийно.


Каждому игроку отводится на матч не более 100 000 ходов. Игра может завершиться раньше, если все слоты игрока мертвы. В любом случае, победа присуждается тому игроку, у кого осталось больше живых слотов. Если слотов осталось поровну, засчитывается ничья.

Карты

Дан следующий набор карт.
  • Карта “I” - тождественная функция.
  • Карта “zero” - целое число 0 (не функция).
  • Карта “succ” - функция, принимающая аргумент n и возвращающая n+1, если n<65535 (или 65535, если n=65535). Возвращает ошибку, если n - не целое число.
  • Карта “dbl” - функция, принимающая аргумент n и возвращающая n*2, если n<32768 (или 65535, если n>=32768). Возвращает ошибку, если n - не целое число.
  • Карта “get” - функция, принимающая аргумент i и возвращающая значение поля i-го слота игрока-зашитника, если этот слот жив. Возвращает ошибку, если i - некорректный номер слота, или слот мертв.
  • Карта “put” - функция, принимающая (неиспользуемый) аргумент и возвращающая функцию #'identity.
  • Карта "S" - S-комбинатор λf.λg.λx.fx(gx).
  • Карта "K" - K-комбинатор λx.λy.x.
  • Карта "inc" - увеличивает на 1 хит-поинты слота защитника, если слот жив и количество хит-поинтов не привысит допустимого лимита.
  • Карта "dec" - увеличивает на 1 хит-поинты слота противника, если слот жив.
  • Карта "attack" - функция, принимеющая аргумент i и возвращающая другую функцию, которая (будучи применена) примет другой аргумент j и возвратит еще одну функцию, которая (будучи применена) примет аргумент n и уменьшит на n*9/10 хитпоинты (255-i)-го слота противника, при этом уменьшит также и хитпоинты атакующего j-го слота на n, после чего возвратит тождественную функцию.
  •  Карта "help" - действует похожим образом, но, вместо уменьшения жизней слота противника на n*9/10, увеличивает количество жизней слота защитника на n*11/10.
  • Карта "copy" - функция от i, которая возвращает функцию от j, которая копирует содержимое (255-i)-го слота притивника в поле j-го слота защитника.
  • Карта "revive" - функция, которая оживляет слот зашитника, давая ему 1 хит-поинт.
  • Карта "zombie" - функция от i, которая возвращает функцию от x, которая запишет x в (255-i)-й слот противника, если этот слот мертв, устанавливает его хит-поинты в -1 и возвращает тождественную функцию.
Непосредственно перед началом каждого хода игрока функция в поле каждого слота с хит-поинтами -1 автоматически применяется к тождественной функции начиная с первого мертвого слота до конца по возрастающей. При каждом из таких автоматических применений происходит ошибка. если поле содержит не функцию, или количество применений функции привысило 1000. Если возникает ошибка, то слот перезаписывается тождественной функцией, а хитпоинты слота устанавливаются в 0.

Кроме того, во время такого автоматического применения эффекты четырех карт изменяются:
  • Эффекты карт “inc” и "dec" меняются между собой.
  • Третья функция в карте “attack” увеличивает, а не уменьшает хит-поинты атакуемого слота.
  • Третья функция в карте “help” уменьшает, а не уменьшает хит-поинты подлечиваемого слота.
Такое автоматическое применение позволяет делать нетривиальные вещи с помощью зомбей.

Виртуальная машина

Первое, что необходимо было сделать - написать виртуальную машину, которая симулировала бы состояние обоих игроков. Матчи велись отдельной спарринг-программой, которая принимала от ботов через stdin три значения. Так, "1 dbl 10" соответствует левому применению карты dbl к десятому слоту, а "2 zero 0" - правому применению слота 0 к карте zero. Это означает, что простейший бот мог просто посылать одну и ту же команду на каждом ходу, но для сколько-ниудь осмысленных действий необходимо было знать текущее состояние слотов.

На написание первого приближения виртуальной машины у нас ушел весь первый день. К сожалению, мы долго тупили, проникаясь укуренностью остальной части задачи. Целый день на симулятор - это оказалось слишком много.

Собственно, штанга

В середине первого дня в команду пришел еще один участник, который что-то соображал в комбинаторной логике. И это было очень здорово, потому как, чтобы натравить одного зомби, пришлось бы строить такую функцию: S(K(S(K(zombie(zero)(1)))(get)))(succ)(zero), а это уже целое заклинание некромантии.

К концу второго дня стало ясно в общих чертах, как нужно сочетать карты с помощью SKI-комбинаторов, чтобы получать тот или иной эффект. К восьми часам утра я таки запостил на тестовый сервер примитивного бота, который атаковал всех по-очереди, пока не заканчивались хит-поинты, после чего я пошел спать.

Как ни странно, даже такой тупой бот выиграл бот 16 из 23 матчей, но еще в трех матчах он нарушил спецификацию и был дисквалифицирован. Это означало, что где-то в симуляторе были ошибки. Перспектива шерстить весь код на наличие несоответствий была безрадостной, но куда деваться.


Третий день стало понятно, что хорошие места в турнирной таблице нам не светят, потому как в конфе icfpc@cjr пробегали понты типа "я размочил все слоты за 500 ходов", а мы тогда знали, как убить все слоты за отведенные 100 000 ходов. К концу соревнования довольно результативно полистали код симулятора на предмет ошибок и оформили минимально вменяемую стратегию бота, после чего засабмитили на официальный и тестовый серверы и пошли спать. Всех ошибок в симуляторе мы обнаружить не смогли, но до дисквалификации на тестовом сервере он смог выиграть 12 из 42 матчей (к тому времени соперники стали умнее).


Итоговый бот


Виртуальная машина интерпретировала операции в последовательности инструкций, которые одна за другой передавались спарринг-программе. Одна операция могла преобразовываться в много или очень много инструкций. Серьезную проблему представляло получение больших чисел, т.к. для этой цели были доступны только карты zero, succ и dbl. Так, для записи числа 8 в слот 3 генерировалась следующая очередь:

1  put  3    ;; #'identity
2  0    zero ;; 0
1  succ 3    ;; 1
1  dbl  3    ;; 2
1  dbl  3    ;; 4
1  dbl  3    ;; 8


Доступ к слотам противника осуществлялся в обратном порядке, и, чтобы атаковать его нулевой слот, нужно было хранить в одном из слотов число 255. Первые слоты самые ценные, но и убить их наиболее трудно, потому что номер слота приходится "набирать" последовательным применением succ и dbl в определенном порядке, а это лишние ходы. Поэтому было выделено слотов-хранилищ, которые были своего рода кешем, позволяющим использовать имеющиеся числа повторно. Три слота-хранилища были расположены вначале, т.к. к ним наиболее быстрый доступ, а противнику их сложнее всего убить. Тем не менее, в начале каждого хода проверялось, живы ли эти слоты, и если они какой-либо из них был мертв, текущая очередь команд прерывалась, создавалась новая очередь, применяющся карту revive, а по ее завершению начиналось оживление нового слота, либо возвращалась прерванная очередь. За одну нашу атаку бот снимал с противника 3686 хит-поинтов, но при этом сам терял 4096 хит-поинтов. Если слот противника умирал, то значение слота-хранилица увеличивалось на 1, и атаковался следующий слот. Когда наши хит-поинты подходили к концу, генерировалась очередь, за один ход многократно применяющая карту inc. Полноценную рекурсию сделать не получилось, но многократное удвоенное действие позволило за один ход наращивать 1000 хит-поинтов (больше нельзя, но это тоже неплохо). Когда силы бота восстанавливались, то он снова переходил к атаке.


Вообще говоря, суть конкурса ICFPC в том, что авторы в игровой форме ставят сложные задачи так, чтобы знание предметной области было не обязательным (хотя и желательным). Короче говоря, мы слили, хотя и не так позорно, как в прошлом году. Не помог нам даже великий и славный common lisp (хотя и очень облегчил задачу, потому как жаберы и сиплюсплюсники страшно матерились, и это понятно). В целом, очень интересная задача, заставляет шевелить даже затекшие мозги. Код финального сабмишна, если вдруг кому интересно, лежит по адресу http://lisper.ru/files/icfpc/skobochka.tar.gz


Спасибо всем участникам (turtle, gltronred, laser123, dmitry_vk).


ЗЫ. По завершении конкурса авторы написали, что картинки (на сайте кроме карт были еще две картинки) не так просты, как кажется. Первую картинку можно полуить из второй, а вторую из первой:

java -jar new_books.png > lambda.png
java -jar lambda.png > new_books.png

Вот уж действительно боевые человекоподобные японцы :)

Перевод книги ANSI Common Lisp, #2

К сожалению, выпуск перевода затягивается издательством на неопределенный срок из-за серьезных финансовых проблем. Короче говоря, они на грани банкротства.

Если их трудности утрясутся, то ожидать выпуска книги можно в середине осени. Если им таки настанет крышка, то доработаем и издадим сами, вопрос с правообладанием как-нибудь разрешим.

понедельник, 14 февраля 2011 г.

Перевод книги ANSI Common Lisp

Сабж завершен. До верстки над ним поработают редакторы, до выхода в печать еще ориентировочно два-три месяца.

Такие дела.

upd.

Всего 17 глав.
Если кто-то желает взять одну или несколько глав на детальную вычитку (важна техническая сторона вопроса, грамматику и т.д. будет править редактор), отписывайте номер главы в коментах.

Ожидают своей участи главы:

4, 5, 6, 7, 8, 9, 12, 14, 15, 16, 17

ЗЫ.
Высылаю pdfку на почту, не выкладываю в сети по понятным соображениям. Очень надеюсь, что она не окажется в сети (уже хотя бы потому, что на настоящий момент она наверняка содержит баги, а чтение бажных книжек может быть вредно)

ЗЗЫ.
Для тех, кто интересовался стоимостью печатного издания будущей книги, получил ответ: "Сколько будет стоить книга я не в курсе. Этот вопрос вкомпетенции высшего руководства."

четверг, 2 декабря 2010 г.

Замечания по отладке в SBCL и Slime

Оригнальный текст: https://gist.github.com/659495#file_sbcl_debugging_notes.txt, Nikodemus Siivola

0 Умение сокращать размеры тестового набора - это важный навык, не зависящий от языка или инструментария. Это целое искусство - сокращать до премлемых размеров количество примеров, приводящих к появлению ошибок, неверных результатов (например, моменты, связанные с указанием полного пути или текущей директории, выполнением кода в Slime или вне него). С одной стороны, чем меньше тестовых примеров, тем лучше, но здесь надо соблюдать осторожность. Если вы в состоянии распознать баг за пару минут каким-либо другим методом, очевидно, глупо тратить несколько часов на сжатие тестового набора. Однако, если другими методами вы не в состоянии этого сделать, придется смириться с временными затратами.

1 Осторожное программирование. Речь не только о том, как избегать ошибок в коде, но и о том, как делать его легкоотлаживаемым. Избегайте IGNORE-ERRORS, не позволяйте компилятору безмолвно проглатывать ошибки. Иногда это может быть полезным, но чем больше таких мест в коде, тем сложнее использовать *BREAK-ON-SIGNALS*. Избегайте SAFETY 0 как чумы - он скроет множество огрехов. Не используйте DEBUG 0 - от этого вы не получите выгоды. Определяйте PRINT-OBJECT методы для собственных объектов, давайте им имена. Никогда не употребляйте INTERRUPT-THREAD или WITH-TIMEOUT, пока вы не будете точно уверены в том, что делаете, и пока не поймете, почему их лучше не использовать.

2 Не задумывайтесь там, где не следует. Просто внимательно вчитывайтесь в сообщения об ошибках. Иногда они бесполезны, но иногда вы рискуете упустить много полезной информации.

3 Изучайте возможности инструментария. Здесь стоит остановиться подробнее.

   3.0 M-. - это отличная вещь. Нажимая 'v' в отладочном окне Slime, вы также попадаете в участки кода, предоставляющего достаточно много информации для отладки, но M-. можно использовать везде.

   3.1 Slime Inspector - один из главных отладочных инструментов. Пригодится он вам или нет - зависит от задачи, но будет полезно познакомьться с его возможностями, они того стоят.

   3.2 Обратная трассировка (backtrace) в SBCL на настоящий момент реализована не лучшим образом, но ее использование может принести определенные плоды. Просто загляните (вызовите любую ошибку) в REPL и выясните, что происходит. Поразвлекайтесь с штатным отладчиком SBCL и модным Slime Debugger, прежде чем будете пользоваться ими на практике, и тогда они перестанут казаться вам враждебными. О том, как пользоваться обратной трассировкой, я напишу в другой раз.

   3.3 Разберитесь с *BREAK-ON-SIGNALS* и TRACE. Не забывайте, что SBCL предоставляет некоторые расширения возможностей TRACE.

   3.4 Пошаговое выполнение по сути не является отладочным инструментом. Я считаю, что это всего лишь средство наблюдения за ходом исполнения. Иногда это может быть полезным в отладке, но только при компиляции кода с DEBUG 3, когда (STEP (FOO)) доставит вас в нужное место.

   3.5 Пользуйтесь M-RET (macroexpand) в Slime. Попробуйте (SETF *PRINT-GENSYM* NIL) и посмотрите, что будет происходить. Это несет с собой потенциальные опасности, но зато может позволить легко копировать и вставлять код, в который раскрывается ваш тестовый пример. (Замена раскрытий макросов в пакете COMMON-LISP, как правило, нецелесообразна, но в пользовательских пакетах может быть очень полезным.)

   3.6 Если ничего не помогло, попробуйте (sb-ext:restrict-compiler-policy 'safety 3) и (sb-ext:restrict-compiler-policy 'debug 3), после чего перекомпилируйте весь код. Теперь отладка станет легче. Если ошибка исчезла,  либо (а) вы ошиблись с типами (или допустили похожую ошибку) в коде, собранном с SAFETY 0, и она не терялась благодаря IGNORE-ERRORS или HANDLER-CASE, либо (б) вы обнаружили баг в SBCL: вообще говоря, политика компилятора не должна изменять поведение кода, за исключением нескольких допускаемых ANSI случаев при использовании SAFETY 3, или же когда высокий уровень отладки препятствует оптимизации хвостовой рекурсии. Знающие Scheme объяснят вам, что это может иметь значение.

   3.7 DISASSEMBLE не есть штатное средство отладки, но иногда может быть полезным. Это зависит от сути имеющейся проблемы.

4 Расширения отладочной печати. Часто это простейшее средство, которым можно воспользоваться. Не стыдитесь этого.

   4.1 Пользуйтесь специальными переменными:

  (LET ((*DEBUG* :MAGIC)) ...) и, где-либо в коде,

  (WHEN (EQ :MAGIC *DEBUG*) (PRINT (LIST :FOO FOO)))

Будучи ленивым, я обычно использую глобальные переменные для управления отладочной печатью, как в примере выше. Это позволяет использовать ее только при необходимости, определять, на каком участве кода происходит вызов и т.д.

   4.2 Не бойтесь вставлять в отлаживаемый код (break "foo=~S" foo) или подобные вызовы.

   4.3 SB-DEBUG:BACKTRACE все же можно использовать.

пятница, 19 ноября 2010 г.

Решение задачи о двух спиралях с помощью пакета ANNIL

Задача о двух спиралях известна как трудная, с высокой степенью нелинейности, задача для тестирования алгоритмов классификации.


Две спирали, "одна в другой", симметричные относительно центра и поворота на 180 градусов.


Обучающее множество генерируется так ("annil/tests/two-spirals.lisp")

(defun 2spiral-radius (i) (/ (* 6.5 (- 104 i)) 104))
(defun 2spiral-angle (i) (* i (/ (coerce pi 'single-float) 16)))


(defun genpat-2spirals (&optional (output-ranges '(-1.0 1.0)))
  
(let ((patterns nil))
    
(dotimes (i 97)
      
(let ((r (2spiral-radius i))
        
(a (2spiral-angle i))
)

    
(let ((x (* r (sin a)))
          
(y (* r (cos a)))
)

      
(push (list (make-matrix 2 :initial-contents `(,x ,y))
                  
(make-matrix 1 :initial-element (first output-ranges))
)

        patterns
)

      
(push (list (make-matrix 2 :initial-contents `(,(- x) ,(- y)))
                  
(make-matrix 1 :initial-element (second output-ranges))
)

        patterns
)
)
)
)

    
(nreverse patterns)
)
)

Теперь создадим классификатор, обученный разделять эти спирали.

(defparameter *classifier*
  
(make-cascor-classifier *patterns* nil 'tanh-fn 0.8 20
   `
((:iter . 100) (:verbosity . 2) (:cc-iter . 100) (:cc-candidates . 5))
)
)

Процедура обучения сети состоит из последовательного добавления нового узла (и настройки его входных весов) и настройки выходных весов


Аргументы обучающей процедуры:


*patterns* - обучающий набор (пары вход -- желаемый выход)
nil - тестовый набор для проведения перекрестной проверки (cross-validation, метод предупреждения переобучения сети)
'tanh-fn - функция активации узлов.
0.8 - порог уверенной классификации. (выход в промежутке [-1.0;-0.2] - отрицательная классификация, [0.2;1.0] - положительная, [-0.2;0.2] - неуверенная, рассматривается как неверная)
20 - количество добавляемых скрытых узлов.


Ассоциативный список содержит параметры самого алгоритма (довольно удобный способ хранения и передачи аргументов, не надо париться с порядком последовательности). В примере приведены обязательные аргументы (количество итераций настройки выходов (:iter), входов (:cc-iter), кандидатов на добавление в сеть (:cc-candidates, выбирается лучший из заданного количества узлов, обученных обученных).
Параметр verbosity не обязательный, по умолчанию 0. Определяет "многословность", количество выдаваемой информации (0 - ничего не говорит, 4 - выдает максимум информации)


Также алгоритму могут быть сообщены дополнительные параметры, влияющие на скорость сходимости, которые имеют по-умолчанию хорошие значения для случайной задачи, но могут быть настроены, а также параметры преждевременной остановки в случае длительного отсутствия или слишком слабого улучшения, а также некоторые другие полезные параметры. О них надо будет написать документацию.


Дополнительная опция test-fn (последний аргумент) позволяет выводить состояние системы после обучения каждого нового узла, например, рисовать картинки с помощью gnuplot.


Вернемся к процессу обучения. С параметром verbosity=2 вывод процедуры выглядит следующим образом:

(defparameter *classifier*
  
(make-cascor-classifier *patterns* nil 'tanh-fn 0.8 20
    `
((:iter . 100) (:verbosity . 2) (:cc-iter . 100) (:cc-candidates . 5))
    #'
(lambda (net iter)
        
(visual-classify-2spirals net *pat* 0.8
          
(format nil "'/tmp/test-known~A.png'" iter)
)

        
(visual-test-2d net 10000 6.5 '(-1.0 1.0) 0.8
          
(format nil "'/tmp/test-unknown~A.png'" iter)
)
)
)
)

Сделать нормальный cut с первой попытки не получилось, на то он и blogger, поэтому привожу только начало и конец вывода.

В начале ...


 ;; Final error: 0.9869251
 ;;
 ;; Training 0 node
 ;; Training candidates: .....
 ;; Best corr: 27.80652
 ;; Connecting to outputs
 ;; Final error: 0.97089535
 ;; Epochs passed: 200
 ;;
 ;; Training 1 node
 ;; Training candidates: .....
 ;; Best corr: 24.884932
 ;; Connecting to outputs
 ;; Final error: 0.95397794
 ;; Epochs passed: 300
 ;;
 ;; Training 2 node
 ;; Training candidates: .....
 ;; Best corr: 17.344604
 ;; Connecting to outputs
 ;; Final error: 0.94608283
 ;; Epochs passed: 400

И в конце ... 


 ;; Training 17 node
 ;; Training candidates: .....
 ;; Best corr: 16.05864
 ;; Connecting to outputs
 ;; Final error: 0.062364805
 ;; Epochs passed: 1900
 ;;
 ;; Training 18 node
 ;; Training candidates: .....
 ;; Best corr: 10.090686
 ;; Connecting to outputs
 ;; Final error: 0.052389637
 ;; Epochs passed: 2000
 ;;
 ;; Training 19 node
 ;; Training candidates: .....
 ;; Best corr: 8.781674
 ;; Connecting to outputs
 ;; Final error: 0.043491814
 ;; Epochs passed: 2100



После обучения каждого нового узла рисуются две картинки - результат работы сети на обучающем наборе (проверка качества запоминания) и на наборе случайных точек, которые он должен отнести к одной или другой спирали (проверка качества обобщения).


По полученным изображениям можно проследить изменение запоминающей и обобщающей способностей в процессе обучения.


Картинки лежат на гитхубе. Приведу две соответствующие картинки после окончания обучения.




На последней картинке видны спиральные области красного и зеленого цветов, точки в которых сеть отнесла к одной или другой спирали, а также синие точки, которые сеть затруднилась отнести к конкретному классу.




Неплохо, однако. У Фальмана аналогичные картинки (в статье) более ломаные и меньше похожи на спираль.


Надо сказать, что после добавления 20 узлов среднекваратическая ошибка все еще довольно высока (0.04). Настройкой параметров алгоритма можно значительно ее уменьшить (мне удавалось получить меньше 0.001) и уменьшить время обучения.

среда, 17 ноября 2010 г.

Нейросетевое решение задачи классификации

Наконец-то удалось сделать нормальный классификатор для пакета нейросетевого анализа. (http://github.com/allchemist/annil).

Сеть каскадной корреляции, обучаемая с помощью алгоритма quickprop. Насколько я понимаю, эта связка является наиболее эффективным на настоящий момент алгоритмом такого назначения.

Затратил на реализацию этой связки достаточно много усилий, т.к. архитектура довольно редкая, литературы по ней мало.

Алгоритм quickprop решает задачу нелинейной регрессии с квадратичной сходимостью за время, линейно зависящее от количества весов сети, чем выгодно отличается от обратного распространения (линейная сходимость, линейное время) и от многомерной квазиньютоновской оптимизации (квадратичная сходимость, квадратичное время).

Алгоритм каскадной корреляции настраивает архитектуру сети самостоятельно, добавляя по одному узлу, который обучается извлекать следующий наиболее важный признак (процедура исчерпания, аналогичная ортогонализации Грама-Шмидта).

В результате, архитектура обладает отличной способностью к решению задач классификации, не обладая при этом многими неприятными особенностями обратного распространения.

Как quickprop, так и каскадная корреляция, разработаны Скотом Фальманом, одним из разработчиков CMU CL, также известным как изобретатель смайликов. :)
Авторские статьи по этим алгоритмам лежат тут: http://www-2.cs.cmu.edu/~sef/sefPubs.htm

Реализация тестировалась на нескольких задачах, которые считаются довольно сложными (two spirals, ocr, некоторые задачи проекта elena). Сеть успешно справилась с задачами и показала даже большую эффективность, чем авторская реализация.

В ближайшее время подготовлю примеры использования с красявыми картинками :)

воскресенье, 12 сентября 2010 г.

Математика в SBCL: бенчмарк

После проведения некоторых оптимизаций кода sb-math решил провести тест производительности функций умножения матрицы на матрицу и матрицы на вектор. Для сравнения взял GSLL и простым сишным кодом. Таким образом, сравнивался чистый вызов функций cblas_sgemv и cblas_sgemm из библиотеки GSL CBLAS и два интерфейса к ним.

Код бенчмарков тут:
* bench.lisp - код для gsll и sb-math, а также вызова скомпилированного сишного кода, обработки результатов и отрисовки графиков.
* gemm_bench.c, gemv_bench.c - сам сишный код
* там же графики зависимостей (png)

Итак, умножение матрицы на вектор. Для упрощения умножалась квадратная матрица NxN на вектор длиной N.





На графике показана зависимость времени единичного вычисления от размености N. на больших размерностях GSLL дает существенное отставание. Причина этого неожиданного факта не совсем понятна. Более того, полгода назад на похожем тесте для больших размерностей GSLL шла рядом с сишным кодом, а вот для малых давала из рук вон плохие результаты. Вероятно, это связано с тем, что автор GSLL (Liam Healy) недавно перекроил все матричное api для нее.

Интересно посмотреть, что там вблизи нуля, где все линии сливаются в одну.






Тут не очень интересно, поэтому чуть увеличим размерность:







Так все более-менее ясно.

Теперь умножение матрицы на матрицу. Простоты ради все матрицы квадратные, с одинаковой размерностью.






Начиная с N=200 GSLL резко уходит уходит в отрыв, sb-math продолжает преследовать gcc :)

Напоследок посмотрим поближе на результаты для малых размерностей:


Подводя итог, можно сказать, что sb-math смотрится достаточно неплохо даже на  фоне gcc, хотя на матрицах малых размерностей относительное отставание от сишного кода велико. Но там еще есть возможности для оптимизации, и это вселяет надежду :)

GSLL ведет себя достаточно странно, причем это поведение стабильно воспроизводится. Тем не менее, с новым foreign array api там все стало существенно лучше.

Ну а сишный код - что с него взять? Накладных расходов на подготовку параметров там нет, но нет и гибкости и удобства, которые дает lisp.

Ну и это самое. В отличие от GSLL sb-math не привязана к какой-то одной библиотеке CBLAS. Подключение ее к функциям из ATLAS дает существенный рост производительности по сравнению с GSLL. Тем не менее, я не стал включать в бенчмарк тесты на атласе, потому что целью было посмотреть оверхед на вызов функций. Да и не совсем честно это, что sb-math будет обгонять сишный код.

Ну вы поняли :)

UPD: В связи с глобальной переписью кода этот бенчмарк стал неактуальным. Оверхед на малых размерностях стал еще меньше.