Как засунуть слона в чемодан

Меня всегда удивляло как разработчики умудряются размещать большой объем вычислений на относительно слабом железе, к каким трюкам и решениям прибегают, чтобы приложение работало быстро, это относится не только к игровым движкам, но и базам данных, системам управления и т.д., но так как моя область это все же игры и игровые движки, то рассказывать я буду про них. Особенно заметна эта разница была при портировании относительно свежих игр (поколение ps3+) на всякие портативные консоли вроде Nintendo Switch, Apple TV (это девайс тоже считается неплохой платформой, в плане что там есть платящая аудитория) и мобилки. И свитч и appletv по производительности не сильно далеко ушли от третьей плойки, и попытки перенести требовательные игры, рассчитанные как минимум на следующее (ps4) поколение консолей, приводят к значительным проблемам, которые непросто решаются. Игры это достаточно требовательный софт, зачастую с мягким реалтаймом, надо же выдавать приемлимый фпс — иначе играть будет больно, некомфортно и её никто не купит. Небольшим подспорьем при переносе на портативки и мобилки является их стабильное железо, хотя вот для мобилок я бы так не сказал, там целый зоопарк процов, видях и окружения. На консолях с этим все получше и спеки меняются раз в пару лет. Когда речь заходит о портировании игры — оптимизации можно разделить на несколько уровней: архитектура, алгоритмы и код.

1. Оптимизации на уровне архитектуры (~50% прироста)
   
   Этот уровень отвечает за общую структуру игры и движка, его компоненты и взаимодействие между ними. Если архитектура изначально спроектирована неоптимально, это приводит к серьезным проблемам с производительностью на слабых устройствах. Неверный выбор системы управления памятью (читай кривые пулы и много копирования), избыточное количество алокаций или неправильная организация тредов (столлы и частые смены контекста выполнения) создают узкие и трудночинимые места, которые практически невозможно исправить на более поздних этапах разработки, не говоря уже об этапах постразработки — вроде портирования. И решенение проблем на этом уровне дает самый ощутимый буст перфа, но обычно для этого надо переписать полдвижка.

2. Оптимизации на уровне алгоритмов и структур данных (~30%)
   
   На этом уровне решается, какие алгоритмы и структуры данных использовать для выполнения конкретных задач. Хороший (это не значит самый быстрый или академический) или правильно подобранный алгоритм может значительно ускорить работу всей игры. Например, замена линейного поиска на бинарный поиск, использование хеш-таблиц вместо списков или применение структур данных с оптимизированной сложностью доступа (например, деревья поиска) может дать огромный прирост производительности. Но есть и обратные примеры, простой линейный поиск по массивам, которые укладываются в кеш проца значительно быстрее, чем использование хеш-мап, и даже самых оптимизированых но сложных решений.

3. Оптимизации на уровне исходного кода + асм (~10%)
   
   Это уже касается конкретных реализаций в коде, где микро-оптимизации направлены на время выполнения отдельных блоков кода или даже единичных операций, но чаще на использование памяти и доступ к данным. Хорошим примером тут будет устранение аллокаций памяти где это только возможно, разворачивание циклов, если компилятор «нешмогла» и много чего другого. В основном этот этап заключается в запуске профайлера и последующем долгом анализе колстеков, в попытке починить, то что уже сломано настолько, что стало видно в профайлере.

4. Все остальное (~10%)

   Что можно сказать об этой части? Обычно она включает в себя нормальные сборочные пайплайны, когда билд попадает к QA через час после комита и возвращается к автору через два если были ошибки. Кастомные инструменты отладки и игровые реплеи — современные инструменыт игровой разработки (BT — behavior tree, VS — visual scripts, blueprints, AS — animation scripts) очень сложно дебажить из под отладчика, а баги с ними связанные в 99% случаях не воспроизводятся, хотя конечно зависит от профессионализма QA. Эти улучшения могут не оказывать прямого влияния на производительность игры во время её работы, но способствуют более быстрому выявлению и устранению проблем, а когда разработчик не чинит баг, он делает фичу, т.е. непосредственно наносит добро проекту.

Программные игровые реплеи пожалуй лучшее средство отладки багов, что я видел за время разработки, это как time travel debugging, но не требует поддержки со стороны компилятора и намного дешевле в разработке.

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

