?

Log in

No account? Create an account

Previous Entry | Next Entry

Допустим, в вашем проекте понадобилось найти и использовать быструю библиотеку для парсинга 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 s
YTiny!
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 :(

UPD: Связался с автором jsmn, и он починил работу с выходным массивом. Теперь по производительности парсинга jsmn минимум в пару раз обгоняет все остальные протестированные проекты.

Tags:

Comments

( 102 comments — Leave a comment )
Page 1 of 2
<<[1] [2] >>
levgem
Sep. 23rd, 2012 06:27 am (UTC)
Один файл — это удобно, жаль только, что utf8 не распаковывается.

Что выбрали? Вам был нужен SAX?
lionet
Sep. 23rd, 2012 06:30 am (UTC)
Пока не выбрали. Но пойдёт любого типа API.
ostapru
Sep. 23rd, 2012 06:39 am (UTC)
Жалко QJson в списке нет.
lionet
Sep. 23rd, 2012 06:40 am (UTC)
А что его на json.org нет?
(no subject) - fi_mihej - Sep. 23rd, 2012 10:00 am (UTC) - Expand
(no subject) - chabapok - Sep. 23rd, 2012 06:45 am (UTC) - Expand
(no subject) - ostapru - Sep. 23rd, 2012 12:46 pm (UTC) - Expand
(no subject) - chabapok - Sep. 23rd, 2012 06:50 am (UTC) - Expand
(no subject) - lionet - Sep. 23rd, 2012 07:06 am (UTC) - Expand
(no subject) - chabapok - Sep. 23rd, 2012 08:49 am (UTC) - Expand
(no subject) - fi_mihej - Sep. 23rd, 2012 10:28 am (UTC) - Expand
(no subject) - chabapok - Sep. 23rd, 2012 11:02 am (UTC) - Expand
(no subject) - fi_mihej - Sep. 23rd, 2012 11:07 am (UTC) - Expand
(no subject) - fi_mihej - Sep. 23rd, 2012 09:52 am (UTC) - Expand
(no subject) - chabapok - Sep. 23rd, 2012 11:06 am (UTC) - Expand
(no subject) - fi_mihej - Sep. 23rd, 2012 11:09 am (UTC) - Expand
archaicos
Sep. 23rd, 2012 06:47 am (UTC)
Чёрт, глядя на это, можно подумать, что правильно распарсить json нереально трудно. И да, тесты люди писать не любят. А зря.
ssart
Sep. 23rd, 2012 06:56 am (UTC)
> jsmn ... 16 MB/s, 3.3 s

То есть на большом объёме достаточно сильно тормозит по сравнению с остальными, но на мелких просто летает, выигрывая у всех с отрывом в полтора раза?
lionet
Sep. 23rd, 2012 07:09 am (UTC)
Да, только не в полтора, а в четыре раза. Похоже, потому что ему приходится обслуживать выходной массив указателей в json-данные, который должен иметь размер, пропорциональный количеству встреченных токенов. И, судя по коду, он этот массив не просто заполняет, но ещё и елозит по нему дополнительно, когда что-то нашёл, и меняет какие-то данные. Я не вчитывался пока, хотя и надо бы. Я так полагаю, имеется возможность ускорить его неимоверно, поменяв способ работы с выходным массивом.

Edited at 2012-09-23 07:21 am (UTC)
(no subject) - ssart - Sep. 23rd, 2012 07:30 am (UTC) - Expand
(no subject) - lionet - Sep. 23rd, 2012 07:40 am (UTC) - Expand
(no subject) - ssart - Sep. 23rd, 2012 08:12 am (UTC) - Expand
(no subject) - lionet - Sep. 29th, 2012 08:03 am (UTC) - Expand
(no subject) - ssart - Sep. 30th, 2012 03:44 pm (UTC) - Expand
semigr
Sep. 23rd, 2012 06:57 am (UTC)
Тесты на плохие данные не являются видом fuzz-testing'a?
lionet
Sep. 23rd, 2012 07:07 am (UTC)
Нет. Они детерминированные, и явно тестируют то, про что автор подумал. А случайные тесты тестируют то, о чём автор ещё не подумал.
(no subject) - woodroof - Jan. 14th, 2014 10:48 am (UTC) - Expand
(no subject) - lionet - Jan. 14th, 2014 08:11 pm (UTC) - Expand
(no subject) - woodroof - Jan. 15th, 2014 04:07 am (UTC) - Expand
nponeccop
Sep. 23rd, 2012 07:42 am (UTC)
http://hackage.haskell.org/package/aeson-0.6.0.2
http://hackage.haskell.org/package/yajl-enumerator
http://hackage.haskell.org/package/JsonGrammar
http://hackage.haskell.org/package/RJson
http://hackage.haskell.org/package/json
http://hackage.haskell.org/package/JSONb

Интересно было бы сравнить.. В случае yajl-enumerator было бы интересно увидеть разницу между нативной и обернутой производительностью.

Конечно, это Haskell и не для простых смертных. Но может кто-то из хаскелефилов или хаскелефобов заимплементит бенч чисто назло :)

