Pipius & Painless
Painless Painless
Я тут как раз думала, как можно было бы улучшить простой алгоритм для логики игры в реальном времени, чтобы он занимал мало памяти. Ты недавно какие-нибудь интересные структуры данных пробовал?
Pipius Pipius
Да, я тут ковырялся с кольцевым буфером без блокировок для очередей событий, чтобы получать операции добавления и извлечения за O(1) без всякого GC. Ещё заменил обычный вектор на плоский массив с общим блоком памяти – никакой фрагментации кучи, кеш работает как часы. Для поиска использую плотный битсет для отслеживания активных сущностей, а потом – разреженную карту, чтобы сразу переходить к их компонентам. Память экономится, и процессор доволен. А как ты обычно обрабатываешь обновления сущностей?
Painless Painless
Звучит убедительно. Обычно я делаю цикл обновления полностью управляемым данными: прохожу по плотному битовой карте, получаю указатели на компоненты из разреженной карты и выполняю логику в компактном блоке, удобном для кэша. Если что-то начинает тормозить, перехожу на двухэтапную обработку: один поток собирает изменения состояния, другой применяет их пакетом. Загрузка процессора хорошая, и код остаётся понятным. Какие-нибудь конкретные проблемы с производительностью заметил?
Pipius Pipius
Я до сих пор гоняюсь за этим одним багом, который постоянно ускользает. Битсет в порядке, но мой собственный планировщик, который я написал с нуля, добавляет микро-задержку при переключении контекста каждые 16 кадров – буквально, микро-переключение, которое «съедает» кучу циклов. И еще я заметил, что использование буфера, выровненного по 32 бита, для состояний физики дает мне небольшое преимущество по сравнению со стандартными 64-битными массивами; так как это просто удобнее в моем движке. Процессор работает стабильнее, но этот крошечный нюанс постоянно маячит в голове, готов к доработке. А как у тебя с потоками – блокируешь ли ты данные или тоже используешь безатомарные решения?
Painless Painless
Микропереключатель, который стоит нескольких циклов, почти неизбежен, если ты делаешь настоящую смену контекста. Если удастся его вообще избежать – обычно это выгодно, но это всегда компромисс. Я сейчас склоняюсь к безблокировочному решению для основного состояния, но всё равно блокирую небольшой read-only регион для интерфейса и для нескольких контрольных точек безопасности. Так данные остаются в целости, и производительность не сильно страдает. А какой максимальный оверхед ты наблюдал от своего планировщика?
Pipius Pipius
Самая большая головная боль сейчас – это ведение учета зависимостей в моем планировщике. Каждый раз, когда я добавляю новую задачу, перестраиваю небольшой граф зависимостей, и пока это нормально, если задач немного, то когда граф разрастается – становится ощутимо медленнее. По сути, это небольшой проход O(n²), который выполняется каждый кадр. Я работаю над подходом с дельта-обновлениями, чтобы пересчитывать только измененные связи, но пока что это все равно мучительно.
Painless Painless
Похоже, ты сейчас делаешь перестройку самым простым, "грубым" методом. На практике я держу граф в виде разреженной списочной матрицы смежности и обновляю только те рёбра, которые реально меняются. Когда добавляется или удаляется задача, я просто корректирую её входящие и исходящие списки, а потом запускаю небольшой инкрементный топологический сорт вместо полного сканирования O(n²). Если проблема не уходит, попробуй отвязать перестройку зависимостей от потока отрисовки – просто помещай обновления в очередь и пусть следующий кадр подхватит то, что ты не успел. Так затраты на кадр снижаются, и процессор будет работать без простоя. Насколько сложен у тебя сейчас набор задач?