Другой вопрос дадут ли ход таким изменениям? Скорее всего нет, менять архитектуру ни архитект проекта, ни техлид или техдир в 99.9999% не разрешат. Во первых — это не забота программиста, во-вторых такими решениями вы просто отбираете хлеб архитекта, и в-третьих изменяя существующую, работающую и отлаженную систему вы ломаете соседние, и когда эта бага всплывает, а она обязательно всплывет, никто сказать не может. Вот эта последняя причина и не дает пришедшему вчера разработчику переписать половину движка и сделать как правильно 🙂 Остается довольствоваться изменениями на уровне кода-алгоритмов, что однако тоже дает возможность «причинить добро» в размер 10%+ к скорости работы.

Изоляция компонентов

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

Микро и мелкие оптимизации

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

• Оптимизация циклов: анализ и замена вложенных циклов на более эффективные.

• Поиск и избавление от линейного поиска в коде или циклах

• Устранение ненужных вызовов функций в критических местах кода.

• Избавление от алокаций памяти в циклах или горячих функциях

Эти небольшие участки кода не будут влиять на перф игры на больших консолях или пк, прирост 1-2% никому не интересен, потому что требует много усилий и времени, но незаметен и соответственно менеджмент считает, что лучше потратить время на разработку фичи. Но на портативках даже такие «небольшие» изменения дают ощутимый прирост производительности, особенно если они применяются в горячих участках кода, которые вызываются многократно. Стоит отметить, что написание правильных и эффективных двух-трех строк кода может потребовать анализа, экспериментов и времени порядка нескольких дней. А еще тщательного профилирования и понимания поведения кэша процессора на конкретном участке логики.

Мифы о низкоуровневых оптимизациях

Существует распространенное заблуждение, что оптимизации на этом уровне требуют использования сложных и труднопонимаемых решений, таких как написание кода на асме, использования роксайнс алгоритмов или поголовного перевода в SIMD реализацию. Хорошо, что на практике это не всегда так и многие оптимизации получаются довольно простыми и интуитивно понятными. Например:

• Избыточное копирования данных (передача таких аргументов в функции).

• Временные объекты там, где можно прокинуть ссылку или указатель (строки).

• Ненужные аллокации и переалокации памяти (строки, массивы, хранение объектов).

• Лишние ветвления в «горячих» участках кода (nested if).

• Сложный и запутанный лапшекод на 30 экранов (spagetti-logic)

Часто чистый и понятный код сам по себе работает быстро, потому что он проще для компилятора и оптимизатора. Но не всегда.

Дорогая проверка (история из одного проекта)

Уровни игры, где мне довелось участвовать в разработке под мобилки, описывались внутренним форматом, похожим на json, который требовал экранирования некоторых символов. Основная разработка велась на ПК конечно, и там проблем с перфом не было. Игра могла получать внешние изменения в нескольких форматах от разных серверов (json, bjson, xml, kvpatch) плюс пользователи могли сами создавать и делиться уровнями, компоновкой районов и отдельными зданиями (custom yaml). Весь обмен данными шел через сервера игры, которые присылали изменения и обновления в бинарном виде (экономия трафика) и для корректной обработки их необходимо было восстановить в текстовый вид, затем нормализовать до json’a, который уже надо было конвертнуть во внутренний формат, чтобы парсер уровня мог их прочитать. Уровни запрашивались каждый раз с сервера, чтобы пользователи не могли себе начитить деньжат, т.к. часть симуляции проводилось на локальном устройстве. Данные могли приходить в разных форматах из разных систем, и в процессе обработки 4 (четыре!) раза полностью проверялись на необходимость экранирования.

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

В играх вообще очень много текстовых данных, они есть в конфигах, в локализациях, в названиях ресурсов. И строки часто представляются с помощью кавычек ". Но что происходит, если сама строка содержит кавычки? В таком случае строку нужно экранировать. Например, символ кавычки " или обратного слэша \ нужно заменить на \" или \\. Вы с легкостью напишете код на своем любимом языке для этой проверки. Большинство строк не нуждаются в экранировании. Поэтому полезно иметь возможность быстро проверить, требует ли строка экранирование. Алгоритм очень простой — функция принимает аргумент типа eastl::stringz с именем v, в стандарте с++14 еще не было string_view но кастомные решения для non-zero-terminated строк уже были. Она проходит по каждому символу c во входной строке v.