Edited at 2012-09-23 07:45 am (UTC)
_slw
Sep. 23rd, 2012 08:45 am (UTC)
Плюс, register, который современным компиляторам совсем не сдался, они и сами не хуже умеют.

по факту -- как то херово они умеют

ps: что такое Followers?
alnsn
Sep. 23rd, 2012 09:10 am (UTC)
> по факту -- как то херово они умеют

В большинстве случаев все-таки умеют, а если нет, то надо в комментариях к коду писать.
(no subject) - _slw - Sep. 23rd, 2012 09:14 am (UTC) - Expand
(no subject) - alnsn - Sep. 23rd, 2012 09:22 am (UTC) - Expand
(no subject) - nponeccop - Sep. 23rd, 2012 09:36 am (UTC) - Expand
(no subject) - lionet - Sep. 23rd, 2012 09:11 am (UTC) - Expand
(no subject) - _slw - Sep. 23rd, 2012 09:22 am (UTC) - Expand
(no subject) - alnsn - Sep. 23rd, 2012 09:31 am (UTC) - Expand
(no subject) - _slw - Sep. 23rd, 2012 09:33 am (UTC) - Expand
(no subject) - nponeccop - Sep. 23rd, 2012 09:41 am (UTC) - Expand
(no subject) - _slw - Sep. 23rd, 2012 09:51 am (UTC) - Expand
(no subject) - alnsn - Sep. 23rd, 2012 10:14 am (UTC) - Expand
(no subject) - nponeccop - Sep. 23rd, 2012 10:18 am (UTC) - Expand
(no subject) - alnsn - Sep. 23rd, 2012 09:53 am (UTC) - Expand
(no subject) - nponeccop - Sep. 23rd, 2012 10:29 am (UTC) - Expand
(no subject) - blacklion - Sep. 23rd, 2012 10:42 am (UTC) - Expand
(no subject) - _slw - Sep. 23rd, 2012 10:55 am (UTC) - Expand
(no subject) - blacklion - Sep. 23rd, 2012 10:56 am (UTC) - Expand
(no subject) - nponeccop - Sep. 23rd, 2012 12:33 pm (UTC) - Expand
(no subject) - blacklion - Sep. 23rd, 2012 02:11 pm (UTC) - Expand
(no subject) - nponeccop - Sep. 23rd, 2012 04:21 pm (UTC) - Expand
(no subject) - blacklion - Sep. 23rd, 2012 04:53 pm (UTC) - Expand
(no subject) - _navi_ - Sep. 26th, 2012 05:31 am (UTC) - Expand
fi_mihej
Sep. 23rd, 2012 10:21 am (UTC)
Где-то пол-года назад выбирал либы для json-а. Что-бы быстрые были (ну и там по другим параметрам). Сам не тестировал, но смотрел на описания / готовые бенчмарки из сети.

Чисто по скорости выбрал:
- rapidjson
- libjson

Все они есть на json.ork ("C++")

