serde_json स्ट्रिंग प्रोसेसिंग 20% तेज

 (purplesyringa.moe)
2 पॉइंट द्वारा GN⁺ 2024-08-25 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Rust ecosystem में बेसिक JSON parser की तरह इस्तेमाल होने वाला serde_json स्ट्रिंग-भारी benchmarks में छोटे internal optimizations से भी 10%, 23%, 32% performance improvement हासिल करता है
  • error position calculation में स्ट्रिंग के शुरुआती हिस्से को सीधे scan करने के बजाय memchr से line count और आख़िरी newline खोजने के लिए बदलाव किया गया, जिससे success path की तुलना में 2 गुना से ज़्यादा धीमे error path का अंतर कम हुआ
  • string parsing का core loop \\, \", control characters को अलग-अलग खोजने के बजाय SWAR से एक बार में जाँच करता है, जिससे असली SIMD के बिना भी छोटी strings में low latency मिलती है
  • \\u escape decoding में LUT, signed integers, और pre-shift table से branch और shift cost घटाई गई, और रूसी War and Peace JSON parsing 284 MB/s से 344 MB/s तक तेज हुई
  • इसके बाद bottleneck बने UTF-8 encoding को char::encode_utf8 और Vec::extend_from_slice की initialization·copy cost से बचाने वाली manual UTF-8 generation से संभाला गया, जिससे वही benchmark 374 MB/s तक पहुँचा

serde_json optimization का बड़ा असर क्यों पड़ता है

  • serde Rust का प्रतिनिधि serialization·deserialization framework है, और serde_json JSON handling के लिए उसका widely used official combination है
  • पोस्ट के समय के अनुसार serde_json की reverse dependencies 26,916 थीं, जबकि simd-json की 66 थीं
  • इस स्तर के usage में serde_json के अंदर का छोटा सुधार भी पूरे Rust ecosystem में cumulative effect दे सकता है
  • जब बहुत से users किसी दूसरे JSON parser पर आसानी से switch नहीं करते, तब मौजूदा library के भीतर low-risk optimization व्यावहारिक होता है

error position calculation: simple loop से memchr तक

  • error path benchmark में serde_json उसी data के success path से 2 गुना से ज़्यादा धीमा था
    • canada, citm_catalog, twitter datasets में error path, success path की तुलना में -48%~-77% धीमा था
  • bottleneck position_of_index() function था, जो error message formatting के लिए index को line/column में बदलता था
    • पुराना implementation self.slice[..i] को byte unit में iterate करता था और हर \n पर line और column update करता था
  • calculation को दो stages में बाँटने पर memchr लागू किया जा सका
    • self.slice[..i] के भीतर \n की count से 0-based line number निकाला गया
    • आख़िरी \n की position खोजकर उसे i से घटाकर column number निकाला गया
  • memchr single-character search और count के लिए optimized implementation देता है, और अंदर से SIMD इस्तेमाल करता है
  • PR #1160 merge होने के बाद error path performance काफ़ी सुधरी
    • canada DOM मानक के अनुसार error path 122 MB/s से 216 MB/s तक बढ़ा
    • citm_catalog struct मानक के अनुसार 195 MB/s से 736 MB/s तक बढ़ा
    • error path अब भी success path से धीमा था, लेकिन अंतर कम हुआ

string escape search: तीन conditions एक साथ ढूँढना

  • string parsing का पुराना core loop ESCAPE table को देखते हुए non-escape bytes को skip करता था
    • JSON string में handle किए जाने वाले escape targets \\, \", और 0x1F से कम या बराबर ASCII control characters हैं
    • JSON spec के अनुसार string के अंदर control codes allowed नहीं हैं
  • पहली कोशिश memchr2 से पहले \\ या \" खोजने और फिर control characters को अलग से check करने की थी
    • इससे string को एक बार तेज़ और एक बार धीमे, यानी दो बार iterate करना पड़ता था
    • सिर्फ़ आधे हिस्से को vectorize करके बाकी scalar छोड़ने से overall improvement नहीं मिला
  • दूसरी कोशिश memchr2 और manual SIMD से control characters की अनुपस्थिति जाँचने वाली structure थी
    • छोटी strings में runtime dispatch function call की cost भारी पड़ती थी
    • लंबी strings में memory को दो बार पढ़ने की समस्या बनी रही
  • अंतिम implementation को \\, \", और control characters को एक ही pass में खोजने की दिशा में व्यवस्थित किया गया

