company_banner

Как я сократил время загрузки GTA Online на 70%

Автор оригинала: t0st
  • Перевод
GTA Online. Многопользовательская игра, печально известная медленной загрузкой. Недавно я вернулся, чтобы завершить несколько ограблений — и был потрясён, что она загружается настолько же медленно, как и в день своего выпуска, 7 лет назад.

Пришло время докопаться до сути.

Разведка


Сначала я хотел проверить, вдруг кто-то уже решил проблему. Но нашёл только рассказы о великой сложности игры, из-за чего она так долго загружается, истории о том, что сетевая p2p-архитектура — мусор (хотя это не так), некоторые сложные способы загрузки в сюжетный режим, а потом в одиночную сессию, и ещё пару модов, чтобы скипнуть видео с логотипом R* во время загрузки. Ещё немного почитав форумы, я узнал, что можно сэкономить колоссальные 10-30 секунд, если использовать все эти способы вместе!

Тем временем на моём компе…

Бенчмарк


Загрузка сюжетного режима:  ~1м 10с
Загрузка онлайна:           ~6м
Без загрузочного меню, от логотипа R* до игрового процесса (без логина в Cоциальный Клуб.

Старый, но приличный проц:   AMD FX-8350
Дешёвый SSD:                 KINGSTON SA400S37120G
Надо бы прикупить RAM:       2x Kingston 8192 MB (DDR3-1337) 99U5471
Нормальный GPU:              NVIDIA GeForce GTX 1070

Знаю, что моё железо устарело, но чёрт возьми, что может замедлить загрузку в 6 раз в онлайн-режиме? Я не мог измерить разницу при загрузке из сюжетного режима в онлайн, как это делали другие. Даже если это сработает, разница небольшая.

Я (не) одинок


Если доверять этому опросу, проблема достаточно широко распространена, чтобы слегка раздражать более 80% игроков. Прошло уже семь лет!



Я немного поискал информацию о тех ~20% счастливчиках, которые загружаются быстрее трёх минут, и нашёл несколько бенчмарков с топовыми игровыми ПК и временем загрузки онлайн-режима около двух минут. Я бы кого-нибудь убил хакнул за такой комп! Действительно похоже на железячную проблему, но что-то не складывается…

Почему у них сюжетный режим по-прежнему загружается около минуты? (кстати, при загрузке с M.2 NVMe не учитывались видео с логотипами). Кроме того, загрузка из сюжетного режима в онлайн занимает у них всего минуту, в то время как у меня около пяти. Я знаю, что их железо гораздо лучше, но не в пять же раз.

Высокоточные измерения


Вооружившись таким мощным инструментом, как Диспетчер задач, я приступил к поиску узкого места.



Почти минута уходит на загрузку общих ресурсов, которые нужны и для сюжетного режима, и для онлайна (почти наравне с топовыми ПК), затем GTA в течение четырёх минут полностью нагружает одно ядро CPU, больше ничего не делая.

Использование диска? Нет! Использование сети? Есть немного, но через несколько секунд падает в основном до нуля (кроме загрузки вращающихся информационных баннеров). Использование GPU? Ноль. Память? Вообще ничего…

Что это, майнинг биткоинов или что-то такое? Чую здесь код. Очень плохой код.

Единственный поток


На моём старом процессоре AMD восемь ядер, и он ещё молодцом, но это старая модель. Его сделали ещё тогда, когда производительность одного потока у AMD была намного ниже, чем у Intel. Наверное, это главная причина таких различий во времени загрузки.

Что странно, так это способ использования CPU. Я ожидал огромное количество операций чтения с диска или массу сетевых запросов, чтобы организовать сеансы в сети p2p. Но такое? Вероятно, здесь какая-то ошибка.

Профилирование


Профилировщик — отличный способ найти узкие места в CPU. Есть только одна проблема — большинство из них полагаются на инструментирование исходного кода, чтобы получить идеальную картину происходящего в процессе. А у меня нет исходного кода. Мне также не требуются идеальные показания в микросекундах, у меня узкое место на 4 минуты.

Итак, добро пожаловать в образцы стека (stack sampling). Для приложений с закрытым исходным кодом есть только такой вариант. Сбросьте стек запущенного процесса и местоположение указателя текущей инструкции, чтобы построить дерево вызовов в заданные интервалы. Затем наложите их — и получите статистику о том, что происходит. Я знаю только один профилировщик, который может проделать это под Windows. И он не обновлялся уже более десяти лет. Это Люк Stackwalker! Кто-нибудь, пожалуйста, подарите Люку немножко любви :)



