История изменений

Вот здесь можно почитать https://arxiv.org/pdf/1902.08318.pdf

Смотрим алгоритм.

1. Вместо обычно применяемого однократного прохождения по всем данным, авторы проходят два раза.

Результатом первого прохода является разметка элементов json формата, т.е. они получают массив указателей на начало каждого элемента.

Для этого они пользуют SIMD инструкции, чтобы обрабатывать по нескольку байт за раз. При этом они сами отмечают, что это для некоторых случаев неэффективно, но на «обычных» данных неэффективность достаточно редкая чтобы она окупилась. Формально говоря, тут все равно идет побайтовый разбор входных данных.

2. Они предполагают, что целые числа лежат в диапазоне -2^63 до 2^63.

В базах данных ID часто это uint64_t, т.е. от 0 до 2^64.

3. Вещественные числа у них лежат в диапазоне от -1 * 10^309 до +1 * 10^309.

Может и приемлимо, но обычно на 64bit системах double лежит в большем диапазоне. Про количество значащих знаков в тексте ничего не сказано.

4. В результатом их парсинга является массив 64 битных слов, в котором:

• целые числа кодируются двумя 64битными словами, первое слово специальное и сигнализирует, что за ним идет целое число в обычном формате (int64_t, как я понял).

• вещественные числа тоже кодируются двумя 64битными словами, первое слово специальное и сигнализирует, что за ним идет вещественное число (binary64 формат).

• массив в этой ленте хранится как спец. символ (первые 64bit) и индекс последнего элемента массива (64bit)

• строки хранятся в отдельном массиве, в основной ленте хранится номер (указатель) строки.

===

В целом ускорение получено за счет:

1. эвристик, которые на имеющихся данных в среднем дают прирост скорости от SIMD (с данными повезло) больше, чем потерь от SIMD (с данными не повезло).

2. некоторых предположений о входных данных

3. специальный выходной формат (парсинг идет не в дерево)

===

С т.з. алгоритма ничего нового нет.

• Есть микро модификация обычного парсинга с целью использования SIMD инструкций процессора.

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

===

В целом, на мой взгляд работа по ускорению парсинга JSON бессмыслена. В HPC никто JSON данными обмениваться на скорость не будет. Огромные объемы JSON могут получатся или из-за тупости разработчика (проф беседа, повышение квалификации, замена разработчика), или из-за исторически накопленных данных (тут скорость обработки не принципиальна), или из-за того, что данные стырены (скорость обработки не принципиальна).

Сам JSON задумывался как очень простой и читаемый формат для обмена небольшим объемом данных. Он не предназначен для пересылки мегабайтов doulbe, так его использовать это идиотизм, как и для бэкапа объемных баз данных.

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

===

И еще раз повторюсь: написать программу, которая раскроет весь потенциал процессора даже для простых задач это очень нетривиально. Поэтому почти для всего, что есть можно получить очень значительное ускорение просто поправив код (написанный на системном языке, например, на С или С++), даже не алгоритм.

Вот здесь можно почитать https://arxiv.org/pdf/1902.08318.pdf

Смотрим алгоритм.

1. Вместо обычно применяемого однократного прохождения по всем данным, авторы проходят два раза.

Результатом первого прохода является разметка элементов json формата, т.е. они получают массив указателей на начало каждого элемента.

Для этого они пользуют SIMD инструкции, чтобы обрабатывать по нескольку байт за раз. При этом они сами отмечают, что это для некоторых случаев неэффективно, но на «обычных» данных неэффективность достаточно редкая чтобы она окупилась. Формально говоря, тут все равно идет побайтовый разбор входных данных.

2. Они предполагают, что целые числа лежат в диапазоне -2^63 до 2^63.

В базах данных ID часто это uint64_t, т.е. от 0 до 2^64.

3. Вещественные числа у них лежат в диапазоне от -110^309 до +110^309.

Может и приемлимо, но обычно на 64bit системах double лежит в большем диапазоне. Про количество значащих знаков в тексте ничего не сказано.

4. В результатом их парсинга является массив 64 битных слов, в котором:

• целые числа кодируются двумя 64битными словами, первое слово специальное и сигнализирует, что за ним идет целое число в обычном формате (int64_t, как я понял).

• вещественные числа тоже кодируются двумя 64битными словами, первое слово специальное и сигнализирует, что за ним идет вещественное число (binary64 формат).

• массив в этой ленте хранится как спец. символ (первые 64bit) и индекс последнего элемента массива (64bit)

• строки хранятся в отдельном массиве, в основной ленте хранится номер (указатель) строки.

===

В целом ускорение получено за счет:

1. эвристик, которые на имеющихся данных в среднем дают прирост скорости от SIMD (с данными повезло) больше, чем потерь от SIMD (с данными не повезло).

2. некоторых предположений о входных данных

3. специальный выходной формат (парсинг идет не в дерево)

===

С т.з. алгоритма ничего нового нет.

• Есть микро модификация обычного парсинга с целью использования SIMD инструкций процессора.

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

===

В целом, на мой взгляд работа по ускорению парсинга JSON бессмыслена. В HPC никто JSON данными обмениваться на скорость не будет. Огромные объемы JSON могут получатся или из-за тупости разработчика (проф беседа, повышение квалификации, замена разработчика), или из-за исторически накопленных данных (тут скорость обработки не принципиальна), или из-за того, что данные стырены (скорость обработки не принципиальна).

Сам JSON задумывался как очень простой и читаемый формат для обмена небольшим объемом данных. Он не предназначен для пересылки мегабайтов doulbe, так его использовать это идиотизм, как и для бэкапа объемных баз данных.

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

===

И еще раз повторюсь: написать программу, которая раскроет весь потенциал процессора даже для простых задач это очень нетривиально. Поэтому почти для всего, что есть можно получить очень значительное ускорение просто поправив код (написанный на системном языке, например, на С или С++), даже не алгоритм.