SWAR से SIMD-जैसी processing

  • platform-specific SIMD code अलग से न जोड़ने के लिए SWAR(SIMD Within A Register) technique का इस्तेमाल किया गया
    • 128-bit SIMD के बजाय 64-bit word को 8 bytes की तरह treat किया गया
    • bit operations से हर byte का condition match एक साथ जाँचा गया
  • control character check को c >= 0 && c < 0x20 condition के bit-operation form में बदला गया
    • 8-byte chunk में !c & (c - 0x2020202020202020) & 0x8080808080808080 जैसे mask से check किया गया
    • 64-bit subtraction का borrow ऊपरी bytes तक propagate हो सकता है, लेकिन सबसे निचली position के control character को खोजने के उद्देश्य में यह समस्या नहीं थी
  • \\ और \" को भी इसी तरह check करके एक expression में जोड़ा गया
    • पूरी expression 9 bit operations से बनी थी
    • x86 SIMD में 7 operations काफ़ी होते, इसलिए throughput कम था, लेकिन छोटी strings में latency ज़्यादा महत्वपूर्ण थी
  • json-benchmark में यह SWAR code असली SIMD code से ज़्यादा efficient था
  • बहुत छोटी strings में SWAR scalar code से धीमा हो सकता था
    • लगभग 5-character strings में regression दिखा
    • empty string "" और लगातार escape \r\n, \uD801\uDC37 जैसे सामान्य patterns को सुरक्षित रखने के लिए SWAR loop में जाने से पहले पहले character के escape होने की जाँच की गई
  • string search optimization के नतीजे dataset के अनुसार अलग थे
    • twitter struct 638 MB/s से 785 MB/s तक, यानी +23%
    • twitter DOM 305 MB/s से 335 MB/s तक, यानी +10%
    • citm_catalog struct 865 MB/s से 905 MB/s तक, यानी +5%
    • empty string कुछ microbenchmarks में अब भी 2% के भीतर धीमी रही

Unicode escape decoding optimization

  • serde_json raw Unicode strings और \\u escapes दोनों handle करता है
    • उदाहरण: "🥺" और "\\ud83e\\udd7a"
  • पुराना hex decoding 256-entry LUT से हर character को 0~15 value में map करता था
    • '0'..='9', 'A'..='F', 'a'..='f' को handle करता था
    • invalid characters को sentinel value से mark किया जाता था
  • \\u escape में 4 hex digits पढ़े जाते हैं, इसलिए पुराने तरीके में हर iteration पर shift, add, compare और conditional branch शामिल थे
  • बेहतर implementation में loop के दौरान हर बार error return नहीं किया गया, बल्कि सभी 4 digits process करने के बाद validity check की गई
  • अंतिम implementation [i8; 256] LUT से invalid digit को -1 रखकर 32-bit integer में calculation करता है
    • success पर result negative नहीं होता, और failure पर negative हो जाता है
    • x86 पर memory load और sign extension को movsx में combine किया जा सकता है
  • shift latency घटाने के लिए दो tables इस्तेमाल किए गए
    • HEX0: original value
    • HEX1: value को पहले से 4 bits left shift किया हुआ table
  • loop को साफ़ तौर पर unroll किए गए decode_four_hex_digits() implementation में व्यवस्थित किया गया
  • इस optimization से रूसी War and Peace को JSON-encoded form में parse करने की performance 284 MB/s से 344 MB/s तक पहुँची, यानी 21% improvement