Обычно Люк группировал бы одинаковые функции, но у меня нет отладочных символов, поэтому пришлось смотреть на соседние адреса, чтобы искать общие места. И что же мы видим? Не одно, а целых два узких места!

Вниз по кроличьей норе


Позаимствовав у моего друга совершенно законную копию стандартного дизассемблера (нет, я действительно не могу его себе позволить… когда-нибудь освою гидру), я пошёл разбирать GTA.



Выглядит совсем неправильно. Да, у большинства топовых игр есть встроенная защита от реверс-инжиниринга, чтобы защититься от пиратов, мошенников и моддеров. Не то чтобы это их когда-то останавливало…

Похоже, здесь применили какую-то обфускацию/шифрование, заменив большинство инструкций тарабарщиной. Не волнуйтесь, нужно просто сбросить память игры, пока она выполняет ту часть, на которую мы хотим посмотреть. Инструкции должны быть деобфусцированы перед запуском тем или иным способом. У меня рядом лежал Process Dump, так что я взял его, но есть много других инструментов для подобных задач.

Проблема 1: это что… strlen?!


Дальнейший разбор дампа выявил один из адресов с некоей меткой strlen, которая откуда-то берётся! Спускаясь вниз по стеку вызовов, предыдущий адрес помечен как vscan_fn, и после этого метки заканчиваются, хотя я вполне уверен, что это sscanf.

Куда ж без графика

Он что-то парсит. Но что? Логический разбор займёт целую вечность, поэтому я решил сбросить некоторые образцы из запущенного процесса с помощью x64dbg. Через несколько шагов отладки выясняется, что это… JSON! Он парсит JSON. Колоссальные десять мегабайт JSON'а с записями 63 тыс. предметов.

...,
{
    "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"]
},
...

Что это? Судя по некоторым ссылкам, это данные для «сетевого торгового каталога». Предполагаю, он содержит список всех возможных предметов и обновлений, которые вы можете купить в GTA Online.

Проясним некоторую путаницу: я полагаю, что это предметы, приобретаемые за игровые деньги, не связанные напрямую с микротранзакциями.

10 мегабайт? В принципе, не так уж и много. Хотя sscanf используется не самым оптимальным образом, но, конечно, это не так уж плохо? Что ж…



Да, такая процедура займёт некоторое время… Честно говоря, я понятия не имел, что большинство реализаций sscanf вызывают strlen, поэтому не могу винить разработчика, который написал это. Я бы предположил, что он просто сканировал байт за байтом и мог остановиться на NULL.

Проблема 2: давайте использовать хэш-…массив?


Оказывается, второго преступника вызывают сразу за первым. Даже в одной и той же конструкции if, как видно из этой уродливой декомпиляции:



Все метки мои, и я понятия не имею, как на самом деле называются функции/параметры.

Вторая проблема? Сразу после разбора элемента он хранится в массиве (или встроенном списке C++? не уверен). Каждая запись выглядит примерно так:

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

А перед сохранением? Он проверяет весь массив, сравнивая хэш каждого элемента, есть он в списке или нет. С 63 тыс. записей это примерно (n^2+n)/2 = (63000^2+63000)/2 = 1984531500, если я не ошибаюсь в расчётах. И это в основном бесполезные проверки. У вас есть уникальные хэши, почему не использовать хэш-таблицу.



Во время реверс-инжиниринга я назвал его hashmap, но это явно не_hashmap. И дальше ещё интереснее. Этот хэш-массив-список пуст перед загрузкой JSON. И все элементы в JSON уникальны! Им даже не нужно проверять, есть они в списке или нет! У них даже есть функция прямой вставки элементов! Просто используйте её! Серьёзно, ну ребята, что за фигня!?

Доказательство концепции


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

План такой. 1. Написать .dll, 2. внедрить её в GTA, 3. зацепить некоторые функции, 4. ???, 5. профит. Всё предельно просто.

Проблема с JSON нетривиальная, я не могу реально заменить их парсер. Более реалистичным кажется заменить sscanf на тот, который не зависит от strlen. Но есть ещё более простой способ.

  • зацепить strlen
  • подождать длинной строки
  • «закэшировать» начало и длину
  • если поступит ещё вызов в пределах диапазона строки, вернуть закэшированное значение

