Optimalizace async. parseru JSON v C++20

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.

Co měřit?

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

Copy-Paste bug

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

Optimalizujeme

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\"" |
+-----------+-------------+----------+

Malá úprava awaiteru udělá hodně

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é.

Přímé kopírování znaků 

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:

1. Nalezení souvislého úseku znaků, které odpovídají podmínce (zpravidla je test postaven tak, že znaky se nerovnají nějakému výčtu znaků)
2. Výpočet, kolik znaků se bude kopírovat
3. Zvětšení výstupního bufferu
4. Binární kopírování

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í řetězců

Č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ší

Validace čísel

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ů: 

• čárka – oddělovač polí
• zavírací hranatá závorka -poslední číslo v poli
• zavírací složená závorka -poslední číslo v objektu
• EOF – prozatím tuto variantu nebudu řešit (vím, není to v souladu se specifikací formátu)

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)

Znovupoužití parseru

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í.

Výsledky

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

Závěr

Je to dost rychlý?

Kód k prohlédnutí najdete zde: parser.h