UTF-8 encoding bottleneck और manual generation

  • Unicode escape decoding के बाद bottleneck UTF-8 encoding पर शिफ्ट हो गया
  • UTF-8 codepoint को उसकी length के अनुसार 1~4 bytes में encode करता है
    • 1 byte: 0xxxxxxx
    • 2 bytes: 110xxxxx 10xxxxxx
    • 3 bytes: 1110xxxx 10xxxxxx 10xxxxxx
    • 4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • Rust standard library का char::encode_utf8 &mut [u8] buffer में लिखता है, इसलिए buffer में पहले से valid u8 values होनी चाहिए
    • इसे uninitialized buffer में सीधे नहीं लिखा जा सकता
    • UTF-8 variable-length encoding है, इसलिए LLVM के लिए अनावश्यक zeroization हटाना मुश्किल होता है
  • serde_json इसे scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes()) तरीके से handle करता था
    • local [0u8; 4] buffer सैद्धांतिक रूप से alias analysis में मदद कर सकता था
    • लेकिन व्यवहार में 1~4 byte variable-length copy के कारण LLVM memcpy call generate करता था
  • memset और memcpy calls से बचने के लिए UTF-8 को सीधे generate किया गया
    • algorithm ख़ुद simple था, लेकिन इसके लिए unsafe की ज़रूरत पड़ी
    • कुछ छोटे बदलावों के साथ War and Peace benchmark 344 MB/s से 374 MB/s तक, अतिरिक्त +9% सुधरा