Что-то вроде такого:

size_t strlen_cacher(char* str)
{
  static char* start;
  static char* end;
  size_t len;
  const size_t cap = 20000;

  // если "словили" строку и текущий указатель внутри
  if (start && str >= start && str <= end) {
    // calculate the new strlen
    len = end - str;

    // если мы около конца, выгружаемся
    // мы не хотим больше ни с чем путаться
    if (len < cap / 2)
      MH_DisableHook((LPVOID)strlen_addr);

    // супербыстрый возврат!
    return len;
  }

  // считаем реальную длину
  // нужно минимум одно измерение большого JSON
  // или нормального strlen для других строк
  len = builtin_strlen(str);

  // если это реально большая строка
  // сохраняем адреса начала и конца
  if (len > cap) {
    start = str;
    end = str + len;
  }

  // медленный, скучный возврат
  return len;
}


А что касается проблемы хэш-массива, то здесь просто полностью пропускаем все проверки и вставляем элементы напрямую, поскольку мы знаем, что значения уникальны.

char __fastcall netcat_insert_dedupe_hooked(uint64_t catalog, uint64_t* key, uint64_t* item)
{
  // без реверса структуры
  uint64_t not_a_hashmap = catalog + 88;

  // без понятия, что это такое, просто повторяем оригинал
  if (!(*(uint8_t(__fastcall**)(uint64_t*))(*item + 48))(item))
    return 0;

  // вставляем напрямую
  netcat_insert_direct(not_a_hashmap, key, &item);

  // удаляем хуки после хэша последнего предмета
  // и выгружаем .dll, мы закончили :)
  if (*key == 0x7FFFD6BE) {
    MH_DisableHook((LPVOID)netcat_insert_dedupe_addr);
    unload();
  }

  return 1;
}

Полный исходный код PoC здесь.

Результаты


Ну и как оно работает?

Прежнее время загрузки онлайн-режима: около 6м
Время с патчем проверки дубликатов:   4м 30с
Время с парсером JSON:                2м 50с
Время с двумя патчами вместе:         1м 50с

(6*60 - (1*60+50)) / (6*60) = 69.4% улучшение времени (класс!)

Да, чёрт возьми, получилось! :))

Скорее всего, это не решит всех проблем с загрузкой — в разных системах могут быть и другие узкие места, но это такая зияющая дыра, что я понятия не имею, как R* пропустила её за все эти годы.

Краткое содержание


  • При запуске GTA Online есть узкое место, связанное с однопоточным вычислением
  • Оказалось, GTA изо всех сил пытается распарсить 1-мегабайтный файл JSON
  • Сам парсер JSON плохо сделан/наивен и
  • После парсинга происходит медленная процедура удаления дублей

R*, пожалуйста, исправьте


Если информация каким-то образом дойдёт до инженеров Rockstar, то проблему можно решить в течение нескольких часов силами одного разработчика. Пожалуйста, ребята, сделайте что-нибудь с этим :<

Вы можете либо перейти на хэш-таблицу для удаления дублей, либо полностью пропустить дедупликацию при запуске как быстрое исправление. Для парсера JSON — просто замените библиотеку на более производительную. Не думаю, что есть более простой вариант.

ty <3
ITSumma
Собираем безумных людей и вместе спасаем интернет

