0xDEADBEEF

Parsování JSONu je neuvěřitelně pomalé, ale nemusí být

JSON je všude, na webu, v databázi i všude mezi těmito dvěma extrémy, jde o univerzální formát a všichni ho rádi používají. Svět by byl krásný, kdyby JSON neměl jedno ošklivé tajemství: Jeho parsování je většinou strašlivě pomalé.

Jeden malý test: Mám v souboru 20 GB JSONů, jeden na každém řádku, zkomprimováno přes zstd na ±1 GB a chci z nich vyhlodat všechny pole objektů s klíčem id, těch je několik v každém JSONu, který má formu mělkého stromu. Napsal jsem program v jazyce D, který ze stdin čte dekomprimovaná data po řádcích, z nich naparsuje JSON pomocí implementace ze standardní knihovny a pak z toho vytahá všechny id klíče.

Výsledek: Program dekomprimovaná data zpracovává rychlostí 26 MB/s.

Dobře, teď se nabízí jedna otázka: Je to hodně nebo málo?

Málo. Strašlivě, strašlivě málo.

Testoval jsem na stařičkém laptopu s tímhle procesorem (silikon ročník 2011), to jen aby bylo jasno. Zstd na něm dekomprimuje data rychlostí 1000 MB/s a nepředstavuje úzké hrdlo. D program bez problémů čte z standardního vstupu dekomprimovaná data 1000 MB/s¹ , takže si můžeme být celkem jisti, že problém spočívá ve zpracování JSONu.

Když ale budu podvádět a místo parsování JSONu budu jen hledat řetězec "id": s tím, že pak to, co po něm následuje, bude zpracováno jako číslo, můžu na prehistorickém stroji jet rychlostí 750 MB/s v jednom vlákně. Nevím jak vám, ale mě to připadá jako o něco málo víc, skoro 30× víc.

Abych sem taky vlepil nějakou ukázku kódu, tak takhle vypadá ono ohledání v jazyce D.

while (line.findSkip(`"id":`)) {
  int i = 0;
  long id = 0;
  for (; i < line.length && line[i] >= '0' && line[i] <= '9'; id = (id*10+line[i]-'0'), i++) {}
  processId(id);
  line.popFrontN(i);
  line = line.find('}'); // přeskočí na konec objektu, klíčová optimalizace
}

Nijak extra jsem nezkoumal, jestli jde o nejefektivnější variantu, vůbec jsem se nedíval na disassemblovaný kód, jestli jsou použité SIMD instrukce. Nebylo třeba, 750 MB/s je blízko mému teoretickému maximu a tak to můžu brát jako metu podle které můžeme poměřovat všechny ostatní varianty.

Pak jsem se podíval do světa PHP. Tento jazyk nemá pověst nejrychlejšího na světě, ale přesto v určitých oblastech exceluje. Jeho regexový engine je jeden z nejrychlejších vůbec. Podobně tak se to má s JSON parserem, který mi dává 64 MB/s.

Potom jsem vyzkoušel, jak je na tom Java svět.² Jackson parser má streaming API, které nikdy neprovádí plnou materializaci JSON AST a perfektně se hodí, když chci vytáhnout jen část dat. Jackson v testu jede rychlostí 109 MB/s a to hlavně proto, že v tomto případě může naprostou většinu dat přeskočit. Nemusí třeba dekódovat skoro žádné stringy a ve většině případů postačí, když najde kde aktuální token končí, což je velice efektivní.

Něco málo přes 100 MB/s na starém hardwaru možná nevypadá zas tak zle, ale máme se s tímhle spokojit? Je to všechno? Je tohle cena, kterou platíme za pohodlný serializační formát?

Naštěstí vše není ztraceno. Daniel Lemire vytvořil knihovnu simdjson, která si bere za cíl parsovat JSON maximální možnou rychlostí. Benchmarky ukazují, že v určitých situacích na Skylake CPU parsuje JSON rychlostí 2500 MB/s a navíc výsledkem není stream tokenů, ale plně navigovatelné JSON AST.

Na laptopu simdjson v mém konkrétním testu jede rychlostí 380 MB/s — 6× rychleji než PHP parser, 10× rychleji než D implementace. Stále to má daleko k teoretickým limitům prezentovaným autory knihovny, ale přesto za mě dobré.³

Testy jsem ještě zopakoval na o něco novějším hardwaru (ne o moc, je to desktopový Haswell z roku 2013) a tam to běží kolem 520 MB/s. Konečně čísla, se kterými se dá pracovat.

Tady máte naměřené rychlosti pro oba procesory v tabulce + data z testu Go knihoven.

Takže jo, JSON je fajn a když si dáte pozor, dá se parsovat s trochu rozumnou rychlostí.

1. To jen proto, že nedochází ke zbytečnému kopírování. Když data jednou zbytečně zkopíruji (byLineCopy namísto byLine), rychlost čtení spadne na 770 MB/s.
2. V Javě je obtížnější zařídit, aby nedocházelo ke zbytečnému kopírování dat. Nejjednodušší způsob, jak číst řádky, přes BufferedReader.readLine pro každý řádek alokuje nový string a dojde k pokusu konverze na interní UTF16 formát. To je v podstatě no-op, protože JSON neobsahuje žádné ne-ASCII znaky a Java tak string stejně bude reprezentovat jako ASCII string, ale pořád je to práce navíc. Čtení jede rychlostí 287 MB/s. Jackson dokáže brát i InputStream, takže se to dá zařídit (s různým množství extra úsilí v závislosti na detailech), ale není to výchozí varianta jako v D nebo C++.
3. Moje teorie je taková, že dochází k vybílení cache. V testu průměrný JSON objekt po dekompresi má ±400 kB, což je víc než L2 cache. Když se parsující proces pustí do práce, data nejsou v rychlé L2 cache, ale musí se tahat z L3 nebo rovnou z hlavní paměti. Pokud by objekty byly menší, zůstaly by v L2 cache a parsování by bylo svižnější. Nebo něco na ten způsob. Další výzkum nutný.