В результате небольшого рефакторинга системы частиц сломался “рандом”. Как его можно сломать и на что это повлияло?

Тестировщики создали систему частиц со случайным разбрасом и получили следующий результат:

Как же могло получится, что есть явно 3 выделенных направления?

Прежде чем фиксить баг, стоит всегда понять, а какое поведение было изначально.

Но и тут есть 3 выдленных направления! Хотя если присмотрется, то их больше. Получается, только с увеличением количества частиц можно было увидеть этот баг.

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

Как повлияло добавление нового поля в класс?

Упрощенно, код генерации направления движения частицы выглядит примерно следующим образом:

constexpr int PRE_GENERATED_SIZE = 57;
std::array<Vector3, PRE_GENERATED_SIZE> preGeneratedDirection;

Vector3 GetRandomDirection(const Particle *particle)
{
    uintptr_t partticlePointer = reinterpret_cast<uintptr_t>(particle);
    uint64 particleId = static_cast<uint64>(partticlePointer);

    uint32 clampedIndex = particleId % PRE_GENERATED_SIZE;
    return preGeneratedDirection[index];
}

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

• исключает необходимость вызова функции random во время генерации частиц:
• можно записать этот массив и затем воспроизвести в точности в любой среде независимо от генератора (аля seed);

Дебаг показал, что значение clampedIndex всегда равно одному из 3 чисел {0, 19, 38}. А это значит что particleId и PRE_GENERATED_SIZE кратен 19. Выбирать в качестве делителя непростое число - странная идея, так как наличие общих делителей ухудшает распределение в пределах [0, PRE_GENERATED_SIZE]. Скорей всего, автор кода посчитал 57 простым числом. Быстрая проверка с заменой на 59 дает отличный результат - все работает корректно.

здесь могла быть гифка с фиксом, но предется поверить на слово =)

Но почему particleId кратен 19? Частицы выделяются последовательно и указатели будут располагаться на расстоянии размера частицы. Размер частицы до рефакторинга был равен 120 байтам. После добавления vector3 стал 132 байта. Но… 132 ведь не кратно 19! А вот 133 - кратен. Где еще один байт?

А тут уже виновата еще одна оптимизация в геймдеве. Для частиц используется кастомный аллакатор, который выделяет их последовательно в большом блоке памяти. Это нужно для улучшения пространственной локации частиц - в кеш процессора данные загружаются эффективнее и, как результат, снижается количество кэш миссов. Аллокатор выделяет блок размером sizeof(Particle) + short. И этот дополнительный байт используется для создания связанного списка выделенных объектов.

Распределение по статическому массиву направлений:

clampedIndex для расстояния 133 и размера 57. Тут только 3 значения:

>>> sorted([(133*i)%57 for i in range(30)])
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38]

clampedIndex для расстояния 121 и размера 57. Распределение хоть и лучше, но в распределении все равно есть дыры:

>>> sorted([(121*i)%57 for i in range(30)])
[0, 4, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26, 27, 28, 32, 33, 34, 35, 40, 41, 42, 47, 48, 49, 54, 55, 56]

clampedIndex для расстояния 133 и размера 59 уже дает честное распределение:

>>> sorted([(133*i)%57 for i in range(30)])
[0, 1, 2, 3, 4, 5, 6, 7, 15, 16, 17, 18, 19, 20, 21, 22, 30, 31, 32, 33, 34, 35, 36, 45, 46, 47, 48, 49, 50, 51]