Format wymiany danych

Pliki JSON (JavaScript Object Notation) są wszechobecnie wykorzystywane w internecie. Stanowią one tekstowy format reprezentacji danych i pośredniczą w komunikacji między przeglądarką a serwerem. Uchodzą za lekkie i łatwiejsze w zrozumieniu przez człowieka względem plików XML. Wbrew rozwinięciu skrótowca jest to format niezależny od języka programowania, lecz jego syntaktyka okazuje się podzbiorem JavaScriptu.

Przykład wiadomości sformatowanej jako plik JSON:

{
 "product": "JSON i efektywna analiza składniowa liczb zmiennoprzecinkowych",
 "version": 1,
 "releaseDate": "2020-03-20",
 "person": {
 "name": "Przemysław Pintal",
 "WWW": {
 "Blog": "https://teamquest.pl/blog"
 }
 }
}

Realny scenariusz użycia plików JSON stanowią relacyjne bazy danych, takie jak MySQL czy PostgreSQL. Wartym wskazania przykładem byłby tutaj ClickHouse, zorientowany na kolumny system zarządzania bazą danych, opracowany na potrzeby Yandex Metrica (Narzędzie analizujące ruch na stronie internetowej). W plikach JSON zostają zgromadzone gigabajty danych, które rodzą problemy związane z wydajnością.

Informatyka stosowana

Następstwem trudności związanych z narastaniem tekstowych typów danych jakie należy poddać analizie składniowej, będą koszty spowodowane zwiększonym poborem prądu. Wyższe zużycie elektryczności przełoży się na wygenerowanie dodatkowego ciepła, w efekcie niezdolność do jego efektywnego rozpraszania spowoduje obniżenie taktowania procesora, tym samym wydłuży czas niezbędny do sfinalizowania procesu. Nie powinno się też zapominać o poczuciu responsywności. Dlatego że nie tylko bazy danych wykorzystują pliki JSON. Znajdziemy je także w zupełnie odmiennych programach i sytuacjach użytkowania, np. posiada je Clang Build Analyzer.

Przeczytaj także: Deno - młodszy brat Node.js

Daniel Lemire, profesor informatyki na Uniwersytecie Quebecu w Montrealu, wraz z inżynierem oprogramowania Geoffem Langdalem, zbadali problem przetwarzania plików JSON o dużej objętości. W efekcie napisali artykuł naukowy - "Analiza składniowa gigabajtów danych JSON na sekundę (Parsing Gigabytes of JSON per Second)", opublikowany w The VLDB Journal (Międzynarodowe czasopismo na rzecz wielowymiarowych baz danych - The International Journal on Very Large Data Bases). Publikacja pociągnęła za sobą implementację w postaci biblioteki simdjson, której kod źródłowy znajduje się na GitHubie (licencja Apache 2.0). Jest także wymieniona w kolekcji Awesome Modern C++ - zbiór dobrych praktyk, książek i bibliotek poświęconych nowoczesnemu C++ (standard C++11 i wyższe).

Rozbiór gramatyczny

Simdjson to pełnowartościowy parser (sprawdza poprawność wprowadzonych danych), jednakże nie jest to pełnoprawna biblioteka (nie pozwala na edycję i jej zapis w pliku JSON). simdjson potrzebuje o trzy czwarte mniej instrukcji procesora niż RapidJSON i o pięćdziesiąt procent mniej względem sajson. Poniższa grafika prezentuje wyniki benchmarku (szczegóły we wzmiankowanym artykule naukowym), przeprowadzonego na procesorze i7-6700 3.4 GHz w trybie 64-bitowym.

Jest to najprawdopodobniej pierwszy parser JSON, który jednocześnie sprawdza poprawność i osiąga wydajność liczoną w gigabajtach na sekundę, mimo że jest napędzany konsumenckim procesorem. Dzieję się tak za sprawą kilku czynników, ale przede wszystkim operuje on na 64-bitach (operatory bitowe - bitwise) i wykorzystuje instrukcje SIMD.

Zobacz też: Żegnamy Visual Basic. Język przestanie być rozwijany wraz z premierą .NET 5.0

Pierwszy etap działania parsera jest czysto mechaniczny i w większości wolny od skoków instrukcji (brak operacji rozgałęziania - branch free code). Nie licząc weryfikacji UTF-8 i dużych struktur znaków na finale etapu.

Etap pierwszy:

1. Na wejściu weryfikuje poprawność UTF-8 w całym pliku.
2. Wyszukuje nieparzyste sekwencje ukośników odwrotnych (wtedy następuje sekwencja ucieczki).
3. Wykrywa jakie znaki znajdują się wewnątrz cudzysłowów, poprzez odfiltrowanie cudzysłowów ze znakiem modyfikacji z poprzedniego kroku i dokonuje współbieżnej sumy prefiksowej z operatorem XOR (używa instrukcji PCLMULQDQ z argumentem -1 jako mnożnikiem), aby przekształcić uwalnianą wcześniej maskę w maskowanie które wskaże jakie bity znajdują się pomiędzy parą cudzysłowów.
4. Wykrywa znaki strukturalne i odstępy metodą wyszukiwania tablicowego (zaimplementowane parą instrukcj VPSHUFB).
5. Wykrycie znaków pseudostrukturanych, aby wskazać je kolejnemu etapowi parsowania, w celu detekcji błędów.
6. Konwersja maski bitowej złożonej ze znaków strukturalnych i pseudostrukturalnych w szereg indeksów.

Etap drugi nie jest już wolny od rozgałęzionego kodu. Działa jako automat oparty na goto ze stosem, po czym sprawdza czy sekwencja znaków strukturalnych i pseudostrukturalnych, które przeszły walidację odpowiadają prawidłowemu JSON.

Parsowanie liczb

Na blogu Daniela Lemire można przeczytać, iż sedno problemu optymalizacji parsowania plików JSON objawia się w ciągach liczb. Jest możliwe przekształcić ciąg 1,3553e142 w liczbę zmiennoprzecinkową podwójnej precyzji (koszt setek lub tysięcy instrukcji procesora), niemniej funkcja strtod z biblioteki standardowej działa powoli. Norma IEEE 754 zawiera trudne w implementacji funkcje, choćby zaokrąglanie do liczb parzystych. Poświęcenie tego typu subtelności sprawi, że zostanie utracony ostatni bit w wyniku dekodowania ciągu, jakkolwiek jest on bez znaczenia. Świadomość tego jest irytująca dla programisty, mimo że liczby podwójnej precyzji zapewniają większą dokładność, niż będzie wymagał tego jakikolwiek projekt inżynieryjny.

Zobacz również: Standard C++20 został sfinalizowany. Zwięzłe omówienie popularniejszych nowości

Dla większości przypadków obliczeń można użyć szybkiego algorytmu, ale należy zachować możliwość odwrotu (fallback) do funkcji zapewniającej dokładność określoną przez standard. Jedyne co należy zrobić to prawidłowo uwzględnić ewentualność błędu i zastosować obejście. Dzięki temu nie poświęci się dokładności, gdy sparsuje się ciąg liczb dziesiętnych do wartości zmiennoprzecinkowych podwójnej precyzji (binary64).

Kod nowej metody znajduje się na GitHubie. Benchmark przeprowadzono na kolekcji ciągów z sampla geojson - canada.json, na iMacu (2017):