Введение

Во время разработки игр объем данных, обрабатываемых игрой, увеличивается. Художники создают новые ресурсы, программисты пишут код, а геймдизайнеры добавляют больше конфигураций и настроек в игру. Когда размер этих конфигураций превышает десятки мегабайт, производительность даже самых тривиальных компонентов, таких как 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. Эти изменения привели к существенному приросту производительности, демонстрируя влияние даже небольших оптимизаций в высокочастотных кодовых путях.

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

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