SIMDProto
Я убил приличное количество времени думая о проблемах с памятью в последнее время. Одна из них -- можно ли как-то быстрее парсить protobufs. Хочу здесь поделиться, с какими проблемами я столкнулся, и почему это сложнее, чем кажется.
Самая главная проблема, что практически невозможно парсить varints быстро. Попробую дать интуицию:
В JSON вы можете найти символы ", {, }, [, ], : достаточно быстро, они будут в какой-то степени разделителями, показывая где начало и где конец поля. После этого вам надо найти все позиции и на каждый найденный символ найти второй соответствующий, например, на открывающую скобку -- закрывающую. Это зависимость (цепочка) длины 1, остальные байты легко пропускаются, итерации по битам делать не надо.
У протобуфов числа устроены таким образом, что мы должны смотреть на старший бит байта, чтобы понять, какой следующий -- что это продолжение числа или начало нового поля? В итоге, чтобы понять разделители и их индексы, нужно решать достаточно длинные цепочки, и в итоге парсер прыгает как-то по одному-двум байтам. Если хочется выйти из лимита, как 1 cycle на байт для чисел, тегов и тд, нужно уметь обрабатывать varints пачками, притом пачками в том смысле, чтобы varint спокойно могли находиться между других полей, в том числе широкие вектора могут состоять из такого ужаса:
1. [строка][tag][varint][tag][size][строка]
2. [varint][tag][varint][tag][varint]
И так далее. В итоге если вы посчитаете огромное количество различных конфигураций, будет не так красиво и в итоге нужна ветвистая логика для всех случаев, сложные инструкции как tzcnt, чтобы считать пропускные биты и итерации по битам с 2 cycle на байт.
Тем не менее у нас есть кандидаты для парсинга varint с помощью SIMD.
Любые попытки написать даже простой код заканчиваются неудачно. В итоге сейчас SIMDJSON быстрее и популярнее протобуфов. Даже по скорости на 1 бит информации (JSON обычно весит больше, чем прото).
Менять формат абсолютно другая история. Но пробить гигабайты в секунду у протобуфов становится какой-то непосильной задачей, которую я скоро перестану решать.
Я убил приличное количество времени думая о проблемах с памятью в последнее время. Одна из них -- можно ли как-то быстрее парсить protobufs. Хочу здесь поделиться, с какими проблемами я столкнулся, и почему это сложнее, чем кажется.
Самая главная проблема, что практически невозможно парсить varints быстро. Попробую дать интуицию:
В JSON вы можете найти символы ", {, }, [, ], : достаточно быстро, они будут в какой-то степени разделителями, показывая где начало и где конец поля. После этого вам надо найти все позиции и на каждый найденный символ найти второй соответствующий, например, на открывающую скобку -- закрывающую. Это зависимость (цепочка) длины 1, остальные байты легко пропускаются, итерации по битам делать не надо.
У протобуфов числа устроены таким образом, что мы должны смотреть на старший бит байта, чтобы понять, какой следующий -- что это продолжение числа или начало нового поля? В итоге, чтобы понять разделители и их индексы, нужно решать достаточно длинные цепочки, и в итоге парсер прыгает как-то по одному-двум байтам. Если хочется выйти из лимита, как 1 cycle на байт для чисел, тегов и тд, нужно уметь обрабатывать varints пачками, притом пачками в том смысле, чтобы varint спокойно могли находиться между других полей, в том числе широкие вектора могут состоять из такого ужаса:
1. [строка][tag][varint][tag][size][строка]
2. [varint][tag][varint][tag][varint]
И так далее. В итоге если вы посчитаете огромное количество различных конфигураций, будет не так красиво и в итоге нужна ветвистая логика для всех случаев, сложные инструкции как tzcnt, чтобы считать пропускные биты и итерации по битам с 2 cycle на байт.
Тем не менее у нас есть кандидаты для парсинга varint с помощью SIMD.
Любые попытки написать даже простой код заканчиваются неудачно. В итоге сейчас SIMDJSON быстрее и популярнее протобуфов. Даже по скорости на 1 бит информации (JSON обычно весит больше, чем прото).
Менять формат абсолютно другая история. Но пробить гигабайты в секунду у протобуфов становится какой-то непосильной задачей, которую я скоро перестану решать.