simdjson - JSON को GB/सेकंड की दर से पार्स करना

• SIMD instruction set का उपयोग करके मौजूदा parsers की तुलना में 2.5 गुना तेज़ parsing

• runtime पर CPU के अनुसार optimized parser का अपने-आप चयन: Haswell(AVX2)/Westmere(SSE4.2)/ARM64/अन्य64

• Full JSON और UTF-8 validation सपोर्ट

• एक .h + .cpp फ़ाइल

• RapidJSON की तुलना में केवल 25%, sajson की तुलना में 50% instruction set का उपयोग

[novemberoscar]

लगता है इसके लिए कई तरह के bindings / ports उपलब्ध हैं

• ZippyJSON: simdjson project के लिए Swift bindings.

• libpy_simdjson: libpy का उपयोग करने वाले simdjson के लिए high-speed Python bindings.

• pysimdjson: simdjson project के लिए Python bindings.

• simdjson-rs: Rust port.

• simdjson-rust: Rust wrapper (bindings).

• SimdJsonSharp: .NET Core के लिए C# version (bindings और full port).

• simdjson_nodejs: simdjson project के लिए Node.js bindings.

• simdjson_php: simdjson project के लिए PHP bindings.

• simdjson_ruby: simdjson project के लिए Ruby bindings.

• fast_jsonparser: simdjson project के लिए Ruby bindings.

• simdjson-go: Golang assembly का उपयोग करने वाला Go port.

rcppsimdjson: R bindings.

[xguru]

Rust संस्करण - https://github.com/simd-lite/simd-json

QCon में डेवलपर की प्रस्तुति "Parsing JSON Really Quickly: Lessons Learned"

https://www.youtube.com/watch?v=wlvKAT7SZIQ

[kunggom]

लिंक किए गए व्याख्यान वीडियो का प्रतिलेख:

https://www.infoq.com/presentations/simdjson-parser/

यह जानने की उत्सुकता में पढ़ा कि यह इतनी तेज़ रफ़्तार कैसे हासिल करता है, और सच कहूँ तो यह हर तरह की ब्लैक मैजिक का निचोड़ लगता है। मुख्य बिंदुओं को मोटे तौर पर इस तरह समेटा जा सकता है.

---

[परिचय]

ज़्यादातर JSON parsing libraries ड्राइव की sequential read speed से धीमी होती हैं

• मेरे (वक्ता Daniel Lemire के) सिस्टम ड्राइव पर बड़े text file को sequentially पढ़ने की गति 2.2 GB/s है, लेकिन प्रमुख JSON libraries की parsing speed इससे पीछे रह जाती थी.

• 1 GB/s से ऊपर parsing speed देने वाली libraries बहुत कम दिखीं, इसलिए हमने खुद एक बनाकर देखने का फैसला किया.

• नतीजतन, हमने ऐसी processing speed हासिल की जो ड्राइव bandwidth का पूरा उपयोग कर सकती थी। हिसाब लगाएँ तो input के प्रति 1 byte पर CPU के सिर्फ 1.5 cycles लगे। यह कैसे संभव हुआ?

[विभिन्न सिद्धांत]

branch statements से जितना हो सके बचें

• उदाहरण के लिए, किसी array में random numbers डालने वाले साधारण code में अगर सिर्फ यह जाँचने वाला एक if statement डाल दिया जाए कि संख्या odd है या नहीं, तो वह 5 गुना धीमा हो जाता है। वजह यह है कि CPU branch prediction के असफल होने की लागत बहुत ज़्यादा होती है.

• ऊपर दिए गए code में bit operations से if statement हटा दें तो speed लगभग फिर से पहले जैसी हो जाती है.

• code को बार-बार चलाने पर branch prediction की accuracy बढ़ सकती है, इसलिए performance drop कुछ कम हो सकता है, लेकिन यह आखिरकार nondeterministic behavior है, इसलिए जहाँ branch prediction काम करती है वहाँ performance का अनुमान लगाना या उसे मापना कठिन हो जाता है.

wider words का उपयोग करने के लिए SIMD का आक्रामक उपयोग करें

• SIMD instructions का इस्तेमाल करने पर 64-bit से भी wider word वाले registers उपयोग किए जा सकते हैं, इसलिए 1 cycle में ज़्यादा data process किया जा सकता है। (जैसे SSE या NEON 128-bit, AVX 256-bit) इसलिए जहाँ संभव था, हमने SIMD का भरपूर उपयोग किया। यही input data के प्रति 1 byte पर केवल 1.5 cycles इस्तेमाल कर पाने का राज़ था.

• SIMD का उपयोग करने के लिए processor-specific intrinsic functions इस्तेमाल किए गए। सीधे assembly language का उपयोग करने की सिफारिश नहीं की जाती.

memory/object allocation से बचें

• simdjson में JSON data को एक लंबी tape की तरह माना जाता है, और data को reuse किया जाता है। यानी strings या numbers के लिए अलग से memory allocate नहीं की जाती, बल्कि सब कुछ एक सीधी धारा में process किया जाता है। यह एक आम trick है.

performance को लगातार मापते रहें

• development benchmark-driven तरीके से किया गया। हमारे CI में performance benchmarks शामिल हैं.

• वैसे, जब भी कोई CPU-intensive काम किया जाए, तो यह याद रखना चाहिए कि CPU की operating frequency लगातार बदलती रहती है.

[वास्तविक उदाहरण]

उदाहरण 1: यह सत्यापित करना कि UTF-8 वैध है या नहीं

