Update: это такая замечательная история, что я не удержался и собрал на её основе целое ютуб-видео; выбирайте сами, какая форма изложения материала вам интереснее.
Вы наверняка читали уже, почему: приблизительно семьдесят процентов времени загрузки GTA Online упирается в производительность единственного треда, обрабатывающего десятимегабайтный JSON-файл с 63 тысячами записей. Объём задачи – не что-то сверхтяжёлое: десять мегабайт JSON разбираются при помощи даже совсем не по-игровому медленного Python за десятые доли секунды.
Так что… мы закончили с этим? Дело в плохом качестве кода, выполняющего тривиальную задачу? Не так быстро, время разобраться с причинами причин. Но сначала – несколько ограничим себя в глубине поиска ответов.
Мы оставим за скобками следующие вопросы:
- Что это вообще за файл и можно ли было без него обойтись
- Всегда ли загрузка игры была такой медленной именно из-за него
- Точно ли необходимо на клиенте проверять уникальность каждой записи в этом файле
Просто потому что задавшись ими – очень легко оказаться на сложной философской территории “преступление ли зарабатывание денег на видеоиграх или просто аморальная практика”, и в интернете и так достаточно сайтов, уделяющих исследованию этого направления серьёзные ресурсы.
Итак, GTA Online проводит ~70% времени загрузки в разборе десятимегабайтного JSON-файла с ~63000 записей.
JSON это чуть более сложный .ini, человекочитаемый текстовый файл, содержащий структурированные описания объектов, что-то вроде этого:
{
"key": "WP_WCT_TINT_21_t2_v9_n2",
"price": 45000,
"statName": "CHAR_KIT_FM_PURCHASE20",
"storageType": "BITFIELD",
"bitShift": 7,
"bitSize": 1,
"category": ["CATEGORY_WEAPON_MOD"]
},У нас не должно быть особых проблем с тем, чтобы его разобрать, верно? Компьютеры выполняют задачи типа этой абсолютно всё время. Почему код Rockstar настолько медленный? Очевидно, он использует очень неоптимальный парсер JSON. Профилирование исполняемого файла игры автором оригинального исследования показало, что больше всего времени он проводит в выполнении функции стандартной библиотеки C strlen(), которую, в свою очередь, вызывает sscanf().
sscanf() – это функция, считывающая из строки её кусочек и преобразующая, например, в целочисленный тип, чтобы из каждой пары типа “ключ-значение” сегмента выше, скажем,
“price”: 45000,
считать эти самые 45000 в отдельную переменную.
А strlen() – это функция, возвращающая… длину строки.
И говоря “строки” мы в данном случае имеем в виду всю десятимегабайтную текстовую последовательность целиком.
С – старый, быстрый, простой1 и опасный язык. В его стандартной библиотеке нет оптимизированных типов, обеспечивающих лёгкую работу с большими объёмами сложных данных. Строка в представлении C – это последовательность символов, завершённая специальным непечатаемым 0-символом (ASCII-код 0x00, не строковой “0”, имеющий ASCII-код 0x30). И каждый раз, когда вы, работая со встроенными типами данных С, хотите выяснить длину строки – вы не берёте это значение откуда-то из дополнительного информационного поля, куда положили его при создании или последней модификации строковой переменной. Нет. Вы просто считаете, один за одним, символы в строке, сравниваете каждый из них с 0x00, и только встретив 0x00 – останавливаетесь. Это, допустим, от нескольких до нескольких десятков тактов процессора на каждый цикл.
Для десятимегабайтной строки вы повторяете этот цикл десять миллионов раз чтобы только один раз узнать, сколько осталось до самого конца файла. И в коде Rockstar каждый вызов sscanf() вызывает strlen()2, чтобы случайно не выйти за границу строки при обработке3. GTA Online повторяет этот вызов по несколько раз для каждой из шестидесяти трёх тысяч записей – каждый раз, когда хочет считать значение каждого из её параметров! Всё это выливается в многие миллиарды циклов проверки и минуты ожидания результата.
Вторая аналогично долгая вещь – во время разбора JSON GTA Online проверяет уникальность каждого из 63 тысяч его элементов, сравнивая со всеми уже обработанными, что даёт…
(n^2-n)/2 = (63000^2-63000)/2 = 1984468500
…почти два миллиарда операций сравнения! Не заходя слишком глубоко и не ставя под сомнение необходимость этой процедуры просто отметим, что есть альтернативные алгоритмы проверки уникальности, дающие и близко не такое время выполнения на таких объемах данных.
Здесь очень легко обвинить Rockstar в полной криворукости4, но мы вместо этого заостримся на вещи поинтереснее: компьютеры настолько быстры в тривиальных задачах, и программисты настолько вынужденно хороши в декомпозиции сложных задач на тривиальные, что мы давно уже не говорим о практической скорости работы кода: достанет ли наш JSON-парсер значение переменной за 0.0001 секунды или за 0.00000001 секунды? Какая воообще разница?
Вместо этого мы привыкли говорить о вычислительной сложности алгоритма, которая выражает, как быстро объём работы, выполняемой алгоритмом, растёт вместе с ростом объёма обрабатываемых данных. И вот здесь-то и начинается сильный разброс. Обратимся к страшно упрощённой и драматизированной картинке:
Неплохо, да? Время работы алгоритмов растёт с увеличением объема обрабатываемых данных не всегда линейно, и алгоритмы с квадратичной временной сложностью занимают здесь особую нишу: они достаточно хорошо масштабируются, чтобы вы не заметили проблем с их производительностью на этапе разработки или даже при отгрузке, и достаточно плохо масштабируются, чтобы проблемы могли возникнуть позже, с ростом количества данных, и оказаться достаточно серьёзными. Если во время разработки игры количество записей в нашем многострадальном JSON-файле было в десять раз ниже, чем сейчас – его обработка задерживала загрузку игры вовсе не на десятки секунд вместо сотен.
Вернёмся к проверке уникальности и нашей формуле (n^2-n)/2 как к более простой составляющей проблемы (ситуация с strlen() похожа, но не полностью эквивалентна), но подставим туда не 63000, а 6300 записей.
Мы получим
(6300^2-6300)/2 = 19841850
двадцать миллионов операций сравнения против двух миллиардов, стократную, а не десятикратную разницу во времени выполнения! Этот код мог выполняться десятые доли или единицы секунд на стадии разработки! И тут уже вступала в дело совсем другая математика: этот код выполняется один раз, а не каждый фрейм, это не что-то, что мы хотим оптимизировать, бросив все остальные задачи. Это не что-то, что мы вообще видим как стоящую цель для оптимизации.
Разумеется, семь лет спустя GTA Online как гигантский денежный бегемот должна бы в идеале иметь совсем другие приоритеты в оптимизации, но это и совершенно другая тема, а мы завершаем на этом.
-
Что, к сожалению, абсолютно не означает, что писать код на нём просто. ↩︎
-
Технически это делает код библиотеки C, и не каждая библиотека C будет вызывать strlen() внутри sscanf() – имплементации бывают разные. Но спецификации стандарта языка – не будем углубляться слишком сильно – подгоняют имплементации к этому. Одна из двух “банальных ошибок”, замедляющих работу игры Rockstar – это даже не код Rockstar, он вполне мог бы быть другим при сборке для другой системы или даже другим компилятором! Одна из всеми любимых вещей в разработке мультиплатформенных продуктов. ↩︎
-
В C легко случаются плохие, очень плохие вещи при случайном выходе за границу строки. ↩︎
-
Хотя, допустим, в странном подходе к поиску приоритетов в оптимизации энгейджмента приносящей миллиарды GaaS – хочется обвинить и мне. ↩︎