Может что и тебе подойдет.
alexott
Sep. 26th, 2012 09:36 am (UTC)
rapidjson - ужас летящий на крыльях ночи, может он и быстрый, но чтобы его использовать надо постоянно помнить про move semantic и т.п., что не добавляет простоты. я пока взял jsoncpp, у которого либеральная лицензия и код можно нормально использовать
(no subject) - fi_mihej - Sep. 27th, 2012 11:15 pm (UTC) - Expand
(no subject) - woodroof - Jan. 14th, 2014 10:50 am (UTC) - Expand
(no subject) - chabapok - Sep. 29th, 2012 09:25 pm (UTC) - Expand
(no subject) - lionet - Sep. 30th, 2012 06:58 am (UTC) - Expand
(no subject) - fi_mihej - Sep. 30th, 2012 11:36 am (UTC) - Expand
macrop
Sep. 23rd, 2012 02:49 pm (UTC)
Я просто самодёльный писал. Потом с ним возиться надоело, поставил чужой. А выбирал просто самый удобный. Давно пользуюсь, жаль только опознать его уже не смогу:
http://narod.ru/disk/61381699001.0fdc6124df3d5fff9a7b0d06cff9a5c2/json.zip.html
krasin
Sep. 24th, 2012 01:32 am (UTC)
Возможно, опознать будет проще, если код будет лежать не в архиве на narod.ru, а на github или любом другом хостинге кода.
(no subject) - macrop - Sep. 24th, 2012 06:39 am (UTC) - Expand
(no subject) - macrop - Sep. 24th, 2012 07:34 am (UTC) - Expand
levgem
Sep. 25th, 2012 07:19 am (UTC)
а тебе это потом куда надо? в С обрабатывать или в эрланг засовывать?
Ведь от этого может зависеть требуемая модель обработки.
lionet
Sep. 25th, 2012 07:20 am (UTC)
В C обрабатывать.
deathbaba
Sep. 25th, 2012 11:41 am (UTC)
Используем у себя jansson - работает отлично. Даже отписывали раньше багфикс, ребята его в новую версию оперативно вставили.
lionet
Sep. 25th, 2012 11:42 am (UTC)
Thanks for feedback!
(Deleted comment)
lionet
Sep. 25th, 2012 08:53 pm (UTC)
> Не поняла связи качества парсера и лицензии.

Не люблю [L]GPL :)

См. http://lionet.livejournal.com/109094.html
familom
Sep. 29th, 2012 02:53 pm (UTC)
Используем YAJL. Жаль, автор на нее подзабил.
levgem
Oct. 6th, 2012 12:07 pm (UTC)
Есть такие вопросы:

1) имеет ли смысл имплементить DOM читалку через SAX или имеет смысл сразу парсить в DOM?
2) как оно по сравнению с mochijson2? Я поглядел, мне кажется что в mochijson2 много промежуточного парсинга типа переложить из одного представления в другое и потом обратно, а так же недостаточно используется вложенность стека
3) насколько нормально использовать вложенность стека в парсере JSON?
lionet
Oct. 7th, 2012 11:24 pm (UTC)
1. Depends on your needs. Если ты, например, считаешь CRC (ну а вдруг?), то зачем тебе дерево?
2. Оно эрланг, это заведомо медленнее примерно на порядок величины. Если сравнивать с ним, тогда нужно сравнивать со всеми другими языками, указанными на json.org. Начав с C++.
3. Поясни, что такое "использовать вложенность стека"?
(no subject) - levgem - Oct. 8th, 2012 02:34 am (UTC) - Expand
(no subject) - lionet - Oct. 8th, 2012 02:39 am (UTC) - Expand
(no subject) - chabapok - Oct. 16th, 2012 02:25 pm (UTC) - Expand
(no subject) - lionet - Oct. 16th, 2012 03:14 pm (UTC) - Expand
lusever
Oct. 18th, 2012 05:00 pm (UTC)
Для питона есть быстрый ujson. По их тестам он быстрее yajl.
lionet
Oct. 18th, 2012 05:15 pm (UTC)
Это не тот yajl.
Page 1 of 2
<<[1] [2] >>
( 102 comments — Leave a comment )