воскресенье, 23 мая 2010 г.

Aivika версии 2.0

В ходе разработки моей небольшой библиотеки моделирования Айвика на языке F# произошел ряд важных прорывных событий. Во-первых, я значительно ускорил модуль системной динамики. Обсчет модели по методу Рунге-Кутта стал в раз 5 быстрее. Потом я добавил агентное моделирование (АМ), как его понял после прочтения статьи Андрея Борщева (одного из создателей системы AnyLogic). Для этого я переписал очередь событий модуля дискретно-событийного моделирования (DES), который стал на порядки производительнее. В общем, теперь охватываются все три основные парадигмы имитационного моделирования (ИМ), и в целом я доволен скоростью имитации. Также создал каталог с примерами моделей, каждая из которых снабжена справочной информацией и ссылками. Теперь более подробно.

Модуль системной динамики (SD)

Мне удалось значительно ускорить этот модуль за счет отказа от функций нескольких аргументов. После компиляции такие функции вызываются в конечном итоге через метод InvokeFast, который вопреки своему названию совершенно не быстр. Там используется RTTI, что делает каждый такой вызов достаточно медленным. Если же функция имеет всего один аргумент, то тогда вызывается напрямую абстрактный метод Invoke, минуя RTTI. Вызов Invoke очень эффективен.

Поэтому я переписал внутренности модуля так, чтобы везде использовалась функция одного аргумента. Теперь монада Dynamics стала просто частным случаем монады Reader с небольшим исключением: некоторые функции создают жестко контролируемый побочный эффект. Мне кажется, это можно как-то записать и в хаскеле, но там придется программировать на Си, реализуя местами функциональность монады ST.

В итоге модуль системной динамики стал где-то в пять раз быстрее прежнего. Учитывая, что все в Айвике в конечном счете построено на монаде Dynamics, это имеет колоссальные последствия для всей библиотеки в целом.

Еще я лучше осознал смысл термина комбинатор. Оказывается, что все функции eDSL системной динамики являются у меня комбинаторами. Причем выглядят они почти так же как в специализированных системах Simtegra MapSys, ithink или Vensim. Но у меня функции, которые принимают одни функции и создают другие, обладая свойством замыкания.

Агентное моделирование (АМ)

Система AnyLogic использует карты состояний (statecharts) для описания агентов. Я придумал API, которое позволяет достаточно декларативно задавать агенты и их состояния так, как если бы мы использовали эти самые карты состояний. Получается кратко и наглядно. Все действия задаются в монаде Dynamics. Широко используются такие возможности F# как взаимно-рекурсивные определения через let rec и объектные выражения (object expressions). Благодаря монаде Dynamics агенты легко интегрируются с модулем системной динамики.

Дискретно-событийное моделирование (DES)

Агентное моделирование реализовано поверх очереди событий, которая является сердцем DES.

В предыдущей версии очередь была реализована как proof-of-concept, т.е. через двусторонний список… Тормоза стали особенно заметны после добавления АМ. Сначала я переписал очередь через иммутабельный хип, описанный в одной замечательной книге по хаскелю. Но функции добавления и удаления по-прежнему продолжали висеть в списке десяти самых тормозных функций, показываемых профайлером SharpDevelop. Тогда я переписал очередь через императивный бинарный хип, реализованный на основе массива. Функции работы c очередью ушли из списка. Агентное моделирование просто взлетело.

Примеры моделей

Я создал аналоги моделей, используемых в системах Simtegra MapSys (SD), Berkeley&Madonna (SD), AnyLogic (АМ) и SimPy (DES). Также реализовал пару моделей, описанных в книге Ильи Труба “Объектно-ориентированное моделирование на C++”.

Планы

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

Сейчас в документации достаточно полно освещен модуль системной динамики. Теперь нужно описать модули дискретно-событийного моделирования (DES) и агентного моделирования (АМ). Думаю, что можно заняться продвижением. Важно, что библиотеку можно использовать и из C#, но наиболее полно возможности доступны только через F#.

Комментариев нет:

Отправить комментарий