Как я улучшил производительность JSON-парсера в два раза

Введение

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

О оптимизации кода

Первым шагом в любой оптимизации кода является профилирование. Любые предположения о том, что нуждается в оптимизации без объективных данных профилирования, скорее всего, будут неверными. Многие, включая меня, попадали в ловушку, думая: «Я лучше знаю, как это будет выполняться». Даже с профилировщиком предположения о производительности конкретных частей вашей программы действительны только для вашего оборудования и версии ОС. Однако это лучше, чем вносить изменения вслепую.

Переход от парсинга char[] к byte[]

При написании парсеров для текстовых форматов данных или протоколов есть два способа обработки входных данных: обращаться к ним как к строкам или как к числам. JSON — это текстовый формат, поддерживающий строки в кодировке UTF-8, но все значимые для разметки символы находятся в диапазоне ASCII. Это означает, что его можно парсить без декодирования символов из byte в char, но всё еще надо детектить и пропускать многобайтовые символы. Предыдущая реализация токенизатора была такой:

1. Чтение байтов из потока в буфер byte[].

2. Декодирование этого буфера byte[] в другой буфер char[].

3. Токенизация этого буфера char[].

4. Интерпретация этих токенов.

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

1. Чтение байтов из потока в буфер byte[].

2. Токенизация этого буфера byte[].

3. Декодирование только строковых токенов.

4. Интерпретация этих токенов.

Это потребовало значительного изменения токенизатора и само по себе обеспечило минимальное улучшение производительности. Однако этот подход позволил реализовать несколько других оптимизаций, таких как кэширование коротких строк и использование парсеров чисел сразу из byte[], о которых будет рассказано ниже.

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

Типичный парсер данных состоит из токенизатора и лексера. Токенизатор обрабатывает каждый байт/символ в потоке данных и разделяет поток данных на токены, в то время как лексер придает этим токенам контекст (этот токен — число, этот токен — строка и т.д.). Код в цикле токенизации вызывается наиболее часто, и даже небольшие оптимизации могут значительно повысить производительность.

Замена цепочек if на единичные обращения к массиву

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

// OLD if (charCode == SPACE_CHAR_CODE ||      (charCode >= TAB_CHAR_CODE && charCode <= RETURN_CHAR_CODE) ||      charCode == NO_BREAK_SPACE_CHAR_CODE ||      charCode == IDENTIFIER_SEPARATOR_CHAR_CODE ||      charCode == VALUE_SEPARATOR_CHAR_CODE ||      charCode == END_ARRAY_CHAR_CODE ||      charCode == END_OBJECT_CHAR_CODE ||      charCode == BEGIN_OBJECT_CHAR_CODE ||      charCode == BEGIN_ARRAY_CHAR_CODE) {   // ... }  // NEW static bool[] LexemeTerminatorChars;  if (charCode < LexemeTerminatorChars.Length &&      LexemeTerminatorChars[charCode]) {   // ... }

Развертывание структуры ArraySegment из поля в локальные переменные

Токенизатор не читает файл байт за байтом, а работает с буфером данных. В C# структура ArraySegment используется для фрагментов данных и изначально хранится в классе чтения, занимая 16 байт. Токенизатор обращается к ней много раз в цикле при парсинге буфера на токены. Поскольку компилятор не может предположить состояние этого поля в классе между обращениями, каждое обращение генерирует инструкции для чтения, проверки на null для ArraySegment.Array и проверки границ. Переместив массив и границы в метод и вне цикла, компилятор может оптимизировать эти проверки. Это простое изменение дает заметный прирост производительности на горячих блоках кода .

private ArraySegment<byte> rawJsonValue;  // OLD bool NextToken() {   if (this.rawJsonValue.Count == 1)   {     var oneCharNotation = this.rawJsonValue[this.rawJsonValue.Offset];     // ...   }   else if (this.rawJsonValue.Count == 4 &&             SequenceEqual(this.rawJsonValue, JsonNotation.Null))    {     // ...   } }   // NEW bool NextToken() {   var rawJsonArray = this.rawJsonValue.Array;   var rawJsonOffset = this.rawJsonValue.Offset;   var rawJsonLength = this.rawJsonValue.Count;    if (rawJsonLength == 1)   {     var oneCharNotation = rawJsonArray[rawJsonOffset];     // ...   }   else if (rawJsonLength == 4 &&             SequenceEqual(rawJsonArray, rawJsonOffset, JsonNotation.Null))    {     // ...   } }