Комментарии 49

    +14
    Извинияюсь за глупый вопрос, сам не играл, но я правильно понял, проблеса с загрузками есть с 2013 года, и никто не догадался (кроме автора поста) попрофайлить её?
      +4
      Из статьи следует, что по мере наполнения внутриигрового магазина и роста кол-ва ассортимента, росло и время загрузки. И на данный момент размер конфига достиг до 10МБ (ассортимент магазина до 63к элементов), что с неверно выбранным способом парсинга привело к отложенным проблемам, хотя кол-во и небольшое.
        +2
        Проблемы с долгой загрузкой онлайна были с самого старта, особенно страдали консольщики. Как обычно что то пофиксили, что то сломали.
          +7

          типичная проблема алгоритмов O(n^2): начальные данные слишком маленькие, чтобы обнаружить проблему на старте, через какое-то время объем данных вырастает, чтобы все начало тормозить, и не очень понятно из-за чего: "раньше работало же".

        –13
        Онлайн же так долго грузится, потому что ищет свободную совместимую сессию, сюжетка загружается довольно быстро, не мгновенно, конечно, но приемлемо. А вот в онлайн вечером можно и 15 минут заходить
          +5
          Онлайн грузится долго даже в закрытую сессию только для друзей или одиночную сессию. С релиза играю, знаю.
          +2
          Подтверждаю, онлайн всегда грузился оооочень долго, в т. ч. сейчас с последними патчами и дополнениями. Комп у меня немного побыстрее авторского.

          Очень классная статья, спасибо за перевод! Не думал, что так просто (относительно) можно исправлять такие вещи без перекомпилирования/патчинга бинарника.
          +12

          Посмотрел исходники glibc (не знаю насколько свежие) — всё именно так и есть: https://code.woboq.org/userspace/glibc/libio/strops.c.html#41


          Не совсем strlen, но тоже последовательное сканирование строки в поисках завершающего нулевого символа.


          Если кому интересно зачем так сделано — там поленились писать отдельную ветку для разбора нуль-терминированной строки, и вместо этого превращают переданную строку в буфер для как-бы-файла (FILE*). На этом этапе и требуется размер строки.


          Избежать квадратичного алгоритма можно было бы или передав размер строки в аналог sscanf, или явно открыв строку как файл и используя fscanf. Вот только стандартная библиотека не даёт сделать ни того, ни другого...

            0

            Но ведь sscanf для нуль-терминированных строк — очень широко применяемый юз-кейс, можно было и оптимизировать эту ветку.

              +1

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


              Я был бы все-таки за то, чтобы иметь какой-нибудь snscanf, который бы читал не больше n символов.

                +1
                вот так ремонт игрушки выльется в изменение стандарта с/с++…
                  0

                  Вообще они могли бы использовать какой-нибудь готовый проверенный сообществом JSON-парсер, а не велосипедить свой. JSON на 10 Мб, в общем-то, не что-то сверхъестественное.

                    0
                    Это странно. Но я регулярно вижу какие-то велосипедные json парсеры в крупных игровых проектах.
                    Чуть ли не копипасты примитивных парсеров со stackoverflow. Ощущение, что просто условный мидл которого попросили прикрутить фичу, не хочет связываться со сложными либами и берет самую простую из инета, которую может найти.
                    Это не исключение. Прям стабильно натыкаюсь на такое.
                      +2
                      Возможно либы сложно согласовывать, там лицензии всякие, вопросы с их поддержкой. А велосипед вот он, готов ехать!
              0
              После такого RG обязаны позвать его в штат.
                +25
                Вы плохо знаете RG и их хозяев TakeTwo. Повезет если не подадут в суд и не пришлют частных детективов выпытывать откуда он узнал такую сверхсекретную информацию.
                0
                Надо попросить автора оригинала сделать то же самое для Killing Floor 2.
                  0

                  А там загрузки по сколько минут занимают?

                    0
                    Там очень долгий, на несколько минут, запуск самой игры, особенно если не с SSD. Причём с другими играми на UE3 такого нет. Благо загрузки уровней в самой игре потом довольно быстрые.
                      0
                      KF2 на UE3 сделан? Тогда не удивлён долгим загрузкам. Напхали туда новых технологий мама не горюй
                  0

                  Еще в онлайн режиме она дико тормозит на пс4 ( не про )

                    +3
                    Вот будет смешно, если они так и не исправят всё равно.
                      –2

                      Зачем? Игра отживает свое.

                        +3
                        Нуу, такое. Онлайн и сейчас приносит килобаксы профита.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            +1
                            Скажите это парням которые переписывали с реверсом ГТА 3 и попали под копирайтеров. 3ю ГТА, Карл, которая еще продается
                              0
                              как отживает? летом версия для ps5 выходит с новым контентом
                              0
                              Будет не смешно, а грустно.
                                +1
                                Они ему уже 10к$ по bughounty заплатили. Так что исправят.
                                  0
                                  А есть ссылка? Всё, нашёл в оригинале. И в последнем апдейте даже написано, что уже и апдейт вышел с исправлением.
                                +4
                                Да, одна из причин, по которой я забросил GTA Online — долгое время загрузки, причем не только при запуске GTA5.exe, но и при любом переходе из сессии в сессию, например при выполнении задания, по его окончании и выходе в свободную игру и т.п. При этом загрузка сессии может не состояться и меня выбросит в свободную игру… которая тоже, в свою очередь, не загрузится и принудительно загрузит оффлайн сюжетку. Нет желания тратить (суммарно) десятки минут просто на ожидание загрузки. Я догадывался, что проблема не на моей стороне, но думал, что причина в «бутылочном горлышке» где-то на полпути к серверам Rockstar. А оно вот как оказалось…
                                  +1

                                  А что если использовать вместо json какой-то бинарный формат данных?

                                    +4
                                    Ну да Вы что, тогда на собеседованиях вместо вопроса «Слышали ли вы о JSON?» надо будет спрашивать «Слышали ли вы о бинарных форматах данных?», это сузит круг соискателей и придётся предлагать им более высокие зарплаты.
                                      +5

                                      В данном случае проблема не в JSON, а в зачем-то написанном самодельном неэффективном парсере, при том что готовых горы, в том числе под лицензиями, допускающими беспроблемное использование в закрытом софте.

                                        +3

                                        JSON можно парсить со скоростью 3гбайта на ядро. Или за 3.5мс в данном случае, причём скорость чтения с современного ССД и парсинга будут +- сравнимыми, при желании можно хоть каждый фрейм перепарсивать, после перечитывания с диска без кеширования :)

                                          +1
                                          со скоростью 3гбайта на ядро.
                                          Это как ехать со скоростью 100 километров на машину?
                                        +3
                                        Играю периодически, тоже бесит долгая (и негарантированная) загрузка онлайн. Поделюсь лайвхаками.
                                        Есть простой способ «выгнать всех» из сессии: запускаем виндовый Монитор ресурсов, находим процесс GTA5, ПКМ — «Приостановить процесс», ждем когда когда в миганиях лапочки на LAN (я гляжу на свой роутер) возникнут перебои (или просто считаем до 10) — «Возобновить процесс», вуаля, все вышли, ты один в сессии (для остальных в сессии это ты вышел).
                                        Подобным способом ускоряю загрузку в сессию: при загрузке игры наблюдаю за индикатором LAN, как начался интенсивный сетевой обмен (идет «синхронизация» с сессией), замораживаю-размораживаю процесс GTA5 и попадаю в пустую сессию.
                                          0

                                          Но парсинг JSON это не ускорит.

                                          +2
                                          Жесть.
                                          У меня на php сотнимегабайтные XML(1c)/YML/Excel от поставщиков на десятки тысяч товаров парсятся не более чем за 10 секунд, через практически ручной построчный разбор, используя XMLReader, вместе с групповой вставкой в базу (которая ещё ведёт лог изменений через триггеры).

                                          Какие нафиг 1м50с (и тем более 6мин) на парсинг 10мб? Тем более на С.
                                            +1

                                            Все просто, у вас O(n) алгоритм, а в GTA — внезапный O(n^2). Ну не думал разработчик, что sscanf будет по всей строке пробегаться каждый раз. А со вторым примером — кого-то явно не спрашивали на собеседовании про хеш таблицы.

                                              0

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

                                                0
                                                Её просто никто не пытался решить — это вопрос к менеджменту. Проблему долгой загрузки знает кто угодно, кто играл в GTA5 Online, причём таких загрузок, бывает, проходит по нескольку штук (т.е. в сумме 10 и более минут ожидания может накопиться), пока компанией пытаешься соединиться на одном сервере. Эти ожидание отбивают всякое желание играть в онлайн в компании, только если случайно зайти куда то, что тоже не всегда интересно.
                                                0
                                                Со вторым примером кто-то предусмотрел вероятность дубликата хеша. Правда не учёл, что данные никогда не дублируются.
                                                  0

                                                  На самом деле, для разных данных хэш в общем-то имеет право совпадать. Но тем не менее, стандартные хэш-таблицы позволяют искать дубликаты за почти константное время (для этого правда надо иметь хорошую хэш-функцию, но ведь взять готовую тоже вполне можно)

                                                    0

                                                    Ну вот, правильная обработка коллизий — это основа хэш таблицы. Если тупо пробегать по ней всей каждый раз, то смысл вообще хэши считать? Просто разработчик не знал про такую структуру данных и нагородил что-то свое. А ревью у них или нет, или оно попало к такому же.

                                                  0

                                                  Спасибо за статью. Читалось как детектив. А убийца как обычно дворецкий.


                                                  Но если честно, после таких статей становится непонятно почему самолёты падают так редко...

                                                    0
                                                    Когда начали менять и дополнять то, что диды писали — так и повалились один за другим.

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое