Допустим, в вашем проекте понадобилось найти и использовать быструю библиотеку для парсинга JSON. Смотрим на json.org, там есть целый список на выбор.

• JSON_checker
• YAJL
• js0n
• LibU
• json-c
• json-parser
• jsonsl
• WJElement
• M's JSON parser
• cJSON
• Jansson
• jsmn
• cson

Что выбрать? Давайте попробуем отсеять совсем уж шлак, совершив поверхностное сравнение качества исходного кода парсеров.

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

Сводная табличка

Project	License	API	UTF-8	Neg. tests	Followers	Benchmark	Finalist?	Note
yajl	ISC	SAX	Y	Y	815/120	249 MB/s, 5.1 s	Y	Large code base.
jsonsl	MIT	SAX	N	Y	10/2	246 MB/s, 5.6 s	Y	Tiny source code base.
Jansson	MIT	DOM	Y	Y	234/59	25 MB/s, 52 s	Y
cson	BSD'	DOM	Y	Y	n/a	30 MB/s, 44 s	Y
json-c	BSD	DOM	Y	N	103/45	38 MB/s, 29.7 s	Y
json-parser	BSD	DOM	N	Y	276/24	49 MB/s, 12.4 s	Y	Tiny! A single source file.
jsmn	MIT	custom	N	Y	65/4	16 MB/s, 3.3 s 482 MB/s, 2.3 s	Y	Tiny!
js0n	pub.	custom	N	N	67/10	n/a	N
LibU	BSD			N	18/3	n/a	N
WJElement	LGPL			N	7/2	n/a	N
M's JSON parser	LGPL			N	n/a	n/a	N
cJSON	BSD			N	n/a	n/a	N

Примечания

• Колонка UTF-8 обозначает, происходит ли преобразование эскейпинг \X, в том числе \uXXXX кодов в прямой UTF-8.
  
• Обратите внимание, что никто с LGPL-лицензией не прошёл сквозь фильтр.
  
• SAX-парсеры дают 250+ мегабайт в секунду, DOM-парсеры дают в десяток раз меньше.
  
• jsmn довольно аномальный — он быстрый, если всё помещается в кэш, но медленный на длинных дистанциях. Похоже, это связано со способом работы с возвращаемым значением — деревом, закодированным в массив. Подробнее не проверял.
  
• Ни один проект не использует fuzz-testing :(

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