Всем привет!

У кого-нибудь из присутствующих есть опыт разработки масштабных дискретных симуляций (порядок 1-10 млн агентов)? Интересует вопрос, насколько для этого подходит Julia?
В данный момент работаю над задачей оптимального распределения райдшеринг-такси по городу, столкнулся с проблемой, что стандартные симуляторы типа MATSim дохнут на ~100к агентах и крайне плохо параллелятся (никак). Это на порядок ниже, чем допустимый для моей задачи минимум.
Мне придется написать свой симулятор, динамика среды достаточно простая, реализация же предвидится сложной в части синхронизации асинхронных расчетов каждого агента со средой и предотвращение коллизий.
Из ближайших задач попробовать SimJulia на простом gridworld с тривиальной динамикой и посмотреть, как оно вообще заводится и масштабируется. Если кто уже пробовал large multi-agent simulations на Julia - поделитесь опытом, наблюдениями или ссылками, плиз

Насколько я понимаю, самый более-менее функционально полный фреймворк это https://github.com/JuliaDynamics/Agents.jl

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

Я не думаю, что в данный момент он поддерживает паралелизм, но начиная с 1.3, насколько я понимаю паралельные программы писать стало немного проще чем раньше.

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

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

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

Просто на том же дискурсе часто обсуждали, что отсутствие дебагера для многих является барьером, поэтому ребята в vscode и juno активно работают над его добавлением.

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

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

Самая очевидная проблема: так как симуляция обычно вычисляется как x_{n+1} = f(x_n), то среда и агенты должны быть иммутабельными, то есть к концу вычисления нового шага у тебя в памяти будут две копии среды - от предыдущего шага и от нового. Если (условно) у тебя одно состояние занимает 10 Гб, то два состояния будут занимать 20 и меньше ты не сделаешь никак. Можно конечно пытаться как-то хранить распределённо, но это чистый кастом, вряд ли фреймворки из коробки позволят тебе это сделать за просто так.

Но это только одна сторона проблемы, менее тривиальный аспект заключается в том, что все промежуточные вычисления могут аллоцировать и это нужно ловить постоянно. Каждый аллоцированный байт нужно умножать на 10 млн агентов и он превращается в 10 мегабайт. Каждый аллоцированный килобайт превращается в 10 гигабайт и вычисление будет падать с Out Of Memory.

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

function neighbours(agent)
    1. Создать массив, в котором будем накапливать результат
    2. с помощью какого-нибудь более-менее продвинутого пространственного индекса обежать окрестность агента, если в ней находятся другие агенты, то `push!` их в промежуточный массив
    3. Вернуть массив агентов

Понятно, что начинка может меняться, но основная мысль, которую хочу сказать - в этом подходе аллоцируется массив, потом он ещё несколько раз переаллоцируется когда push! пытается его растянуть.
Хотя массив будет хранить только указатели на агентов, это всё равно 8 байт на агента + оверхед от самого массива. Если у тебя в среднем 10 соседей, то это уже получится в районе 100 байт на один вызов. Умножаем на 10 миллионов агентов, и...

Правильная версия разумеется в состоит в создании контейнера, который будет переиспользоваться

function neighbours!(neighbours_container, agent)
1. создаем инкрементную переменную i, которая указывает куда будет записываться новый сосед.
2. Пробежать по окрестности агента, находя соседей, записываем их в neighbours_container, инкрементим переменную i
3. Возвращаем neighbours_container (хотя это уже опционально)

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

Джулия в целом достаточно хорошо подходит для решения этой задачи имхо, потому что можно на любом уровне абстракции писать, сохраняя скорость вычислений. Ну и в данной задаче тебе придётся спать в обнимку с @allocated 😊

я кстати часто для прожорливых функций сразу две версии пишу, одна из которых — чисто обертка, которая аллоцирует массив и передает аргументы и массив в in-place функцию

Да, я тоже так делаю 😊))

А! Второй неприятный момент с аллокациями связан с тем, что ещё довольный жёсткий оверхед от garbage collector добавится, потому что ему всю эту гору придётся ещё убирать. И если это будет гора мелких аллокаций, то боюсь, что он легко может добавить ещё +100% к времени выполнения.

может тогда использовать ЯП без GC? :D

Можно. Но GC - это следствие, не причина.

его можно отключить

(но будет только хуже думаю...)

O_O
Круто! :)

Вне зависимости от языка, память надо будет возвращать. И если будет очень много аллокаций, то доступная память станет сильно фрагментированной и тогда появится дополнительная проблема, как её дефрагментировать - то есть по сути написать свой собственный Garbage Collector.

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