Использование класса Utf8Parser для преобразования byte[] в числа/DateTime/TimeSpan

.NET давно поддерживает парсинг дат, времени и чисел напрямую из byte[], минуя стадию декодирования байт в string, используя класс Utf8Parser. Использование этого класса уменьшает количество выделений памяти для string и улучшает производительность парсинга чисел из текста.

// OLD double ReadJsonAsNumber() {   string tokenAsString = this.ReadJsonAsString(); // costly and wasteful   return double.Parse(tokenAsString, CultureInfo.InvariantCulture); }  // NEW double ReadJsonAsNumber() {    if (Utf8Parser.TryParse(this.rawJsonValue.AsSpan(), out double value, out _))    {       return value;    }    else     {       throw new FormatException(/* error message */);    } }

Развертывание сложной структуры ReaderNode в отдельные поля: от абстракции к конкретной реализации

«Любую проблему в компьютерной науке можно решить с помощью еще одного уровня индирекции, за исключением проблемы слишком большого количества индирекций.» — David Wheeler

Моя предыдущая реализация парсера имела элегантный интерфейс для текущего состояния парсера, где толстенькая структура ReaderNode хранила текущий токен и его значение. Значение токена также было абстрагировано для поддержки хранения чисел, строк и сложных объектов. Согласно профилировщику, эта гибкость имела значительную стоимость в производительности парсера. Оптимизация заключалась в упрощении всего до примитивных свойств/полей и отказе от абстракций.

// FROM class JsonGameDataReader {   public ReaderNode Node { get;} }  public readonly struct ReaderNode {   private readonly IStrongBox value;    public readonly ReaderToken Token;   public readonly Type ValueType;    public bool ValueAsBoolean => /* ... */   /* ... */ }  // TO class JsonGameDataReader {   private ReaderToken token;   private bool boolValue;   private bool stringValue;   /* ... other types */     public ReaderToken Token => this.token;   public bool ValueAsBoolean => this.boolValue;   public bool ValueAsString => this.stringValue; }

Использование кэширования строк для уменьшения выделения памяти

«Есть две сложные проблемы в компьютерной науке: инвалидация кэша, именование вещей и ошибки на единицу.» — Leon Bambrick

Еще один трюк из времен бородачей — кэширование результатов тяжелых алгоритмов. Наиболее затратной по памяти и производительности частью парсинга JSON является обработка строк. Часто результат этой обработки используется только один раз и затем отбрасывается. Я говорю о названиях полей, которые часто повторяются и используются только для связывания данных с объектами. Их выделения можно уменьшить. Я реализовал простой кэш, используя Dictionary<Int64, string>, где ключом является первые 8 байт строки, интерпретированные как 64-битное целое число. Этот ключ может приводить к коллизиям между строками вроде "A\0\0\0\0\0\0\0" и "A", но в моем случае это не было проблемой.

if (this.rawJsonValue.Count <= 8) {   var stringCacheKey = 0UL;    // create key from rawJsonValue bytes   var rawJsonArray = this.rawJsonValue.Array;   var end = this.rawJsonValue.Offset + this.rawJsonValue.Count;   for (var offset = this.rawJsonValue.Offset; offset < end; offset++)   {     var charCode = rawJsonArray[offset];     stringCacheKey = stringCacheKey << 8 | charCode;   }   //    if (this.stringPool.TryGetValue(stringCacheKey, out var stringValue))   {     return stringValue;   }   else   {     var chars = this.ReadJsonAsChars();     return this.stringPool[stringCacheKey] = stringValue = new string(chars.Array ?? this.charBuffer, chars.Offset, chars.Count);   } }

Заключение

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

Буду рад услышать ваши мысли и опыт по подобным оптимизациям.

Код парсера после улучшений.