Как я улучшил производительность JSON-парсера в два раза
Введение
Во время разработки игр объем данных, обрабатываемых игрой, увеличивается. Художники создают новые ресурсы, программисты пишут код, а геймдизайнеры добавляют больше конфигураций и настроек в игру. Когда размер этих конфигураций превышает десятки мегабайт, производительность даже самых тривиальных компонентов, таких как JSON-парсер конфигураций, становится критичной. В этой статье я поделюсь своим опытом оптимизации парсеров для нашего инструмента управления игровыми данными под названием Charon.
О оптимизации кода
Первым шагом в любой оптимизации кода является профилирование. Любые предположения о том, что нуждается в оптимизации без объективных данных профилирования, скорее всего, будут неверными. Многие, включая меня, попадали в ловушку, думая: «Я лучше знаю, как это будет выполняться». Даже с профилировщиком предположения о производительности конкретных частей вашей программы действительны только для вашего оборудования и версии ОС. Однако это лучше, чем вносить изменения вслепую.
Переход от парсинга char[] к byte[]
При написании парсеров для текстовых форматов данных или протоколов есть два способа обработки входных данных: обращаться к ним как к строкам или как к числам. JSON — это текстовый формат, поддерживающий строки в кодировке UTF-8, но все значимые для разметки символы находятся в диапазоне ASCII. Это означает, что его можно парсить без декодирования символов из byte в char, но всё еще надо детектить и пропускать многобайтовые символы. Предыдущая реализация токенизатора была такой:
Чтение байтов из потока в буфер
byte[].Декодирование этого буфера
byte[]в другой буферchar[].Токенизация этого буфера
char[].Интерпретация этих токенов.
Идея оптимизации заключалась в том, чтобы токенизировать буфер байтов напрямую и декодировать только строковые токены:
Чтение байтов из потока в буфер
byte[].Токенизация этого буфера
byte[].Декодирование только строковых токенов.
Интерпретация этих токенов.
Это потребовало значительного изменения токенизатора и само по себе обеспечило минимальное улучшение производительности. Однако этот подход позволил реализовать несколько других оптимизаций, таких как кэширование коротких строк и использование парсеров чисел сразу из byte[], о которых будет рассказано ниже.
Когда у блока кода миллионы вызовов: самые незначительные изменения влияют на производительность
Типичный парсер данных состоит из токенизатора и лексера. Токенизатор обрабатывает каждый байт/символ в потоке данных и разделяет поток данных на токены, в то время как лексер придает этим токенам контекст (этот токен — число, этот токен — строка и т.д.). Код в цикле токенизации вызывается наиболее часто, и даже небольшие оптимизации могут значительно повысить производительность.
тут в NextLexeme () крутится каждый байт из входных данных
Замена цепочек 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 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 для преобразования байтов в числа из массивов байтов
.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, где ключом является первые 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. Эти изменения привели к существенному приросту производительности, демонстрируя влияние даже небольших оптимизаций в высокочастотных кодовых путях.
Буду рад услышать ваши мысли и опыт по подобным оптимизациям.
