Toto je dodatek k předchozímu článku o parsování JSON pomocí korutiny. Ačkoliv původním záměrem nebylo maximalizovat rychlost, ale spíš benefit asynchronního zpracování, tak diskutéři pod článkem mne donutili podívat se na možnosti optimalizace právě na rychlost.
Posuzovat efektivitu algoritmu podle rychlosti je asi ta nejjednodušší metrika, ale k tomu jsem se původně nechtěl snižovat. Jedno číslo, které nemusí vyjadřovat skutečnou efektivitu. Algoritmus může mít další benefity, například paměťovou náročnost nebo schopnost analyzovat a validovat vstup asynchronně bez ukládání celého vstupu v mezipaměti. Tohle se musí vyjasnit abychom pochopili mou argumentaci proti hned prvnímu příspěvku:
použij simdjson a ušetři si práci, rychlej to nenapíšeš :)
Chápu, že jde spíš o výkřik a trochu zavání trolováním, ale i další příspěvky se dotazovaly na rychlost a já jsem neměl v ruce žádná čísla. Na rychlo sestavený test mi ukázal rychlost kolem 96MB/s, čímž jsem moc lidí nepotěšil (na stroji Intel s frekvencí 2.9GHz). Podívejme se ale nejprve na nejrychlejší alternativu.
Projekt simdjson se skutečně pyšní rychlostí čtení JSON textu jeho „parsování“. Na stránkách najdeme benchmark, kde jejich algoritmus dosahuje rychlosti až 3GB/s na Intel Skylake processor (3.4 GHz) . Jinými slovy, skoro 1 znak za 1 procesorový takt. Neuvěřitelné. Ale zní to logicky, jedna SIMD instrukce je schopná v 4 taktech zpracovat 16 bajtů, takže mám prostor pro 4 takové instrukce, abych se dostal na 1 znak za 1 takt. V tomhle krátkém čase musím detekovat typ elementu, převést JSON string na utf-8, převést text na číslo, sestavit pole, sestavit objekt… hmmm… opravdu?
Problém simdjson je ten, že nic z toho nedělá. Tahle knihovna používá SIMD instrukce pouze k rychlému nalezení jednotlivých JSON elementů, jednoduše najde čárky, závorky, uvozovky a nad těmito úseky sestaví nějakou pomocnou strukturu. Vlastní parsování začíná až při přístupu k jednotlivým prvkům JSONu. Pokud tedy sestavím benchmark takovým způsobem, že mi postačí měřit pouze počáteční „načtení“ JSON textu, pak neměřím skutečný parser, to číslo mi nic neříká, protože k žádnému parsování nedošlo.
Není tedy divné, že simdjson
bez problému načte i nevalidní JSON, a to že je nevalidní zjistíme až při přístupu k prvkům.
Nepovažuji takový systém měření efektivity za spravedlivý. Nechci úplně „zahazovat“ tento typ benchmarku, ale dohodněme se, že jde o jinou kategorii a nejde to srovnávat. Já se budu pokoušet měřit efektivitu plnohodnotného parseru, který je schopen vyhodnotit validitu JSONu, a třeba převést řetězce do UTF-8 formátu. Otázkou je, jak to bude s čísly, v minulém článku jsem psal, že čísla se neparsují, ale předávám jako řetězec. I tak součástí parseru je ověření validity čísla a tato část bude součástí měření.
Na druhou stranu součástí měření nebude sestavování struktury. Je to asi podobné, jako bych měřil efektivitu SAX parseru pro XML dokument. Jak víme, SAX parser pouze analyzuje vstup a volá uživatelem definované funkce pro jednotlivé eventy, které během analýzy nastanou. Jsou to eventy typu „otevření tagu“,„zavření tagu“, „načtení atributu“, „načtení textu mezi tagy“. Pokud budu chtít udělat benchmark SAX parseru, nechám těla funkcí reagující na tyto eventy príázdné. Potřebuju totiž měřit jen tu analýzu vstupu.
V případě mého JSON parseru, který jsem v minulém článku popisoval, musí uživatel dodat továrnu ( JsonFactory
), což je třída zodpovědná za tvorbu objektů, které představují jednotlivé JSON elementy. Způsob uložení těchto elementů tak nechávám na uživateli knihovny, tak aby si uživatel mohl vybrat své oblíbené API pro manipulaci s dokumentem, který parsováním JSONU vznikne. Tuto továrnu v našem testu budeme mít prázdnou
extern "C" { void no_inline(void *, ...); } struct Empty {}; class EmptyFactory { public: using value_type = Empty; using key_type = Empty; static Empty new_string(std::string_view x) {no_inline(&x);return {};} static Empty new_number(std::string_view x) {no_inline(&x);return {};} static Empty new_bool(bool x) {no_inline(&x);return {};} static Empty new_null() {no_inline(nullptr);return {};} static Empty new_array(std::span<Empty> x){no_inline(&x);return {};} static Empty new_object(std::span<Empty> x, std::span<Empty> y){no_inline(&x,&y);return {};} static Empty new_key(std::string_view x) {no_inline(&x);return {};} };
Céčkovská funkce no_inline() je ve skutečnosti prázdná, ale je definovaná mimo kompilační jednotku. Vytváří „zátěž“, přerušuje optimalizační cesty překladače. Ono by se mohlo stát, že by překladač usoudil, že kód nedělá nic a provedl by optimalizaci „až na nulu“. Tato funkce také přebírá ukazatele na proměnné proto, aby se překladač nesnažil optimalizovat vyřazením kódu, který inicializuje proměnné, které se následně nepoužijí. To by výrazně ovlivnilo měření k optimističtějším číslům
Znáte „copy-paste bug“? To je bug, který vyrobíte tak, že zkopírujete kód z jednoho souboru do jiného, avšak zapomenete jej po zkopírování upravit tak, aby odpovídal nově zamýšlenému účelu. Tenhle bug zasáhl i mě. Když jsem sestavoval test, nevšiml jsem si, že jsem nezměnil JsonFactory
z testovací továrny na EmptyFactory
. To ovlivnilo měření, jehož výsledky jsem dával do diskuze a které vycházelo nějakých :
~96 MB/s
Všechny výsledky jsou na stroji
`Intel(R) Core(TM) i7-10700F CPU @ 2.90GHz`
Až v další vývojářské seanci jsem si toho všimnul a po dodání správné továrny jsem se dostal na výsledek:
~420 MB/s
Při optimalizacích jsem pouštěl test ve dvou variantach. Varianta validační, která byla pomalá a kde jsem testoval, že žádná z úprav nezměnila fungování parsera. A pak samozřejmě benchmark, kde šlo o rychlost. Proto zapomenutí te původní továrny nevedlo k chybě při překladu, neboť též byla přítomna. To vedlo k těm malým číslům
Benchmark jsem pouštěl 1000× nad dokumentem (twitter.json ze simdjson). Při měření docházelo k velkému rozptylu hodnot, takže beru nejvyšší změřené číslo.
Problém u měření byl ten, že CPU náhodně zvyšuje a snižuje frekvenci podle potřeby a vytížení systému. Nebyl jsem schopen dohledat, jak zamknout frekvenci CPU na konkrétní číslo (pokud by někdo věděl jak to udělat, budu vděčný). Nejvyšší čísla by tak odpovídala frekvenci CPU 3.2 GHz (základní frekvence je 2.9 GHz).
Poznámka: Veškeré optimalizace budu provádět v C++. Nebudu používat ASM. Nejnižší úroveň je použití pointerové aritmetiky.
Veškeré optimalizace nesmí narušit schopnost parseru zpracovávat data asynchronně, nesmí ho rozhodit to, že text je rozdělen v nevhodných místech. Například musí fungovat zpracování řetězce který je rozdělen takto :
+-----------+-------------+----------+ | "Text v \ | "uvozovk\u0 | 0E1ch\"" | +-----------+-------------+----------+
Výsledná rychlost algoritmu často závisí na drobných úpravách kódu. Je to často velice nedeterministé, a také značně záleží na překladači. Následná úprava awaiteru znamená zrychlení o 8% v GCC-13
template<typename Source> struct CharacterSource { using SourceAwaiter = coro::make_awaitable<Source>; static_assert(coro::awaitable_r<SourceAwaiter, std::string_view>, "Source must returns string_view and must be avaitable"); Source &_src; std::string_view _str = {}; std::size_t _pos = 0; bool _fetched = false; union { SourceAwaiter _srcawt; }; CharacterSource(Source &src):_src(src) {} ~CharacterSource() {} bool await_ready() { _fetched = false; if (_pos < _str.length()) [[likely]] { return true; } new (&_srcawt) SourceAwaiter(_src); _fetched = true; return _srcawt.await_ready(); } auto await_suspend(std::coroutine_handle<> h) { return _srcawt.await_suspend(h); } char await_resume() { if (_fetched) [[unlikely]]{ coro::on_leave finally=[this]{ _srcawt.~SourceAwaiter();_fetched = false;}; _pos = 0; _str = _srcawt.await_resume(); if (_str.empty()) throw json_parse_error::unexpected_eof; } return _str[_pos++]; } };
Došlo pouze k přesunu nulování příznaku _fetched z místa destrukce zdrojového awaiteru v await_resume
na začátek funkce await_ready
. I když to vypadá nelogicky, protože místo nulování příznaku po načtení dat jej nyní nulujeme při každém průchodu, ve skutečnosti optimalizující překladač jinak přeloží await_resume
. Tam se příznak testuje a pokud překladač vidí, že je příznak nulován a následně není nastaven, tak v téhle větvi úplně ignoruje test a přeloží jen ten return. Funkce await_resume
je přeložena ve dvou variantách. Jednou pro „data jsou k dispozici“ a podruhé „data byla načtena“. První větev je pak lépe začleněna do kódu volajícího, podle toho, jak se s výsledkem pracuje.
Kód by byl možná ještě rychlejší, kdyby místo nulování příznaku v každém kroku bylo možné překladači oznámit, že _fetched je vždycky false, pokud se vstupuje do await_ready
. Pokud vím, nějaké možnosti definovat assumptions se chystají v dalších verzích C++. Vhodnou konstrukcí takového assume by šlo vynutit si stejnou optimalizaci bez zbytečného zápisu stejné hodnoty do proměnné.
V předchozím odstavci jsem připomněl třídu CharacterSource, která má schopnost rozsekat řetězec na písmenka. Je vidět, že optimalizační schopnosti překladačů kolem co_await
na vysoké úrovni, i tak vygenerovaný kód by se dal ještě zrychlit.
Instance této třídy totiž drží nezpracované znaky v zásobníku znaků. Obě následující optimalizace tak pracují přímo s tímto zásobníkem a obchází tak co_await
v situacích, kdy to jde. Je však potřeba zachovat původní funkcionalitu v případě že dojdou znaky v zásobníku. Pouze operátor co_await
umí korutinu přerušit při čekání na další znaky.
Zrychlení přinesla možnost kopírovat znaky binárně do bufferu s podmínkou „dokud znaky odpovídají zadané podmínce“.
Kopírování probíhá takto:
Hlavní zrychlení je přitom v bodě 3 a 4. Vkládání znaků do výstupního bufferu po jednom se totiž nedá dobře zoptimalizovat. S každým vkladem se musí testovat dostupné místo. Oproti tomu rezervace místa a pak binární kopírování se optimalizuje dobře, tam se uplatní přesuny po větších „kusech“. Pro přesun dlouhých řetězců se použijí i SIMD instrukce (v -march=native
)
V tomto směru mě překvapila efektivita std::copy
, který byl rychlejší, než memcpy
. Já vím, je to divné, ale měření tak dopadlo.
Rychlejší také byla přímá práce s ukazateli, namísto práce s indexem do pole znaků
template<std::invocable<char> Condition> void CharacterSource::copy_until(Condition &&cond, std::vector<char> &cont) { const char *b = _str.data(); const char *c = b +_pos; const char *e = b +_str.length(); while (c != e && cond(*c)) ++c; std::size_t fnd = c- b; if (fnd == _pos) return; auto sz = (fnd-_pos); auto bufsz = cont.size(); cont.resize(bufsz+sz); std::copy(_str.data()+_pos, _str.data()+_pos+sz, cont.data()+bufsz); _pos = fnd; }
Čtení a analýzu řetězců jsem přesunul z lambda funkce, přímo do case větvě korutiny – ručně jsem to tam inlinoval. To má výhodu, že nepotřebuji evidovat stav (tedy jestli čtu normální nebo speciální znak)
case '"': { int first_codepoint = 0; do { src.copy_until([](char c){return c != '"' && c != '\\';}, strbuff); c = co_await src; if (c == '"') break; if (c == '\\') { c = co_await src; switch (c) { default: break; case 'b':c = '\b';break; case 'f':c = '\f';break; case 'n':c = '\n';break; case 'r':c = '\r';break; case 't':c = '\t';break; case 'u': { int codepoint = 0; for (int i = 0; i < 4; ++i) { unsigned char c = co_await src; if (c >= 'A') { c = (c | 0x20) - 87; if (c > 0xF) throw json_parse_error::invalid_unicode; } else { c -= '0'; if (c > 9) throw json_parse_error::invalid_unicode;; } codepoint=(codepoint << 4) | c; } if (codepoint >= 0xD800 && codepoint <= 0xDFFF) { if (first_codepoint) { if (first_codepoint > codepoint) std::swap(first_codepoint, codepoint); codepoint = 0x10000 + ((first_codepoint - 0xD800) << 10) + (codepoint - 0xDC00); } else { first_codepoint = codepoint; continue; } } if (codepoint <= 0x7F) { strbuff.push_back(static_cast<char>(codepoint)); } else if (codepoint <= 0x7FF) { strbuff.push_back(static_cast<char>(0xC0 | ((codepoint >> 6) & 0x1F))); strbuff.push_back(static_cast<char>(0x80 | (codepoint & 0x3F))); } else if (codepoint <= 0xFFFF) { strbuff.push_back(static_cast<char>(0xE0 | ((codepoint >> 12) & 0x0F))); strbuff.push_back(static_cast<char>(0x80 | ((codepoint >> 6) & 0x3F))); strbuff.push_back(static_cast<char>(0x80 | (codepoint & 0x3F))); } else if (codepoint <= 0x10FFFF) { strbuff.push_back(static_cast<char>(0xF0 | ((codepoint >> 18) & 0x07))); strbuff.push_back(static_cast<char>(0x80 | ((codepoint >> 12) & 0x3F))); strbuff.push_back(static_cast<char>(0x80 | ((codepoint >> 6) & 0x3F))); strbuff.push_back(static_cast<char>(0x80 | (codepoint & 0x3F))); } first_codepoint = 0; }continue; } } strbuff.push_back(c); } while (true);
Kód vola src.copy_until
pro načtení všech „obyčejných znaků“ v jednom kroku. Čtení je zastaveno pokud je nalezen znak uvozovek nebo znak zpětného lomítka. Čtení se samozřejmě zastaví, pokud dojdou znaky a je třeba korutinu přerušit. To zajistí následující co_await
. Ten také může načíst obyčejný znak, proto je nutné tuhle situaci ošetřit. Pokud je načtena uvozovka, čtení se ukončí. Pokud je načteno zpětné lomítko, následuje vyhodnocení speciálního znaku. Tam se pouze přeloží znak na patřičný řídící znak. Escapované znaky, které nejsou řídícím znakem se pouze přepíší. (To tedy není v souladu se specifikací formátu, výsledkem bude, že nevalidní JSON, který obsahuje chybné escape sekvence bude přijat, jen tyto sekvence budou ignorovány). Při načtení u
se dekóduje HEX sekvence a případně se sloučí surrogate pair do jednoho codepointu a nakonec se převede na UTF-8
Optimalizace tedy využívá faktu, že JSON bude spíš složen z obyčejných znaků, což zahrnuje i znaky přímo v kódování UTF-8, které by měly být povoleny. Pokud však JSON obsahuje unicode znaky pomocí escape sekvence u
, pak bude zpracování pomalejší
Podobná myšlenka byla implementována i u validace čísel. U čísel platí, že za nimi se může vyskytnou jeden z následujících znaků:
Všechny znaky, které nepatří do výše uvedené skupiny budeme načítat do bufferu, včetně případných bílých znaků (kupodivu to vygenerovalo rychlejší kód).
Jakmile máme načteno, provede se validace čísla přímo v bufferu. Pokud je číslo validní, zkontroluje se zbytek bufferu, který smí obsahovat jen bílé znaky. Teprve pak je předán řetězec do továrny.
Validace čísla tak neobsahuje žádný co_await
if (c == '-' || is_number(c)) { static constexpr auto cond = [](char c) { return (c != ',' && c != '}' && c != ']' ); }; do { strbuff.push_back(c); src.copy_until(cond, strbuff); c = co_await src; } while (cond(c)); strbuff.push_back('\0'); std::size_t pos =0; if (strbuff[pos] == '-') ++pos; if (strbuff[pos] == '0') ++pos; else if (is_number(strbuff[pos])) { ++pos; while (is_number(strbuff[pos])) ++pos; } else { throw json_parse_error::invalid_number; } if (strbuff[pos] == '.') { ++pos; if (is_number(strbuff[pos])) { ++pos; while (is_number(strbuff[pos])) ++pos; } else { throw json_parse_error::invalid_number; } } if (is_e(strbuff[pos])) { ++pos; if (is_sign(strbuff[pos])) { ++pos; } if (is_number(strbuff[pos])) { ++pos; while (is_number(strbuff[pos])) ++pos; } else { throw json_parse_error::invalid_number; } } auto end_of_numb = pos; while (pos < strbuff.size()) { if (static_cast<unsigned char>(strbuff[pos])>32) { throw json_parse_error::invalid_number; } ++pos; } items.push_back(co_await coro::make_awaitable([&]{ return fact.new_number(std::string_view(strbuff.data(), end_of_numb)); })); strbuff.clear(); src.put_back(); }
Část která validuje číslo by mohla být přesunuta do obyčejné funkce pro lepší čitelnost, ale ok, teď jsem se tím nezabýval. Jinak je to velice přímočarý způsob validace. Ukončující nula vkládaná ručně do bufferu slouží jako zarážka a případně ukončuje řetězec pokud by k převodu na číslo bylo na uživatelské straně použito strtod
(doporučuji std::from_chars
)
Tahle úprava se týká knihovny libcoro
a zavádí nový typ korutiny, která vychází z generátoru. Jedná se o generátor, který lze spouštět s parametry
coro::generator<Ret(Args...), Allocator>
Pokud má generátor aspoň jeden argument, pak může použít co_yield nullptr
k načtení parametrů. Výsledek pak vrací přes co_yield result
coro::generator<float(int, int)> example() { do { auto [a, b] = co_yield nullptr; //.... //.... auto result = ... co_yield result; } while (true); }
Smyslem tohoto generátoru je znovupoužití existující korutiny a případně alokované paměti v různých bufferech držených tou korutinou. Korutina neskončí odevzdáním výsledku, ale může přijmout nový požadavek a tím využít již alokovanou paměť k novému výpočtu.
Tuto optimalizaci jsem též zapracoval do parseru:
Source src1(...), src2(...); auto parser = json_parser<JsonFactory, Source>(); auto res1 = parser(src1).get(); auto res2 = parser(src2).get();
Optimalizace by měla zrychlit zpracování mnoha malých JSON souborů. Na jednom souboru se nijak neprojeví.
Testoval jsem 1000× twitter.json ze simdjson. (631MB). Zobrazená hodnota je nejvyšší změřená hodnota ze všech testů (eliminace power managment CPU, background tasky operčního systému atd). Flagy -O3 -march=native
CPU: Intel(R) Core(TM) i7-10700F CPU @ 2.90GHz Max frekvence: 3.20GHz (/proc/cpuinfo)
gcc-12: Time: 1293175012 nanosec Speed: 488.162 MB/s gcc-13: Time: 1168591368 nanosec Speed: 540.205 MB/s clang-15: Time: 1043205141 nanosec Speed: 605.134 MB/s
Je to dost rychlý?
Kód k prohlédnutí najdete zde: parser.h
Pokud vím, nějaké možnosti definovat assumptions se chystají v dalších verzích C++.
C++23 má atribut assume https://en.cppreference.com/w/cpp/language/attributes/assume
C23 má macro unreachable https://en.cppreference.com/w/c/program/unreachable
Dá se postavit macro, které detekuje C++23 / C23 / starší standard / specifickou platformu a použije správnou variantu (__builtin_unreachable, __assume, __builtin_assume).
Jj, děkuji za poznámku , já v zásadě o tom vím , jen to nemám pořádně nastudované a testované.
Tady by se hodil assume na _fetched false, protože překladač při optimalizaci co_await neví nic o tom jestli se ten příznak nenastavuje někdy jindy. Z funkce await_ready vedou tři cesty, z nichž jedna končí false a další dvě končí true, s nichž jedna má ten příznak _fetched nastaven na true a druhá na false. Teda takový je záměr ale překladač nemá jak ověřit ten poslední případ. Proto generuje rychlejší kód pokud je příznak explicitně vynulován, protože může přeskočit i ten test na _fetched v await_resume a ten return inlinuje do té přímé větve a vysledkem je pak jednoduchý cyklus s jednim testem - pokud je co_await v cyklu
Zkusím v další seanci tam dat c++23 a ověřit jak se to bude chovat s assume
Já se přiznám, že pořád nechápu, proč trváš na asynchronním parseru? Nebylo by lepší použít stream parser s tím, že asynchronní čtení se vyřeší mimo parser? Ještě bych pochopil něco takového dělat pro studijní účely, ale proč to potom proboha optimalizovat?
Já kdybych psal json parser s použitím minima paměti, tak bych spíš použil libovolný stream parser a čtení dat bych dělal přes IO_uring a mmapované buffery do kernelu. IMHO by to bylo rychlejší i paměťově úspornější než cos napsal (nečetlo by to po bytech a zároveň by se nekopírovala paměť z kernelu do user spacu), jen by to běželo jenom na linuxu.
Nebo mi uniká nějaký důvod proč psát něco takového?
mohl bych stream parser vidět?
Jen abysme si ujasnili o co jde. Jde o to, že nechceš blokovat vlákno, když čekáš na IO. Prostě se ti spojeni v půlce parsování zasekne, nechceš blokovat vlákno, pokud máš jen omezený množství vláken a mnoho requestů.
Třeba útok slowloris se pak dělá velice snadno
Samozřejmě, snadné řešení je stáhnout celý obsah do paměti asynchronně jako blok bajtů a pak to teprve parsovat. Pokud víš, kolik toho máš stáhnout (na bajt)
Pokud myslíš parser, který ti volá callbacky s každým přijatým blokem dat, tak to se přece nevylučuje. První čtení si nastaví strea, a pak kdykoliv mi přijde callback s daty, tak buffer předám awaiteru a zavolám resume, provede se parsování toho bloku a na konci ho hodím zpět do suspend a vrátím se s callbacku a čekám na další callback. Jakmile se načte všechno, korutina ohlásí konec. Jako tohle řešení nepředepisuje, co se má použít jako zdroj dat. Může se použít i zero copy buffer, protože jediné co se vyžaduje je std::string_view. Kopírování dat nikde nedochází, pokud tedy nemyslíš kopírování znaků v řetězcích do datových struktur k tomu určených.
Intenzivně se zabývám programováním zejména v jazyce C++. Vyvíjím vlastní knihovny, vzory, techniky, používám šablony, to vše proto, aby se mi usnadnil život při návrhu aplikací. Pracoval jsem jako programátor ve společnosti Seznam.cz. Nyní jsem se usadil v jednom startupu, kde vyvíjím serverové komponenty a informační systémy v C++
Přečteno 50 233×
Přečteno 23 535×
Přečteno 22 525×
Přečteno 20 434×
Přečteno 17 495×