Вас приветстует игровой канал Иван Чернякова!

На самом деле просто курьезов в игрострое опубличено больше, вот и рассказываю.

Оплошали даже Rockstar’ы.

В GTA Online много лет была загрузка, которая на некоторых ПК занимала около шести минут. В 2021 году программист под ником t0st решил выяснить, что игра вообще делает всё это время.

Оказалось — буквально мучает процессор двумя очень красивыми алгоритмическими ошибками. (meh.)

При запуске GTA Online читала JSON примерно на 10 МБ — каталог из ~63 000 игровых предметов. И парсер постоянно вызывал strlen() для оставшегося куска строки.

strlen() в C не знает длину строки заранее: он идёт по символам до \0. То есть вместо того, чтобы один раз узнать длину, игра снова и снова пробегала огромный кусок JSON.

Но дальше было ещё веселее.

Для каждого из 63 тысяч элементов игра проверяла, нет ли его уже среди загруженных. Причём не через hash set, где поиск в среднем O(1), а обычным проходом по всему массиву.

Получалось примерно:

1 + 2 + 3 + … + 63 000 ≈ 2 миллиарда сравнений.

Это классическое O(n²): если данных станет в 10 раз больше, работы станет примерно в 100 раз больше.

Самое прекрасное — все элементы в исходном JSON и так были уникальными. То есть эти два миллиарда проверок вообще не были нужны. (meh.)

t0st пропатчил бинарник без исходников: закешировал длину строки и убрал бессмысленный поиск дублей.

6:00 → 1:50. Минус 69,4% времени загрузки.

Rockstar проверила его находку, внесла исправления в GTA Online и выплатила ему $10 000 через bug bounty. (АрсТехника)

Прекрасное напоминание: иногда проблема производительности игры стоимостью миллиарды долларов — не GPU, не сеть и не диск.

А цикл не той сложности.

А они хотят, чтобы мы железо постоянно обновляли!!!!

Агенты, спасите!

В посте указаны ссылки на оригинальный пост пользователя t0st об этой проблеме, но вот еще на всякий случай ее перевод на Хабре)