अंतिम परिणाम

  • string-heavy JSON benchmarks में serde_json performance क्रमशः 10%, 23%, 32% सुधरी
  • बहुत-सा JSON data strings से भरा होता है, इसलिए यह optimization serde_json इस्तेमाल करने वाले पूरे Rust codebase को प्रभावित कर सकती है
  • सुधार error position calculation, string escape search, Unicode escape decoding, और UTF-8 encoding जैसे अलग-अलग bottlenecks को क्रमवार हटाकर हासिल किए गए

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-08-25
Hacker News राय

  • UTF-8 ट्रिक को लेकर थोड़ी बेचैनी है, क्योंकि parser confusion attacks बहुत देखे हैं
    serde को लोग speed से ज़्यादा correctness के लिए इस्तेमाल करते हैं, इसलिए उम्मीद है कि उन्होंने ढेर सारी invalid UTF-8 strings डालकर अंत तक fuzzing की होगी

    • अच्छी बात है कि UTF-8 की structure औसत parser की तुलना में काफी सरल है
      इसका मतलब यह नहीं कि bug नहीं हो सकता, लेकिन parser की internal state बड़ी नहीं होनी चाहिए और exhaustive test भी संभव लगता है
    • ऐसे area में तो मैं सच में fuzzer चलाने के नतीजे देखना चाहूंगा
    • इस तरह के bug का कोई उदाहरण तुरंत याद आता हो तो बता सकते हो?

  • serde का इतनी तेजी से आगे बढ़ना शानदार है
    अभी simdutf8 देख रहा था, और पता चला कि SIMD-supported UTF-8 parsing वाला PR लगभग 5 साल से पड़ा है
    https://github.com/rust-lang/rust/issues/68455

  • इस व्यक्ति के blog में मजबूत jart वाली vibe लगी, इसलिए पढ़ना मजेदार रहा
    “wheel को फिर से invent करना पड़ेगा, लेकिन सोचें तो यह काफी बढ़िया है” वाला हिस्सा सच में कहा गया है या irony है, समझ नहीं आया
    पढ़कर author पर हंसते हुए हंसी आई, लेकिन बाकी page में self-deprecation काफी मजबूत दिखती है

    • मेरा खयाल है उसका मतलब wheel को फिर से invent करना पड़ेगा यह fact नहीं, बल्कि approach काफी बढ़िया है
    • jart का मतलब क्या है?

  • “सोचना कैसे है यह सिखाना coding सिखाने जितना ही जरूरी है, लेकिन यह लगभग होता ही नहीं” — इसमें तो अहंकार झलकता है कि सामने वाला सोचता ही नहीं

    • मुझे उस वाक्य में अहंकार नहीं दिखता
      यह मानना नहीं है कि दूसरे लोग सोचते नहीं; बल्कि यह observation है कि ज्यादातर blog posts और how-to articles सिर्फ final result दिखाते हैं, वहां तक पहुंचने के steps नहीं दिखाते
    • author ऐसा दावा नहीं कर रहा
      सोचने का तरीका सिखाने का मतलब है कि research करनी पड़ती है और उस step को skip नहीं किया जा सकता; और research कर लेने से खुद निष्कर्ष निकालने की जिम्मेदारी भी खत्म नहीं होती
      दोनों में से कोई एक skip करना आसान है, लेकिन गलत तरीका है

  • serde_json में debug build और release build एक-एक बार करने पर dependencies 3GB तक हो जाती हैं
    कुछ active projects में serde इस्तेमाल करो तो disk space खत्म हो जाता है
    JSON parsing के लिए 3GB dependencies क्यों चाहिए, समझ नहीं आता; code reuse से सहमत हूं, लेकिन serde की JSON-side dependencies काफी messy लगती हैं
    उन dependencies में से किसी एक में exploit आ गया तो Rust ecosystem का आधा हिस्सा vulnerable हो जाएगा
    Rust में JSON built-in होना चाहिए

    • dependencies सिर्फ 5 हैं, उनमें से एक optional है और दूसरी खुद serde है: https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      जब आप 3GB dependencies कह रहे हैं, तो संभव है कि आपने असल में वह चीज़ measure नहीं की हो
      आप बिना evidence के इसे fact की तरह कह रहे हैं, इसलिए पक्का नहीं कह सकता, लेकिन अंदाजा लगाऊं तो शायद आपने #[derive(Serialize, Deserialize)] बहुत इस्तेमाल किया, जिससे भारी मात्रा में code generate हुआ, और फिर पूरे target directory का size measure कर रहे हैं
      simple build, जैसा दूसरे comments ने दिखाया, कुछ दर्जन MB के आसपास आता है
    • मुझे नहीं लगता Rust में JSON को built-in करना reasonable approach है
      वह सिर्फ bloat को भीतर लाने का तरीका होगा, और standard library stability guarantees के अलावा दूसरी crates से अलग नहीं है, इसलिए कोई खास फायदा नहीं
      आखिर में बस library release cycle को compiler release cycle से बांधने का असर होगा
      वास्तव में पहले rustc-serialize built-in के करीब था, और Rust ने वह दिशा पहले ही आजमा ली है
      और default state में serde_json बड़ा नहीं है
      न serde_json बड़ा है, न serde; दोनों बहुत low MSRV maintain करते हैं जिसे दूसरी crates अच्छे से support नहीं करतीं, इसलिए व्यवहार में इनके पास बहुत सारी dependencies हो भी नहीं सकतीं
    • dependency bloat Rust में व्यापक समस्या है
      थोड़े भी बड़े Rust project की dependency tree जल्दी ही काफी डरावनी हो जाती है, इन सभी dependencies का audit करना realistic नहीं है, और उनमें से कई पर भरोसा भी कम है
      कई साल Rust में काम करने के बाद लगता है कि ecosystem के काफी mature होने तक शायद Rust को फिर हाथ नहीं लगाऊंगा
      वह maturity बड़े enterprise adoption से आएगी; नहीं तो no-std, no-deps, pure C replacement projects में ही इस्तेमाल करूंगा
      हालांकि Zig stable हो गया तो इस use case में भी Rust को हटा सकता है
    • Rust असामान्य रूप से बहुत ज्यादा debug info निकालता है
      यह इतना अजीब तरह से बड़ा है कि मुझे लगता है यह बस bug होगा
      आप कुछ भी compile करें, target folder में gigabytes भर जाते हैं, लेकिन यह debug info हटाने या कम से कम कम detailed setting इस्तेमाल करने के बाद final artifact को represent नहीं करता
    • कुछ हद तक बड़े project में target folder सचमुच हमेशा कम-से-कम कुछ GB का ही लगता है