0xDEADBEEF

[RSS]
««« »»»

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

25. 4. 2020

JSON je všude, na webu, v da­ta­bázi i všude mezi těmito dvěma ex­trémy, jde o uni­ver­zální formát a všichni ho rádi po­u­ží­vají. Svět by byl krásný, kdyby JSON neměl jedno oš­k­livé ta­jem­ství: Jeho par­so­vání je vět­ši­nou straš­livě pomalé.

Jeden malý test: Mám v sou­boru 20GB JSONů, jeden na každém řádku, zkom­pri­mo­váno přes zstd na ±1GB a chci z nich vy­hlo­dat všechny pole ob­jektů s klíčem id, těch je ně­ko­lik v každém JSONu, který má formu měl­kého stromu. Napsal jsem pro­gram v jazyce D, který ze stdin čte de­kom­pri­mo­vaná data po řád­cích, z nich na­par­suje JSON pomocí im­ple­men­tace ze stan­dardní knihovny a pak z toho vytahá všechny id klíče.

Vý­sle­dek: Pro­gram de­kom­pri­mo­vaná data zpra­co­vává rych­lostí 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.

Tes­to­val jsem na sta­řič­kém laptopu s tímhle pro­ce­so­rem (si­li­kon ročník 2011), to jen aby bylo jasno. Zstd na něm de­kom­pri­muje data rych­lostí 1000 MB/s a ne­před­sta­vuje úzké hrdlo. D pro­gram bez pro­blémů čte z stan­dard­ního vstupu de­kom­pri­mo­vaná data 1000 MB/s1 , takže si můžeme být celkem jisti, že pro­blém spo­čívá ve zpra­co­vání JSONu.

Když ale budu pod­vá­dět a místo par­so­vání JSONu budu jen hledat ře­tě­zec "id": s tím, že pak to, co po něm ná­sle­duje, bude zpra­co­váno jako číslo, můžu na prehis­to­ric­kém stroji jet rych­lostí 750 MB/s v jednom vlákně. Nevím jak vám, ale mě to při­padá jako o něco málo víc, skoro 30x víc.

Abych sem taky vlepil ně­ja­kou ukázku kódu, tak takhle vypadá ono ohle­dá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 ne­zkou­mal, jestli jde o nej­e­fek­tiv­nější va­ri­antu, vůbec jsem se ne­dí­val na di­sas­sem­blo­vaný kód, jestli jsou po­u­žité SIMD in­strukce. Nebylo třeba, 750 MB/s je blízko mému te­o­re­tic­kému maximu a tak to můžu brát jako metu podle které můžeme po­mě­řo­vat všechny ostatní va­ri­anty.

Pak jsem se po­dí­val do světa PHP. Tento jazyk nemá pověst nej­rych­lej­šího na světě, ale přesto v ur­či­tých ob­las­tech ex­ce­luje. Jeho re­ge­xový engine je jeden z nej­rych­lej­ších vůbec. Po­dobně tak se to má s JSON par­se­rem, který mi dává 64 MB/s.

Potom jsem vy­zkou­šel, jak je na tom Java svět.2 Jackson parser má stre­a­ming API, které nikdy ne­pro­vádí plnou ma­te­ri­a­li­zaci JSON AST a per­fektně se hodí, když chci vy­táh­nout jen část dat. Jackson v testu jede rych­lostí 109 MB/s a to hlavně proto, že v tomto pří­padě může na­pros­tou vět­šinu dat pře­sko­čit. Nemusí třeba de­kó­do­vat skoro žádné stringy a ve vět­šině pří­padů po­stačí, když najde kde ak­tu­ální token končí, což je velice efek­tivní.

Něco málo přes 100 MB/s na starém hard­waru možná ne­vy­padá zas tak zle, ale máme se s tímhle spo­ko­jit? Je to všechno? Je tohle cena, kterou pla­tíme za po­ho­dlný se­ri­a­li­zační formát?

Na­štěstí vše není ztra­ceno. Daniel Lemire vy­tvo­řil kni­hovnu sim­dj­son, která si bere za cíl par­so­vat JSON ma­xi­mální možnou rych­lostí. Ben­chmarky uka­zují, že v ur­či­tých si­tu­a­cích na Sky­lake CPU par­suje JSON rych­lostí 2500 MB/s a navíc vý­sled­kem není stream tokenů, ale plně na­vi­go­va­telné JSON AST.

Na laptopu sim­dj­son v mém kon­krét­ním testu jede rych­lostí 380 MB/s — 6x rych­leji než PHP parser, 10x rych­leji než D im­ple­men­tace. Stále to má daleko k te­o­re­tic­kým li­mi­tům pre­zen­to­va­ným autory knihovny, ale přesto za mě dobré.3

Testy jsem ještě zo­pa­ko­val na o něco no­věj­ším hard­waru (ne o moc, je to desk­to­pový Haswell z roku 2013) a tam to běží kolem 520MB/s. Ko­nečně čísla, se kte­rými se dá pra­co­vat.

Tady máte na­mě­řené rych­losti pro oba pro­ce­sory v ta­bulce.

*laptopdesktop
D26 MB/s38 MB/s
PHP64 MB/s124 MB/s
Java Jackson109 MB/s172 MB/s
C++ sim­dj­son380 MB/s520 MB/s
podvod750 MB/s954 MB/s
zstd de­kom­prese1000 MB/s1400 MB/s

Takže jo, JSON je fajn a když si dáte pozor, dá se par­so­vat s trochu ro­zum­nou rych­lostí.


  1. To jen proto, že ne­do­chází ke zby­teč­nému ko­pí­ro­vání. Když data jednou zby­tečně zko­pí­ruji (byLineCopy na­místo byLine), rych­lost čtení spadne na 770 MB/s.
  2. V Javě je ob­tíž­nější za­ří­dit, aby ne­do­chá­zelo ke zby­teč­nému ko­pí­ro­vání dat. Nej­jed­no­dušší způsob, jak číst řádky, přes BufferedReader.readLine pro každý řádek alo­kuje nový string a dojde k pokusu kon­verze na in­terní UTF16 formát. To je v pod­statě no-op, pro­tože JSON ne­ob­sa­huje žádné ne-ASCII znaky a Java tak string stejně bude re­pre­zen­to­vat jako ASCII string, ale pořád je to práce navíc. Čtení jede rych­lostí 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á­vis­losti na de­tai­lech), ale není to vý­chozí va­ri­anta jako v D nebo C++.
  3. Moje teorie je taková, že do­chází k vy­bí­lení cache. V testu prů­měrný JSON objekt po de­kom­presi má ±400KB, což je víc než L2 cache. Když se par­su­jí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 ob­jekty byly menší, zů­staly by v L2 cache a par­so­vání by bylo sviž­nější. Nebo něco na ten způsob. Další výzkum nutný.
píše k47 (@kaja47, k47)