Хотел понять, что именно делает Bevy, когда «просто работает быстро», и написал архетипный ECS сам. Заодно проверил на числах одну вещь, в которую до этого верил на слово: что архетипы всегда быстрее. Оказалось — не всегда, и это самое интересное в теме.
Сразу главное расхождение с тем, что я планировал: Rust-часть в архиве есть, но она не собиралась. На машине, где я это писал, нет cargo. Поэтому все цифры ниже — из рабочего Python-прототипа того же алгоритма: те же архетипы, те же колонки, тот же swap_remove, те же поколения хэндлов. Форма одна, скорость разная, и я не буду делать вид, что это бенчмарк крейта.
Почему сущность — это не мешок компонентов
Наивный ECS: сущность — словарь, компонент — значение по ключу. Удобно, пока сущностей тысяча. На ста тысячах каждая система на каждой сущности лезет в хеш-таблицу, а данные одной сущности размазаны по памяти так, что кеш процессора не спасает.
Архетипный ECS переворачивает хранение. Набор типов у сущности задаёт архетип. Внутри архетипа данные разложены колонками: список Position, рядом список Velocity, и оба выровнены по рядам. Сущность — это пара (архетип, ряд), а запрос идёт по колонкам подряд, как по массиву.
Запрос стоит не «сколько сущностей в мире», а «сколько подходящих»
Это видно на маленьком примере из транскрипта. Спавню четыре разных набора: 1000 сущностей с одним Position, 2000 с Position+Velocity, 500 с тремя компонентами, 300 с Velocity+Health. Получается четыре архетипа и 3800 строк — каждая сущность лежит ровно в одном архетипе.
запрос Position -> 3500 сущностей
запрос Position+Velocity -> 2500 сущностей
запрос Position+Velocity+Health -> 500 сущностей
запрос Health (без Position) -> 800 сущностейquery(Position, Velocity) не обходит 1000 сущностей, у которых есть только Position. Он их вообще не видит: он выбирает архетипы, а не строки. Отсюда и главный эффект — добавление в мир сущностей с другим набором компонентов почти не замедляет системы, которые этот набор не трогают.
Удаление: swap_remove и правило, которое из него следует
Удаление строки не сдвигает весь список. Последняя строка встаёт на место удалённой, длина уменьшается на единицу, а сущность из последней строки получает новый ряд.
было: 0:e0 1:e1 2:e2 3:e3 4:e4
удалили ряд 1 -> e4 встаёт на его место
стало: 0:e0 1:e4 2:e2 3:e3Дешево — но из этого следует правило, которое ловит всех: итерацию нельзя продолжать после удаления. Порядок строк поменялся, и текущий индекс теперь указывает на другую сущность. В моём прототипе despawn внутри цикла по колонкам не защищён — это ограничение записано в README, а не спрятано под «используйте осторожно».
Поколения: чтобы старый хэндл не ожил
Слот удалённой сущности переиспользуется. Если хэндл — просто индекс, то старый хэндл начнёт указывать на нового жильца, и это самый неприятный класс багов: программа работает, но не с теми данными. Поэтому хэндл — упакованное целое: младшие 32 бита индекс, старшие поколение. При удалении поколение растёт.
a = w.spawn(Position=1) # index 0, gen 1
w.despawn(a) # слот 0 свободен, gen 2
b = w.spawn(Position=2) # index 0, gen 2 — тот же слот, другой хэндл
w.alive(a) # False
w.alive(b) # TrueВ тестах на это отдельный случай: после деспавна проверяется, что слот переиспользован, что поколение выросло и что старый хэндл мёртв. Дешевле, чем искать такой баг через месяц.
Числа: где архетипы выигрывают и где проигрывают
Сто тысяч сущностей с Position и Velocity, двадцать итераций интеграции — два миллиона обновлений. Сравниваю с наивным словарём сущностей. Замер — три прогона, беру лучший и медиану, gc на время замера выключен.
архетипы : лучший 1.384 с медиана 1.566 с 692.1 нс/обновление 1.4 млн/с
словари : лучший 1.825 с медиана 1.833 с 912.5 нс/обновление 1.1 млн/с
ускорение по лучшему: x1.32Полтора раза. Не «в десять», как обещают статьи, и вот почему: в CPython стоимость самого цикла и арифметики над объектами такая, что доступ к памяти перестаёт быть узким местом. В Rust на этом месте разрыв больше — там между колонкой и инструкцией процессора ничего нет.
А теперь то, ради чего всё писалось. Вставка компонента: двадцать тысяч сущностей, три раунда insert+remove, то есть сорок тысяч переездов между архетипами.
архетипы : 0.567 с на 40к переездов 14165.8 нс на переезд
словари : 0.025 с на 40к вставок 618.8 нс на операцию
итого: на вставке архетипы медленнее в x22.9Двадцать три раза медленнее. Не потому, что код плохой, а потому что это принципиально другая операция: словарю достаточно вставить ключ, а архетипный ECS копирует строку в новый набор колонок и делает swap_remove в старом. Плюс в питоне на каждый переезд собирается и разбирается словарь компонентов — в Rust эта часть дешевле, но копирование строки остаётся.
Отсюда практическое правило, которое видно из чисел: компоненты добавляют пачкой при спавне, а не по одному в горячем цикле. Именно поэтому в Bevy команды собираются и применяются в конце системы — не из любви к архитектуре, а потому что переезд дорогой.
Rust-часть: что там есть и чего в ней нет
В архиве rust/ — тот же алгоритм на Rust: колонки как Vec в Box, ключ архетипа из TypeId, Entity с поколением, swap_remove через сохранённые указатели на функции удаления и обмена (потому что тип колонки известен только при создании). В горячем цикле integrate есть unsafe: два &mut из одного HashMap borrow checker не даст, и это ровно та причина, по которой внутри Bevy тоже есть unsafe.
Чего нет: сборки. cargo test и cargo bench я не запускал, сравнение с hecs и bevy_ecs не сделано. Бенч-файл на criterion лежит и запускается одной командой у тебя, но столбца «hecs» в моих числах нет, и придумывать его я не стану. Ожидание: на итерации в Rust разрыв больше x1.32, на переездах — меньше x22.9; проверка занимает минуту.
Что в архиве
Рабочий Python-ECS (ecs/world.py), бенч, четырнадцать тестов на переезды, swap_remove, устаревшие хэндлы и семантику запросов, make_transcript.py с прогоном в transcript.txt — из него взяты все цифры выше. И Rust-крейт рядом, помеченный как несобранный: rust/src/lib.rs, rust/benches/iter.rs, Cargo.toml.
Если будешь сравнивать с готовыми — держи в голове, что мой прототип не оптимизирован вообще: zip по двум колонкам, объекты на компонент, никакой упаковки. Числа показывают форму алгоритма, а не потолок реализации.