Comparison and microbenchmark of #JSON parsers
Допустим, в вашем проекте понадобилось найти и использовать быструю библиотеку для парсинга JSON. Смотрим на json.org, там есть целый список на выбор.
Что выбрать? Давайте попробуем отсеять совсем уж шлак, совершив поверхностное сравнение качества исходного кода парсеров.
JSON_checker
http://www.JSON.org/JSON_checker/
Сразу не подходит, это не парсер.
yajl
http://lloyd.github.com/yajl/ (ISC)
Код разбит на лексер и парсер - вери гуд. Парсер и лексер написан руками - good enough.
Тесты парсинга нормальных данных и мусора есть. Fuzz-тестов нет.
Проходит в финал.
js0n
https://github.com/quartzjer/js0n (public domain)
Недостаточно высокоуровневый API, gcc-специфичный код (label pointers). Нет стриминг-режима. Реально минимально возможная, оставаясь практичной, имплементация. Но слишком низкоуровневая.
Тестов нет.
Проезжаем мимо. Для обычных людей не подходит.
LibU
https://github.com/koanlogic/libu/blob/master/srcs/toolbox/json.c (BSD)
Вообще LibU - это библиотека для всего сразу: сетевых взаимодействий, URI-парсинга, манипуляций со строками, логирования и т. д. И json.c там в качестве одного из множества компонентов.
Конкретно особых проблем с json.c не нахожу.
Но тесты есть только на правильные значения. Нот гуд.
Вкупе с тем, что за json.c тянется целый грузовик дополнительного кода, LibU финал не проходит.
json-c
https://github.com/json-c/json-c (BSD)
(На json.org используется ссылка на jehiah/json-c, но этот форк менялся позже, чем json-c/json-c).
Код выглядит неплохо.
Тесты есть, тестов на плохие данные нет. Fuzz-тестов нет.
Проходит в финал.
json-parser
https://github.com/udp/json-parser (BSD)
const static int
flag_next = 1, flag_reproc = 2, flag_need_comma = 4,
flag_seek_value = 8, flag_exponent = 16,
flag_got_exponent_sign = 32, flag_escaped = 64, flag_string = 128,
flag_need_colon = 256, flag_done = 512;
Вообще-то идиоматично использовать enum со списком типа
enum ... {
STATE_EXPONENT = (1 << 4),
STATE_COLON = (1 << 5),
}
ну да ладно.
В остальном, вроде нормально. Педантичненько, тесты есть, в том числе и тесты на плохие данные. Fuzz-тестов нет. API ждёт завершённую нулём строку.
Претендент выходит в финал.
jsonsl
https://github.com/mnunberg/jsonsl (MIT)
for (; nbytes; nbytes--, jsn->pos++, c++) {
register jsonsl_type_t state_type;
Эээ. Какая-то странность у автора в голове, честно говоря. Меняем одновременно и указатель, и длину. Хотя могли бы менять только указатель (и проверять start < end, где нужно), тем более что в других местах автор этот подход умеет использовать. Плюс, register, который современным компиляторам совсем не сдался, они и сами не хуже умеют.
Кроме того, небрежно обращается с буфером:
/* Temporarily null-terminate the characters */
origc = *(c+3);
*(c+3) = '\0';
pctval = strtoul(c+1, NULL, 16);
*(c+3) = origc;
На практике ок, но некрасиво.
С другой стороны, видно, что автор тщательно продумывал состояния и вообще довольно педантично подошёл к вопросу.
Тесты есть, в том числе и тесты на плохие данные. Fuzz-тестов нет.
Претендент выходит в финал.
WJElement
https://github.com/netmail-open/wjelement (LGPL)
Библиотека ориентирована в основном на манипуляцию с JSON, а поэтому парсинг у неё какой-то странный. Куча strlen() на ровном месте. Куча каких-то предположений. Оппортунизм.
Вот как мы парсим всякую фигню:
case '"':
/* We have actually reached the end of the string */
WJRDocAssert(doc);
doc->read[i] = '\0';
doc->read += i + 1;
WJRDocAssert(doc);
for (; doc->read < doc->write && *doc->read && *doc->read != ':'
&& *doc->read != ',' && *doc->read != ']' && *doc->read != '}'
; doc->read++);
Вот как мы елозим по данным с квадратической сложностью:
case '\\': {
unsigned int move = 0;
if (strlen(doc->read + i + 1) < (toupper(doc->read[i + 1]) == 'U'
? 5 : (toupper(doc->read[i + 1]) == 'X' ? 3 : 1))) {
/* Make sure we have enough characters */
WJRFillBuffer(doc);
if (strlen(doc->read + i + 1) < (toupper(doc->read[i + 1]) == 'U'
? 5 : (toupper(doc->read[i + 1]) == 'X' ? 3 : 1))) {
Тесты есть, тестов на плохие данные нет, fuzz-тестов нет.
Претендент выбывает из соревнований.
M's JSON parser
http://sourceforge.net/projects/mjson/ (LGPL)
Использует re2c для автоматизации построения парсера. Это очень классно и инженерно.
В остальном код дырявый и неидиоматичный в самых простых местах. Например, вот как происходит аллокация строки:
length = strlen (text);
t->text = (char *) malloc (sizeof (char) * (length + 1));
if (t->text == NULL) {
free (t);
return NULL;
}
strcpy (t->text, text);
sizeof(char)? SRSLY? Стандартов не читаем. По стандарту sizeof(char) всегда равен единице. Кроме того, использование strcpy, когда нам известна уже длина? Ну оке-ей, допустим чел делает всё для высшей цели "очевидной корректности", а не для скорости. Но тогда почему бы не идти дальше и использовать calloc вместо повсеместно использующегося malloc? Выражаем надежду на то, что нигде не забыли проинициализировать поле? В общем, мудрит автор, совершенно не по делу, и не в тех местах, где нужно.
А вот как происходит обработка ошибок памяти. Ну ты или делай assert, либо деаллоцируй, как мужчина, а не вот так вот как здесь.
str = json_new_text (text);
if (str == NULL)
return NULL;
lab = json_new_label (label);
if (lab == NULL) {
/*TODO deallocate memory from the json_text_t object */
return NULL;
}
Тесты есть. Тестов, гоняющих код на ошибочных JSON нет. Fuzz-тестов нет.
Претендент выбывает из соревнований.
cJSON
http://sourceforge.net/projects/cjson/ (BSD)
Так, смотрим на парсинг.
while (*ptr!='\"' && *ptr) {
if (*ptr!='\\') *ptr2++=*ptr++;
else {
ptr++;
switch (*ptr) {
case...
default: *ptr2++=*ptr; break
}
ptr++;
}
}
Вау. Встретили '\0', и погнали дальше, как ни в чём не бывало. Молодцы!
Ну и чуть раньше. Как вычисляем количество памяти для строки? Ну конечно же, двумя проходами, и неверно:
while (*ptr!='\"' && *ptr && ++len)
if (*ptr++ == '\\') ptr++; /* Skip escaped quotes. */
А дальше код, который транслирует строку типа «\x» -> в неё же саму, если только x это не один из [bfnrtu]. Что это даёт? То, что если вся строка состоит их \x, мы будем писать за пределы выделенного буфера. Молодцы в квадрате.
Раунд-трип в тестах есть, тестов на плохие данные нет, fuzz-тестов нет.
В списке открытых багов сидит buffer overflow.
Претендент выбывает из соревнований.
jsmn
http://zserge.bitbucket.org/jsmn.html (MIT)
Парсер для эмбедщины и других сред с ограниченными ресурсами.
Парсинг использует обычный подход с ручной стейт-машиной. Аллокаций памяти ноль, потому что всё предварительно должно быть зааллоцировано в сплошном куске памяти при вызове парсера. Это для моих целей хорошо. Парсер потоковый, то есть его можно рестартовать, если данных не хватило.
Парсер ожидает, что данные в буфере для парсинга будут ASCIIZ, то есть 0-терминированными. Немного неприятно, но тоже себе идиома.
Почему неприятно? Потому что не всегда ноль доступен (например, как парсить JSONP, даже если известны границы JSON?), а поставить '\0' в данный извне буфер идиоматически можно только с его полной реаллокацией.
Тесты делаются как для хороших данных, так и для плохих, неполных. Fuzz-тестов нет.
Претендент выходит в финал.
Jansson
http://www.digip.org/jansson/ (MIT)
Большое количество тестов, как позитивных, так и на парсинг левых данных.
Смотрим на код парсинга.
while(*p != '"') {
if(*p == '\\') {
p++;
if(*p == 'u') {
...
} else {
switch(*p) {
case ...
default: assert(0)
}
}
Молодцы, что тут сказать! Но самом деле, там двухпроходная логика не допускает, чтобы код выпал в assert() в этом месте на втором проходе. Но это совершенно не очевидно из кода, и приходится верить на слово; а раз так, это не очень хороший дизайн.
Оставляем в финалистах.
cson
http://fossil.wanderinghorse.net/repos/cson/index.cgi/index (BSD')
Лексический анализ и парсинг в одной функции. О-ок. Цифры вместо констант в case. О-ок.
Тесты есть, в том числе на левые данные.
for (i = 12; i >= 0; i -= 4, ++p) {
unsigned x = *p;
if (x >= 'a') {
x -= ('a' - 10);
} else if (x >= 'A') {
x -= ('A' - 10);
} else {
x &= ~0x30u;
}
assert(x < 16);
uc |= x << i;
}
Вот ведь любители ассертов в парсинге внешних данных!
Но я проверил рандомными тестами, и дебагом, и получается, что в этот assert() мы не попадаем никогда по логике, которая неявно закодированна в стейт-машине, совершенно в другом месте. Брр...
На парсинг каждого символа происходит какое-то дикое число действий.
Аккуратно, с недоверием, но оставляем кандидата в обойме.
Бенчмарк
Я набросал бенчмарк, который:
1. Сотню раз прогоняет восьмимегабайтный файл через парсер, и вычисляет скорость в мегабайтах в секунду (MB/s). Соответствующая цифра записывается в табличку. Чем больше эта цифра, тем лучше.
2. Даёт парсеру трёхкилобайтный JSON-файл.
2.1. Перед парсингом данные размещаются так, чтобы сразу за завершающим нулём шла mprotect(2)'ed область памяти - это дополнительный тест на buffer overrun парсера.
2.2 Последний значимый байт файла изменяется по всей области определения.
2.3. Всего получается, что парсер вызывается около полумиллиона раз. Результирующий тайминг записывается в соответствующий столбец в табличке. Чем меньше эта цифра, тем лучше.
Код бенчмарк-библиотеки доступен на http://github.com/vlm/vlm-json-test
Сводная табличка
ProjectLicenseAPIUTF-8Neg. testsFollowersBenchmarkFinalist?Note
yajlISCSAXYY815/120249 MB/s, 5.1 sYLarge code base.
jsonslMITSAXNY10/2246 MB/s, 5.6 sYTiny source code base.
JanssonMITDOMYY234/5925 MB/s, 52 sY
csonBSD'DOMYYn/a30 MB/s, 44 sY
json-cBSDDOMYN103/4538 MB/s, 29.7 sY
json-parserBSDDOMNY276/2449 MB/s, 12.4 sYTiny! A single source file.
jsmnMITcustomNY65/416 MB/s, 3.3 s
482 MB/s, 2.3 sYTiny!
js0npub.customNN67/10n/aN
LibUBSDN18/3n/aN
WJElementLGPLN7/2n/aN
M's JSON parserLGPLNn/an/aN
cJSONBSDNn/an/aN
Примечания
Что выбрать? Давайте попробуем отсеять совсем уж шлак, совершив поверхностное сравнение качества исходного кода парсеров.
JSON_checker
http://www.JSON.org/JSON_checker/
Сразу не подходит, это не парсер.
yajl
http://lloyd.github.com/yajl/ (ISC)
Код разбит на лексер и парсер - вери гуд. Парсер и лексер написан руками - good enough.
Тесты парсинга нормальных данных и мусора есть. Fuzz-тестов нет.
Проходит в финал.
js0n
https://github.com/quartzjer/js0n (public domain)
Недостаточно высокоуровневый API, gcc-специфичный код (label pointers). Нет стриминг-режима. Реально минимально возможная, оставаясь практичной, имплементация. Но слишком низкоуровневая.
Тестов нет.
Проезжаем мимо. Для обычных людей не подходит.
LibU
https://github.com/koanlogic/libu/blob/master/srcs/toolbox/json.c (BSD)
Вообще LibU - это библиотека для всего сразу: сетевых взаимодействий, URI-парсинга, манипуляций со строками, логирования и т. д. И json.c там в качестве одного из множества компонентов.
Конкретно особых проблем с json.c не нахожу.
Но тесты есть только на правильные значения. Нот гуд.
Вкупе с тем, что за json.c тянется целый грузовик дополнительного кода, LibU финал не проходит.
json-c
https://github.com/json-c/json-c (BSD)
(На json.org используется ссылка на jehiah/json-c, но этот форк менялся позже, чем json-c/json-c).
Код выглядит неплохо.
Тесты есть, тестов на плохие данные нет. Fuzz-тестов нет.
Проходит в финал.
json-parser
https://github.com/udp/json-parser (BSD)
const static int
flag_next = 1, flag_reproc = 2, flag_need_comma = 4,
flag_seek_value = 8, flag_exponent = 16,
flag_got_exponent_sign = 32, flag_escaped = 64, flag_string = 128,
flag_need_colon = 256, flag_done = 512;
Вообще-то идиоматично использовать enum со списком типа
enum ... {
STATE_EXPONENT = (1 << 4),
STATE_COLON = (1 << 5),
}
ну да ладно.
В остальном, вроде нормально. Педантичненько, тесты есть, в том числе и тесты на плохие данные. Fuzz-тестов нет. API ждёт завершённую нулём строку.
Претендент выходит в финал.
jsonsl
https://github.com/mnunberg/jsonsl (MIT)
for (; nbytes; nbytes--, jsn->pos++, c++) {
register jsonsl_type_t state_type;
Эээ. Какая-то странность у автора в голове, честно говоря. Меняем одновременно и указатель, и длину. Хотя могли бы менять только указатель (и проверять start < end, где нужно), тем более что в других местах автор этот подход умеет использовать. Плюс, register, который современным компиляторам совсем не сдался, они и сами не хуже умеют.
Кроме того, небрежно обращается с буфером:
/* Temporarily null-terminate the characters */
origc = *(c+3);
*(c+3) = '\0';
pctval = strtoul(c+1, NULL, 16);
*(c+3) = origc;
На практике ок, но некрасиво.
С другой стороны, видно, что автор тщательно продумывал состояния и вообще довольно педантично подошёл к вопросу.
Тесты есть, в том числе и тесты на плохие данные. Fuzz-тестов нет.
Претендент выходит в финал.
WJElement
https://github.com/netmail-open/wjelement (LGPL)
Библиотека ориентирована в основном на манипуляцию с JSON, а поэтому парсинг у неё какой-то странный. Куча strlen() на ровном месте. Куча каких-то предположений. Оппортунизм.
Вот как мы парсим всякую фигню:
case '"':
/* We have actually reached the end of the string */
WJRDocAssert(doc);
doc->read[i] = '\0';
doc->read += i + 1;
WJRDocAssert(doc);
for (; doc->read < doc->write && *doc->read && *doc->read != ':'
&& *doc->read != ',' && *doc->read != ']' && *doc->read != '}'
; doc->read++);
Вот как мы елозим по данным с квадратической сложностью:
case '\\': {
unsigned int move = 0;
if (strlen(doc->read + i + 1) < (toupper(doc->read[i + 1]) == 'U'
? 5 : (toupper(doc->read[i + 1]) == 'X' ? 3 : 1))) {
/* Make sure we have enough characters */
WJRFillBuffer(doc);
if (strlen(doc->read + i + 1) < (toupper(doc->read[i + 1]) == 'U'
? 5 : (toupper(doc->read[i + 1]) == 'X' ? 3 : 1))) {
Тесты есть, тестов на плохие данные нет, fuzz-тестов нет.
Претендент выбывает из соревнований.
M's JSON parser
http://sourceforge.net/projects/mjson/ (LGPL)
Использует re2c для автоматизации построения парсера. Это очень классно и инженерно.
В остальном код дырявый и неидиоматичный в самых простых местах. Например, вот как происходит аллокация строки:
length = strlen (text);
t->text = (char *) malloc (sizeof (char) * (length + 1));
if (t->text == NULL) {
free (t);
return NULL;
}
strcpy (t->text, text);
sizeof(char)? SRSLY? Стандартов не читаем. По стандарту sizeof(char) всегда равен единице. Кроме того, использование strcpy, когда нам известна уже длина? Ну оке-ей, допустим чел делает всё для высшей цели "очевидной корректности", а не для скорости. Но тогда почему бы не идти дальше и использовать calloc вместо повсеместно использующегося malloc? Выражаем надежду на то, что нигде не забыли проинициализировать поле? В общем, мудрит автор, совершенно не по делу, и не в тех местах, где нужно.
А вот как происходит обработка ошибок памяти. Ну ты или делай assert, либо деаллоцируй, как мужчина, а не вот так вот как здесь.
str = json_new_text (text);
if (str == NULL)
return NULL;
lab = json_new_label (label);
if (lab == NULL) {
/*TODO deallocate memory from the json_text_t object */
return NULL;
}
Тесты есть. Тестов, гоняющих код на ошибочных JSON нет. Fuzz-тестов нет.
Претендент выбывает из соревнований.
cJSON
http://sourceforge.net/projects/cjson/ (BSD)
Так, смотрим на парсинг.
while (*ptr!='\"' && *ptr) {
if (*ptr!='\\') *ptr2++=*ptr++;
else {
ptr++;
switch (*ptr) {
case...
default: *ptr2++=*ptr; break
}
ptr++;
}
}
Вау. Встретили '\0', и погнали дальше, как ни в чём не бывало. Молодцы!
Ну и чуть раньше. Как вычисляем количество памяти для строки? Ну конечно же, двумя проходами, и неверно:
while (*ptr!='\"' && *ptr && ++len)
if (*ptr++ == '\\') ptr++; /* Skip escaped quotes. */
А дальше код, который транслирует строку типа «\x» -> в неё же саму, если только x это не один из [bfnrtu]. Что это даёт? То, что если вся строка состоит их \x, мы будем писать за пределы выделенного буфера. Молодцы в квадрате.
Раунд-трип в тестах есть, тестов на плохие данные нет, fuzz-тестов нет.
В списке открытых багов сидит buffer overflow.
Претендент выбывает из соревнований.
jsmn
http://zserge.bitbucket.org/jsmn.html (MIT)
Парсер для эмбедщины и других сред с ограниченными ресурсами.
Парсинг использует обычный подход с ручной стейт-машиной. Аллокаций памяти ноль, потому что всё предварительно должно быть зааллоцировано в сплошном куске памяти при вызове парсера. Это для моих целей хорошо. Парсер потоковый, то есть его можно рестартовать, если данных не хватило.
Парсер ожидает, что данные в буфере для парсинга будут ASCIIZ, то есть 0-терминированными. Немного неприятно, но тоже себе идиома.
Почему неприятно? Потому что не всегда ноль доступен (например, как парсить JSONP, даже если известны границы JSON?), а поставить '\0' в данный извне буфер идиоматически можно только с его полной реаллокацией.
Тесты делаются как для хороших данных, так и для плохих, неполных. Fuzz-тестов нет.
Претендент выходит в финал.
Jansson
http://www.digip.org/jansson/ (MIT)
Большое количество тестов, как позитивных, так и на парсинг левых данных.
Смотрим на код парсинга.
while(*p != '"') {
if(*p == '\\') {
p++;
if(*p == 'u') {
...
} else {
switch(*p) {
case ...
default: assert(0)
}
}
Молодцы, что тут сказать! Но самом деле, там двухпроходная логика не допускает, чтобы код выпал в assert() в этом месте на втором проходе. Но это совершенно не очевидно из кода, и приходится верить на слово; а раз так, это не очень хороший дизайн.
Оставляем в финалистах.
cson
http://fossil.wanderinghorse.net/repos/cson/index.cgi/index (BSD')
Лексический анализ и парсинг в одной функции. О-ок. Цифры вместо констант в case. О-ок.
Тесты есть, в том числе на левые данные.
for (i = 12; i >= 0; i -= 4, ++p) {
unsigned x = *p;
if (x >= 'a') {
x -= ('a' - 10);
} else if (x >= 'A') {
x -= ('A' - 10);
} else {
x &= ~0x30u;
}
assert(x < 16);
uc |= x << i;
}
Вот ведь любители ассертов в парсинге внешних данных!
Но я проверил рандомными тестами, и дебагом, и получается, что в этот assert() мы не попадаем никогда по логике, которая неявно закодированна в стейт-машине, совершенно в другом месте. Брр...
На парсинг каждого символа происходит какое-то дикое число действий.
Аккуратно, с недоверием, но оставляем кандидата в обойме.
Бенчмарк
Я набросал бенчмарк, который:
1. Сотню раз прогоняет восьмимегабайтный файл через парсер, и вычисляет скорость в мегабайтах в секунду (MB/s). Соответствующая цифра записывается в табличку. Чем больше эта цифра, тем лучше.
2. Даёт парсеру трёхкилобайтный JSON-файл.
2.1. Перед парсингом данные размещаются так, чтобы сразу за завершающим нулём шла mprotect(2)'ed область памяти - это дополнительный тест на buffer overrun парсера.
2.2 Последний значимый байт файла изменяется по всей области определения.
2.3. Всего получается, что парсер вызывается около полумиллиона раз. Результирующий тайминг записывается в соответствующий столбец в табличке. Чем меньше эта цифра, тем лучше.
Код бенчмарк-библиотеки доступен на http://github.com/vlm/vlm-json-test
Сводная табличка
ProjectLicenseAPIUTF-8Neg. testsFollowersBenchmarkFinalist?Note
yajlISCSAXYY815/120249 MB/s, 5.1 sYLarge code base.
jsonslMITSAXNY10/2246 MB/s, 5.6 sYTiny source code base.
JanssonMITDOMYY234/5925 MB/s, 52 sY
csonBSD'DOMYYn/a30 MB/s, 44 sY
json-cBSDDOMYN103/4538 MB/s, 29.7 sY
json-parserBSDDOMNY276/2449 MB/s, 12.4 sYTiny! A single source file.
jsmnMITcustomNY65/416 MB/s, 3.3 s
482 MB/s, 2.3 sYTiny!
js0npub.customNN67/10n/aN
LibUBSDN18/3n/aN
WJElementLGPLN7/2n/aN
M's JSON parserLGPLNn/an/aN
cJSONBSDNn/an/aN
Примечания
- Колонка UTF-8 обозначает, происходит ли преобразование эскейпинг \X, в том числе \uXXXX кодов в прямой UTF-8.
- Обратите внимание, что никто с LGPL-лицензией не прошёл сквозь фильтр.
- SAX-парсеры дают 250+ мегабайт в секунду, DOM-парсеры дают в десяток раз меньше.
- jsmn довольно аномальный - он быстрый, если всё помещается в кэш, но медленный на длинных дистанциях. Похоже, это связано со способом работы с возвращаемым значением - деревом, закодированным в массив. Подробнее не проверял.
- Ни один проект не использует fuzz-testing :(