• input में दिया गया arbitrary data वैध UTF-8 code point है या नहीं, इसकी जाँच आम तौर पर कई branch statements वाला काम होता है.

• हमने SIMD की मदद से 32-byte data को अधिकतम 20 cycles में बिना किसी branch statement के वैध UTF-8 है या नहीं, यह सत्यापित करने का तरीका बनाया.

• क्योंकि UTF-8 के bytes का integer value अधिकतम 244 से ऊपर नहीं जा सकता, इसलिए SIMD instruction से data को 256-bit register में डालकर हर byte से integer 244 को saturation arithmetic (यानि ऐसा arithmetic जिसमें परिणाम की सीमा सीमित की जाती है) के साथ घटाया जाता है, और फिर सिर्फ यह देखना होता है कि कहीं कोई non-zero value तो नहीं है.

• यह तरीका branch statements वाले तरीके से 20 गुना से भी अधिक तेज़ है!

उदाहरण 2: characters को वर्गीकृत करना

• JSON parse करने के लिए comma, colon, brackets, whitespace आदि तरह-तरह के characters को प्रकार के अनुसार classify करना पड़ता है.

• x86-64 और ARM NEON में 16-byte आकार की lookup table को एक ही बार में देखने वाले instructions होते हैं.

• 1 byte को upper 4 bits और lower 4 bits में बाँटकर, पहले से तैयार 2 lookup tables को अलग-अलग apply किया जाता है, और फिर उनके परिणाम पर AND operation किया जाता है.

• code भले थोड़ा गंदा दिखे, लेकिन सिर्फ 5 instructions में बिना branch के 16 characters को classify किया जा सकता है.

उदाहरण 3: escape characters का पता लगाना

• क्या backspace(\) character को आगे लगाकर व्यक्त किए जाने वाले escape characters को बिना branch statements के detect किया जा सकता है? खासकर तब, जब backspace खुद को escape करने के लिए लगातार कई backspace आए हों, तब भी?

• ऐसे मामले में एक trick है: सिर्फ odd-numbered backspace को देखना होता है.

• even positions और odd positions को दर्शाने वाले bitmasks को constants के रूप में रखकर, जटिल bit operations के बाद बिना branch के escape characters को छाना जा सकता है.

• escaped quotes को हटाने के बाद जो बचता है, वही strings को दर्शाने वाले quotes होते हैं.

• इस तरह निकाले गए quote positions को bitmask के रूप में रखकर अगर बार-बार xor bit operation किया जाए, तो strings की positions बताने वाला bitmask मिल सकता है। अधिकांश processors में यह हिस्सा एक ही instruction से किया जा सकता है.

• bit sets और string positions को correspond कराने के तरीके में भी trick है, लेकिन समय के अभाव में उसे छोड़ते हैं.

उदाहरण 4: numbers को parse करना

• numbers को parse करना बेहद महँगा काम है। एक अच्छी तरह optimized C function से floating-point parsing का benchmark किया गया तो 0.09 GB/s जैसी हैरान कर देने वाली speed मिली। यह साफ़ bottleneck था.

• numbers parse करने वाले ज़्यादातर code आम तौर पर एक बार में byte-level पर काम करते हैं। यह कभी तेज़ नहीं होता.

• 8 characters को लाकर उन्हें एक 64-bit integer में बनाया जाए और वक्ता द्वारा शनिवार देर रात निकाले गए एक खास formula में डाला जाए, तो यह पता लगाया जा सकता है कि ये 8 characters लगातार 8 अंकों वाली संख्या हैं या नहीं। यह खास तौर पर इसलिए महत्वपूर्ण है क्योंकि जिन संख्याओं में digits ज़्यादा होते हैं, उन्हें parse करने में उतना अधिक समय लगता है.

• Stack Overflow पर 8-digit integers को तेज़ी से parse करने वाला code snippet भी दिखा। SIMD का उपयोग करने पर इसे थोड़ा और बेहतर किया जा सकता है, लेकिन महत्वपूर्ण बात यह है कि इस तरह एक बार में अधिक data process करने की strategy का idea मिलता है.

[अन्य]

runtime dispatch

• hardware-dependent code बहुत होने की वजह से हर processor के लिए optimized functions निकलते हैं, और runtime पर processor type के हिसाब से सही function चलवाना काफ़ी मुश्किल था.

• हो सकता है कुछ लोगों को समझ न आए कि इसमें कठिनाई क्या थी, लेकिन असली समस्या यह थी कि compiler की परवाह किए बिना portable code में इसे लागू करना था। कुछ compilers में bugs भी थे, और language level पर भी यह चीज़ समर्थित नहीं थी.

• यह बिंदु इसलिए महत्वपूर्ण था क्योंकि simdjson एक single-header open source library है, जिसे दूसरे projects में आसानी से integrate किया जा सकता है.

अन्य बातें

• कई languages में उपयोग के लिए अलग-अलग wrappers हैं.

• इसका Rust port version है और Go तथा C# ports भी तैयार किए जा रहे हैं, लेकिन Java port नहीं है.

• इस project में उपयोग किए गए कई mathematical formulas सह-लेखक Geoff Langdale के साथ मिलकर बनाए गए थे, और इस पर संबंधित paper VLDB Journal में प्रकाशित किया गया। ( https://doi.org/10.1007/s00778-019-00578-5 )

[xguru]

वाह, बहुत अच्छा पढ़ा। धन्यवाद!