Rust arena से Gleam की 3 साल पुरानी performance समस्या हल करना

 (giacomocavalieri.me)
1 पॉइंट द्वारा GN⁺ 6 시간 전 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Gleam formatter की recursive Document संरचना में बार-बार होने वाली अलग-अलग heap allocation को arena-आधारित references से बदलकर, 3 साल से लंबित performance improvement issue को हल किया गया
  • Box<Self> को arena में stored &Self से replace किया गया, और Rust की lifetime checking यह सुनिश्चित करती है कि arena हटने के बाद अंदरूनी data को refer न किया जाए
  • language keywords और comma जैसे बार-बार दोहराए जाने वाले सैकड़ों Document को सिर्फ एक बार allocate करके reuse करने से pretty printer का execution time 13ms से घटकर 9.8ms हो गया, यानी 24% तेज
  • source read और parsing सहित पूरे gleam format execution time में भी 13% कमी आई, और peak memory usage 8.4MB से घटकर 7.6MB हो गया, यानी लगभग 10% कम
  • arena pass करने के लिए functions और call sites में बड़े पैमाने पर बदलाव करने पड़े, इसलिए +2963/-1032 स्तर का manual काम करना पड़ा, लेकिन बार-बार होने वाली individual allocation कम करने के तरीके से speed और memory usage दोनों में सुधार हुआ

recursive Document संरचना में allocation लागत

  • Gleam का pretty printer यह दिखाने के लिए recursive Document data structure का उपयोग करता है कि code कैसे output हो, और line limit पार होने पर कहाँ break किया जाए
  • इसके मुख्य variant में output string रखने वाला String, line break से पहले और बाद की string को define करने वाला Break, कई documents को group करने वाला Group, और line break होने पर indentation बढ़ाने वाला Nest शामिल हैं
  • list [1, 2] को भी String, Break, Nest, Group के combination से represent किया जाता है
    • अगर वह current line में fit हो जाए, तो [1, 2] की तरह एक ही line में output होता है
    • अगर line limit पार हो जाए, तो तय किए गए Break के अनुसार कई lines में break किया जाता है, indentation दी जाती है, और आख़िरी comma भी print होता है
  • Nest जैसे वे variant जो अपने अंदर दूसरे Document रखते हैं, पहले Box<Self> का उपयोग करते थे, इसलिए हर nested document के लिए heap पर अलग allocation करनी पड़ती थी, और यह काम execution time का बड़ा हिस्सा ले सकता था
  • Gleam pretty printer का आधार algorithm Strictly Pretty paper में देखा जा सकता है