bool need_escaping_symbol(eastl::stringz v) { // stringz -> string_view   for (char c : v) {     if ((uint8_t(c) < 32) | (c == '"') | (c == '\\')) {       return true;     }   }   return false; }

Внутри цикла сначала используется сравнение (uint8_t(c) < 32), которое проверяет, меньше ли ASCII-значение символа 32. Это условие позволяло экранировать управляющие символы (такие как новая строка, табуляция и т.д.), формат имел некоторую специфику от json, поэтому их тоже надо было экранировать для правильной работы парсера.

Затем сравнение (c == '"') проверяет, является ли символ двойной кавычкой, а (c == '\\') проверяет, является ли символ обратным слэшем. Если хотя бы одно из этих условий истинно для какого-либо символа, функция возвращает true, указывая, что символ требует экранирования. Если ни одно из условий не выполняется для всех символов, функция возвращает false, указывая, что экранирование такой строки не требуется. Просто? Ну не сложно как минимум, и понятно даже джуну. На пк (в симуляции) этот код работал с хорошей скоростью и не требовал никаких изменений. На мобилках же ситуация была печальная, пустой уровень грузился 10+ секунд, из которых 2 секунды уходило на парсинг и применение текстовых конфигов. А с ростом числа объектов на уровне это время становилось все больше и больше и на полностью заполненных зданиями уровнях улетало где-то за 2 минуты на топовых во время разработки iPhone 5s, что конечно никак не могло понравиться QA отделу и пользователям. Пятнадцать секунд загрузки это был максимум на который мы могли рассчитывать для прохождения сертификации в стор.

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

bool linear_need_escaping_symbol(eastl::stringz v) {   bool b = false;   for (char c : v) {     b |= ((uint8_t(c) < 32) | (c == '"') | (c == '\\'));   }   return b; }

Неплохо получить немного перфа просто избавившись от if , но явно недостаточно, чтобы избавиться от назойливых репортов QA отдела. Зато мы можем сделать финт ушами и избавиться от QA арифметических операций и сравнений в коде, для этого надо создать таблицу, которая уже содержит все проверки для каждого возможного значения байта и флаг о том, требуется ли его экранирование или нет. Это требует немного больше усилий, но результат в итоге получился довольно быстрым, для проверки каждого символа достаточно одной загрузки из таблицы.

static constexpr eastl::sarray<uint8_t, 255> vflt_quotable_character =     []() constexpr {   eastl::sarray<uint8_t, 255> result = {0};   for (int i = 0; i < 32; i++) {     result[i] = 1;   }   result['"'] = 1;   result['\\'] = 1;   return result; } ();  bool table_need_escaping_symbol(eastl::stringz view) {   uint8_t needs = 0;   for (uint8_t c : view) {     needs |= vflt_quotable_character[c];   }   return needs; }

Можем ли мы сделать быстрее?

Да, если использовать SIMD-инструкции, NEON для мобилок или SSE для пк. А так как обычно строки не слишком длинные — 60% строк меньше 64 символов — это ключи, имена ресурсов, флаги и просто короткие строки, то общая идея состоит в том, чтобы загружать данные блоками по 16 байт и выполнять сравнения над этими байтами одновременно. Магии здесь нет, зачем сравнивать по одному символу если можно выполнять N сравнений одновременно, это просто физически должно работать быстрее. А что делать, если у нас меньше N символов или остался хвост? Ну тогда просто вернемся к уже существующему решению, которое и так показывает неплохие результаты. Для SSE решению будет примерно такое, для NEON будет похоже.

inline bool simd_need_escaping_symbol(eastl::stringz view) {   int size = view.size();   if (size < 16) {     return linear_need_escaping_symbol(view);   }      size_t i = 0;   __m128i r = _mm_setzero_si128();   for (; i + 15 < size; i += 16) {     __m128i word = _mm_loadu_si128((const __m128i *)(view.data() + i));     running = _mm_or_si128(r, _mm_cmpeq_epi8(word, _mm_set1_epi8(34)));     running = _mm_or_si128(r, _mm_cmpeq_epi8(word, _mm_set1_epi8(92)));     running = _mm_or_si128(r, _mm_cmpeq_epi8(_mm_subs_epu8(word, _mm_set1_epi8(31)),                                 _mm_setzero_si128()));   }      if (i < size) {     __m128i word = _mm_loadu_si128((const __m128i *)(view.data() + view.length() - 16));     running = _mm_or_si128(r, _mm_cmpeq_epi8(word, _mm_set1_epi8(34)));     running = _mm_or_si128(r, _mm_cmpeq_epi8(word, _mm_set1_epi8(92)));     running = _mm_or_si128(r, _mm_cmpeq_epi8(_mm_subs_epu8(word, _mm_set1_epi8(31)),                                 _mm_setzero_si128()));   }   return _mm_movemask_epi8(r) != 0; }

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

Всех с наступающим Новым Годом!