Box को arena references से replace करना

  • पहले के Nest(Box<Self>) को Nest(&'doc Self) में बदलकर संरचना को इस तरह बदला गया कि वह arena में stored दूसरे Document को reference करे
  • references रखने के लिए string lifetime 'string के अलावा document data lifetime 'doc को Document में जोड़ा गया
  • implementation में typed_arena crate का उपयोग किया गया
    • alloc से किसी value को arena में store करने पर उस value का reference वापस मिलता है
    • allocated data को arena के जीवित रहने तक उपयोग किया जा सकता है
    • arena scope से बाहर होने पर उसके अंदर का data भी साथ में हट जाता है
  • alloc(&self, value: T) -> &mut T से लौटने वाला reference arena से ज़्यादा समय तक जीवित नहीं रह सकता, और Rust का borrow checker arena हटने के बाद होने वाले invalid references को रोकता है

दोहराए जाने वाले documents को एक बार allocate करके reuse करना

  • arena का उपयोग सिर्फ दूसरे documents को reference करने के लिए नहीं, बल्कि पूरे codebase में बार-बार आने वाले Document को cache करने के लिए भी किया गया
  • String("fn"), String("pub"), String("type") जैसे language keywords को दर्शाने वाले documents अब हर बार नए बनाने की ज़रूरत नहीं रही
  • list items के बीच उपयोग होने वाले Break { unbroken: ", ", broken: "," } जैसे documents भी एक बार allocate करके reuse किए गए
  • पहले जिन सैकड़ों छोटे documents को लगातार Box में डालना पड़ता था, अब उनमें से हर एक को सिर्फ एक बार allocate करना संभव हो गया

सरल API, लेकिन call sites में व्यापक बदलाव

  • arena API अपने-आप में सरल है, लेकिन existing code के बड़े हिस्से को बदलने की प्रक्रिया में बार-बार manual edits करने पड़े
  • जो functions पहले सिर्फ Box::new call करते थे, अब उन्हें data allocate करने के लिए अतिरिक्त arena argument लेना पड़ता है
  • format_list जैसे functions अब list items को format करने वाले child functions तक भी वही arena pass करते हैं, और nested documents को Box::new की जगह arena.alloc से बनाते हैं
  • कई दिनों तक सावधानी से search-and-replace करने के बाद यह काम +2963/-1032 आकार के pull request के रूप में पूरा हुआ
  • यह दोहराव वाला और manual काम था, और इस प्रक्रिया में LLM का उपयोग नहीं किया गया

speed और peak memory usage में सुधार

  • वास्तविक Gleam project squirrel को format करते समय pretty printer का execution time 13ms से 9.8ms तक घट गया
    • सिर्फ pretty printer की तुलना करें तो यह 24% performance improvement है
  • gleam format formatting के अलावा project source code को पढ़ता और parse भी करता है, इसलिए pretty printer पूरे काम का सिर्फ एक हिस्सा है, फिर भी कुल execution time में 13% कमी आई
  • peak memory usage 8.4MB से 7.6MB तक घट गया, यानी लगभग 10% कम
  • arena के ज़रिए individual heap allocations की संख्या घटाने के नतीजे में formatter की execution speed बढ़ी और memory usage भी कम हुआ

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

1 टिप्पणियां

 
GN⁺ 6 시간 전
Lobste.rs की रायें

  • अगर आप peak memory usage को और 10% घटाना चाहते हैं, तो references के बजाय opaque handles लौटाने वाले किसी दूसरे arena पर विचार किया जा सकता है। Handles को 64-bit के बजाय 16-bit या 32-bit बनाया जा सकता है, इसलिए बहुत सारे छोटे allocations होने पर इसका असर बड़ा होता है
    https://donsz.nl/blog/arenas/ के अनुसार, इसे support करने वाला crate सिर्फ compact_arena है, लेकिन अगर वह जरूरतों के मुताबिक न हो तो इसे खुद implement करना भी मुश्किल नहीं है

    • opaque handles इस्तेमाल करने पर data को और घना करके store भी किया जा सकता है। निजी प्रोजेक्ट columnar Option<T> की list को प्रति item करीब 1 bit के presence marker और वास्तव में मौजूद items के T में बांटकर store करता है
      बदले में reference type के रूप में &Option<T> नहीं बल्कि Option<&T> लौटाता है, और ज्यादा सामान्य तौर पर कहें तो structural recursion के अंदर reference रखने के बजाय reference को follow करते हुए structurally recurse करने का तरीका है
    • वह लेख 2 साल पहले की जांच पर आधारित था और सभी crates को पूरी तरह cover नहीं करता, इसलिए अगर कोई गलती या छूटी हुई नई library मिले तो PR भेज सकते हैं
      arenas ज्यादा व्यापक रूप से इस्तेमाल किए जाने लायक हैं, और handles या smart pointers के बजाय references लौटाने से Rust में recursive enum pattern matching बहुत आसान हो जाती है। आम तौर पर if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {} जैसा लिखने की कोशिश करें तो बीच के box या pointer की वजह से यह संभव नहीं होता, लेकिन references को nightly feature के बिना transparently pattern match किया जा सकता है। अगर सभी references एक ही arena की ओर point करते हैं, तो पूरे tree को जोड़ने वाली lifetime भी लगातार बनी रहती है
    • नतीजे अच्छे रहे, इसलिए compiler के दूसरे हिस्सों को भी arena तरीके में बदलने पर विचार किया जा रहा है, और इस approach पर आगे भी नजर रखी जाएगी

  • यह तरीका एक और Wadler-style pretty-printing library pretty द्वारा support किए गए approach से काफी मिलता-जुलता है। हालांकि कई memory allocation strategies support करने की वजह से API कुछ भारी-भरकम लग सकती है

  • लेख में उद्धृत paper के लेखक का Brunswick की एक आम IT company में काम करना चौंकाने वाला है

    • यही open source की खूबसूरती है। expertise और रोजी-रोटी का अक्सर आपस में बहुत ज्यादा संबंध नहीं होता