AST और compiler data structure flattening

(cs.cornell.edu)

3 पॉइंट द्वारा GN⁺ 2023-07-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें

AST को pointer से जुड़े object graph के रूप में रखने के बजाय एक single array और index से represent करने पर compiler-style data structures का memory layout और management सरल हो जाता है
Rust example में Box<Expr> को ExprRef से बदलने और ExprPool में add/get जोड़ने जैसे छोटे बदलाव से flattened AST implement किया गया
लगभग 100 million AST nodes बनाकर तुरंत interpret करने वाले microbenchmark में सामान्य implementation 3.1 सेकंड और flattened implementation 1.3 सेकंड रहा, यानी 2.4× तेज
performance gap लगातार memory layout से मिलने वाली locality, 64-bit pointer के बजाय 32-bit index इस्तेमाल करने वाले छोटे reference, सस्ती allocation और pool-level deallocation से आता है
array में child अपने parent से पहले स्थित होता है इस property का उपयोग करने पर recursive tree traversal linear execution में बदल जाता है, और यह bytecode interpreter जैसे रूप के करीब पहुंचता है

Flattening का basic idea

Arena या region आधुनिक language implementations में व्यापक रूप से इस्तेमाल होते हैं, और यहां चर्चा की गई approach एक ही type रखने वाले arena को simple array की तरह इस्तेमाल करने वाली data structure flattening है
यह pointer-heavy data structures में pointers को array indices से बदलने की technique है; मुख्य example AST है, लेकिन इसे दूसरे compiler data structures पर भी लागू किया जा सकता है
example code flatcalc repository में है, और normal implementation व flattened implementation का अंतर branch comparison में देखा जा सकता है
code changes छोटे हैं, लेकिन microbenchmark में 2.4× speedup दिखा, और performance के अलावा code usability के लिहाज से भी फायदे हैं

सामान्य AST representation

example language बहुत simple arithmetic expression language है जो integer literals और चार binary arithmetic operators ही support करती है
- possible program examples 42, 0 + 14 * 3, (100 - 16) / 2 हैं
Rust representation BinOp और Expr enum से बना है
- Expr::Binary(BinOp, Box<Expr>, Box<Expr>)
- Expr::Literal(i64)
Rust का Box<Expr> Expr की ओर इशारा करने वाले pointer के बराबर है, और C के Expr* जैसी भूमिका निभाता है
parser, output formatter और interpreter typical structure वाले हैं, और interpreter Expr पर recursive method के रूप में लिखा गया है
arithmetic semantics ऐसे बनाए गए हैं कि सभी expressions आखिर में i64 में evaluate हों
- addition, subtraction और multiplication wrapping operations इस्तेमाल करते हैं
- division by zero को checked_div के जरिए 0 return करने के लिए handle किया गया है
fixed PRNG seed वाले random program generator से parsing और output cost के बिना AST manipulation performance मापी गई

AST को array और index में बदलना

flattening दो बदलावों से बनी है
- Expr objects को heap पर अलग-अलग allocate करने के बजाय एक continuous array में store किया जाता है
- child nodes को pointer के बजाय array के भीतर index से reference किया जाता है
Rust example में ExprPool को Vec<Expr> के newtype के रूप में define किया गया है

struct ExprPool(Vec<Expr>);

पुरानी pointer भूमिका 32-bit integer based ExprRef निभाता है

struct ExprRef(u32);

core type change Binary के child fields को Box<Expr> से ExprRef में बदलना है

enum Expr {
    Binary(BinOp, ExprRef, ExprRef),
    Literal(i64),
}

ExprPool में नया Expr डालने के लिए add और ExprRef से Expr खोजने के लिए get utility जोड़ी जाती है
parser सीधे Expr return नहीं करता, बल्कि ExprPool में node जोड़ने के बाद ExprRef return करता है
interpreter भी Expr method नहीं, बल्कि ExprPool method बन जाता है, और pattern matching से पहले self.get(expr) से reference को dereference करता है
पूरा बदलाव Box<Expr> को ExprRef में बदलने और जरूरी जगहों पर add व get डालने जितना छोटा है

Performance benefits

flattened AST का प्रमुख फायदा memory locality है
- सामान्य pointer-based Expr में memory fragmentation का risk होता है
- flattened Expr continuous memory region में compact रहते हैं, जिससे data cache और prefetcher बेहतर काम कर सकते हैं
- काफी smart memory allocator भी similar effect दे सकता है, लेकिन dense array इस्तेमाल करने से uncertainty घटती है
reference size भी घटता है
- सामान्य pointer आधुनिक architectures में 64-bit होता है
- अगर 4,294,967,295 या उससे कम AST nodes ही चाहिए, तो 32-bit reference पर्याप्त है
- हर reference पर 50% space saving संभव है, और pointer-heavy AST में इससे overall memory usage कम हो सकता है
- छोटे data structures के लिए 16-bit या 8-bit references भी संभव हैं
allocation cost कम हो जाती है
- हर node के लिए malloc call करने की जरूरत नहीं
- अगर पर्याप्त memory पहले से reserve की गई है, तो tail pointer बढ़ाने वाली bump allocation से नए Expr के लिए space बनाया जा सकता है
deallocation pool-level पर handle की जा सकती है
- इसमें यह assumption है कि individual Expr free नहीं किए जाते
- कई language implementations में AST साथ में बनते और साथ में खत्म होते हैं
- सामान्य AST में pointers follow करके हर node को free करना पड़ता है, जबकि flattened AST में पूरे ExprPool को एक बार में free किया जा सकता है
Arena allocation introductions में सस्ती deallocation को अक्सर main reason के रूप में highlight किया जाता है, लेकिन compiler environment में AST compilation के अंत तक रखा जा सकता है, इसलिए deallocation सबसे कम important reason भी हो सकता है

Code usability benefits

flattening lifetime management को सरल बनाती है
- n nodes वाले AST को n lifetimes के बजाय एक AST lifetime के रूप में सोच सकते हैं
- Rust में यह simplification code के lifetime representation पर भी सीधे असर डालती है
- &Expr lifetimes manage करने के बजाय u32 वाले ExprRef pass किए जा सकते हैं और ExprPool की lifetime पर निर्भर रहा जा सकता है
यही simplicity C++ जैसी manual memory management वाली languages में भी लागू हो सकती है
flattened array में deduplication implement करना आसान है
- hash consing या अधिक simple तरीके से identical expressions बनने से बचा जा सकता है
- उदाहरण के लिए 0 से 127 तक अक्सर इस्तेमाल होने वाले Literal expressions को ExprPool के पहले 128 slots में reserve किया जा सकता है
- integer literal 42 चाहिए तो नया Expr बनाने के बजाय ExprRef(42) return किया जा सकता है
pointer-based representation में भी ऐसा treatment संभव है, लेकिन auxiliary data structure की जरूरत पड़ने की संभावना ज्यादा है

Microbenchmark results

benchmark ने लगभग 100 million AST nodes वाला random program generate किया और उसे सीधे interpreter में input किया
- parser और output formatter शामिल नहीं हैं
- एक program generate करके तुरंत execute करने का तरीका है, इसलिए यह realistic benchmark नहीं है
experiment conditions में कुछ limitations हैं
- Vec<Expr> में पूरा program रखने के लिए पर्याप्त space पहले से reserve किया गया
- real environment में arena size estimation की और जरूरत होगी
- generation और execution के अलावा बहुत कम काम है, इसलिए cheap allocation/deallocation का फायदा exaggerated हो सकता है
- program इतना बड़ा है कि CPU cache में फिट होने वाला हिस्सा छोटा है, इसलिए locality effect under-estimated हो सकता है
Hyperfine से laptop पर 10 runs का average compare किया गया
- environment M1 Max 10-core 3.2GHz, 32GB memory, macOS 13.3.1, Rust 1.69.0 था
normal implementation में 3.1 सेकंड, flattened implementation में 1.3 सेकंड लगे, यानी 2.4× speedup दिखा
deallocation cost अलग से देखने के लिए दोनों implementations में deallocation skip करने वाला version बनाया गया
- flattened implementation में no-free version और standard version का time लगभग समान था, इसलिए deallocation time बड़ा नहीं था
- normal implementation 3.1 सेकंड से घटकर 1.9 सेकंड हो गया, यानी लगभग 38% memory deallocation में खर्च हो रहा था
- no-free versions की तुलना में भी flattened implementation normal implementation से 1.5× तेज है

Flattened representation का सीधे उपयोग करने वाला interpreter

flattening शुरू में normal allocation और pointers को replace करने वाला internal implementation change जैसा इस्तेमाल हुआ, लेकिन array representation की properties को सीधे भी use किया जा सकता है
अगर Expr immutable है, तो child nodes पहले और parent nodes बाद में बनाने होंगे
- a * b बनाते समय a और b, उन्हें reference करने वाले * से ExprPool में पहले स्थित होते हैं
- reference arrows array में हमेशा पीछे से आगे की ओर जाते हैं, और data flow आगे बढ़ता है
इस invariant का उपयोग करके root से recursively नीचे जाने के बजाय ExprPool को शुरू से अंत तक scan करने वाला interpreter बनाया जा सकता है
- traversal हमेशा children को parent से पहले visit करता है
- हर expression का result state vector में store किया जाता है
- binary expression child ExprRef indices से state lookup करके values लाता है
- अंत में requested root के अनुरूप result return करता है
यह “extra-flat” interpreter recursive calls की stack management नहीं करता और ExprPool को linearly traverse कर सकता है
दूसरी ओर, बड़े state vector पर random access करना पड़ता है, इसलिए locality के लिए नुकसानदेह भी हो सकता है
परिणामस्वरूप extra-flat interpreter 1.2 सेकंड और recursive-based flattened interpreter 1.3 सेकंड रहा, यानी 8.2% improvement

Bytecode interpreter से connection

Bob Nystrom की Reddit comment के अनुसार यह approach दरअसल bytecode interpreter idea को फिर से बनाती है
Expr struct bytecode instruction की तरह काम करता है, और variable references u32 में encoded references की तरह शामिल होते हैं
simple state table को stack जैसी structure में बदल दें, तो यह शुरू से design किए गए bytecode interpreter से लगभग अलग नहीं रहता
सिर्फ AST data structure बदलने के बावजूद tree traversal style से bytecode style की ओर naturally move हो जाता है

Related resources

compiler context में flattening से जुड़े resources
- Mike Pall ने LuaJIT performance के कुछ हिस्से को “linear, pointer-free IR” का credit दिया
- Ruby के लिए Sorbet typechecker performance समझाने वाली post packed array और 64-bit pointer को 32-bit index में बदलने के फायदे पर जोर देती है
- Oil shell project compact AST representation links collection प्रदान करता है
language implementation के बाहर performance-oriented क्षेत्रों में भी similar ideas आते हैं
- Purdue और Indiana का Gibbon सामान्य code जैसा दिखने वाले program को flattened implementation में ले जाने के काम के करीब है
- Andrew Kelley data-oriented design talk में pointer के बजाय index इस्तेमाल करने की approach पर चर्चा करते हैं
- Rust arena library overview post arena-related lifetime usability को cover करती है
- game development की handle vs pointer comparison post same-type objects को array में collect करके index से reference करने की approach का समर्थन करती है
- ECS-related posts locality से जुड़े topics पर चर्चा करती हैं
Inanna Malick की Rust toy calculator language post भी यही technique apply करती है, और Haskell world के recursion scheme ideas भी साथ इस्तेमाल करती है

1 टिप्पणियां

GN⁺ 2023-07-04

Hacker News की टिप्पणियाँ

Blender(3D मॉडलिंग सॉफ़्टवेयर) इस तरीके का एक दिलचस्प उदाहरण है। फ़ाइल load/save को तेज़ और lossless बनाने के लिए यह disk पर मौजूद representation और memory में मौजूद representation को एक जैसा रखता है
यानी सब कुछ arena में होता है, और save/load लगभग पूरे arena को memcpy करने जैसा है। Blender प्रोजेक्ट की संभावित जटिलता और serialization/deserialization समस्याओं को देखते हुए, यह एक शानदार डिज़ाइन लगता है
कमी यह है कि पुराने version की फ़ाइलें भी खुलनी चाहिए, इसलिए data structure डिज़ाइन के जड़ हो जाने की संभावना रहती है
- “पुराने version की फ़ाइलें खोलनी पड़ती हैं, इसलिए data structure डिज़ाइन जड़ हो जाता है” वाली बात में जो हिस्सा छूटा है, वह है database migration की तरह data structure को समय के साथ evolve करने का तरीका
  ऐसे conversion सिर्फ तब चलाए जाते हैं जब पुराने app version का data load किया जाता है, और उसके बाद उसे तुरंत updated version में disk पर save कर दिया जाए तो वही लागत दोबारा नहीं चुकानी पड़ती
  CRDT संदर्भ में बना https://www.inkandswitch.com/cambria/ इस विचार के implementation का एक उदाहरण है, और सीधे लागू न हो तब भी अच्छी प्रेरणा दे सकता है
- मैंने एक बड़े commercial app पर काम किया था जो इसी तरह के सिद्धांत पर चलने वाले in-house I/O framework पर आधारित था, और वह सचमुच बहुत पीड़ादायक था
  I/O framework अच्छा हो या बुरा, वह structs को जस का तस serialize कर देता था, इसलिए हमेशा data structures को भविष्य के लिए तैयार करके बनाना पड़ता था क्योंकि पता था कि हमेशा उसी structure से बंधे रहेंगे। वह अँधेरा दौर था
- लगता है पुराने “doc” दौर का Microsoft Word भी structs को वैसे ही disk पर dump कर देता था
  इसी वजह से converters लिखना बड़ी समस्या बन गया था, और याद है कि undocumented Word internal data structures को reverse engineer करना पड़ता था
- जिस PlayStation game पर मैंने काम किया था, उसमें भी बिल्कुल यही तरीका था, और सब कुछ signed था इसलिए attackers की कोई चिंता ही नहीं थी
  अगर disk पर फ़ाइलें बदली जा सकती थीं, तो उसका मतलब था कि डिवाइस पहले से ही पूरी तरह compromise हो चुका है। इसी वजह से loading बेहद तेज़ थी, सब कुछ memory में पढ़ लेने के बाद pointers की जगह को बस वास्तव में loaded address पर patch कर दिया जाता था
- मेरी जानकारी में Microsoft Word ने भी शुरुआत में यही तरीका अपनाया था, और file format के evolve होने पर यह बहुत बड़ा दर्द बन गया
मुझे flattened abstract syntax trees बहुत पसंद हैं। pulldown-cmark के inline markup handling में इस्तेमाल किया गया तरीका खास तौर पर पसंद है। इसका एक सरल विवरण https://fullyfaithful.eu/pulldown-cmark/ में है
raw input को node sequence में तोड़ा जाता है, और * जैसी चीज़ें emphasis भी बन सकती हैं या अगर उनका pair न मिले तो text बनी रह सकती हैं, इसलिए उन्हें MaybeEmphasis node बनाया जाता है
अगले चरण में stack का इस्तेमाल करके nodes को क्रम से scan किया जाता है और संभव pairs खोजे जाते हैं। pair मिल जाने पर MaybeEmphasis node को उचित emphasis node में बदला जाता है, और opening node और closing node के बीच की पूरी node sequence को काटकर नए node की subtree बना दिया जाता है
यह tree transformation काफ़ी असामान्य है, इसलिए साधारण implementation आसानी से O(n) हो सकती है, लेकिन flattened AST representation में इसे node count या stack depth से स्वतंत्र O(1) में किया जा सकता है
tree representation का विवरण https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6... में है, जहाँ मूल रूप से node body के साथ child, next index रखे जाते हैं। emphasis matching के समय tree surgery का code https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6... में है
performance शानदार है। pulldown-cmark भले ही अकेला सबसे तेज़ CommonMark parser न हो, लेकिन यह काफ़ी competitive है, और उदाहरण के लिए हर node पर allocation करने वाले approach से बहुत तेज़ है
Rust की तारीफ़ करने वाली एक GDC प्रस्तुति याद आ गई। उसमें कहा गया था कि Rust आपको borrow checker की वजह से पागल कर देता है, या फिर कोड को entity component system के रूप में संरचित करने पर मजबूर करता है
मज़ेदार बात यह है कि जटिल lifetime समस्याओं वाले वास्तविक मामलों में borrow checker की असली उपयोगिता आखिरकार आपको यह रास्ता ढूंढने पर ले जाती है कि सब कुछ arrays में डालो और indices से refer करो, ताकि borrow checker से जितना हो सके बचा जा सके
- Bevy गेम इंजन के साथ Rust में थोड़ा काम करने के अपने अनुभव से कहूँ तो, entity component system ऐसा लगा जैसे बहुत हाई-एंड spaghetti code लिखा जा रहा हो
  ऑब्जेक्ट्स एक-दूसरे को सीधे refer नहीं करते, इसलिए type system की उपयोगिता काफी कम हो जाती है, और कोड को समझना बहुत मुश्किल हो जाता है। मुझे यकीन है कि बहुत बड़े systems में यह उपयोगी हो सकता है, लेकिन मैं जो छोटे programs लिख रहा था उनमें यह लगभग बाधा जैसा लगा
- सही। Rust के lifetimes उन खास high-performance programming क्षेत्रों में कमज़ोर पड़ जाते हैं जहाँ heap से बचा जाता है, या heap होता ही नहीं
  इसमें games, databases, embedded, high-performance computing शैली के batch jobs, और यहाँ तक कि compilers भी शामिल हैं
  बेशक aliasing पर पाबंदियाँ अब भी रहती हैं, इसलिए data races नहीं होंगी, लेकिन raw pointers से आने वाले bugs के मूलतः वही bugs अब भी हो सकते हैं
- दूसरे शब्दों में, इसे ऐसे देखा जा सकता है कि long-lived entities को memory own करनी होती है, और short-lived objects को वह उधार दी जाती है
  इस प्रक्रिया में उधार लेने वाला हमेशा owner से कम समय तक जीवित रहता है, और ownership के दौरान आवंटित memory तक ही पहुँच सकता है। owner के मरते ही memory free हो जाती है, और उसके बाद कोई भी उसे न इस्तेमाल कर सकता है न दोबारा free कर सकता है, इसलिए use-after-free, double free, और unallocated memory access से बचाव होता है
- सही। बार-बार ऐसा दिखता है कि arenas या flattened tree/graph structures की बात करते समय memory safety को छोड़ दिया जाता है
  C में arena memory safety समस्याएँ हल कर देता है, ऐसा अजीब दावा भी दिखता है, जबकि program के हिसाब से वही चीज़ dangling pointers या use-after-free जैसी समस्याएँ उतनी ही पैदा कर सकती है
  यही समस्या C/C++ और Rust दोनों में थोड़े अलग तरीके से सामने आती है
  दो महीने पहले इस लेख पर छोड़ी गई मेरी टिप्पणी: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
  संक्षेप में, फायदे बहुत व्यावहारिक हैं, लेकिन नुकसान की भी बात होनी चाहिए। arenas ownership को टाल देते हैं जिससे वह जटिल हो सकती है, mutation और list/vector additions भी पेचीदा हो जाते हैं, और pointer representation debugger के लिए अधिक अनुकूल होती है
  इस लेख के नीचे मेरे wiki page का लिंक है, जिसमें असली code और measurements हैं, इसलिए उसे आभार के साथ देखा: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
- Pointers बस memory space के indices ही हैं। अगर Rust सामान्य programming समस्याएँ हल करना चाहता है, तो लगता है कि borrow checker को सिर्फ memory space के लिए विशेष indices ही नहीं, बल्कि सभी indices को संभालना चाहिए
Prolog terms भी Warren Abstract Machine (WAM) में heap पर इसी तरह represent किए जाते हैं। लेख के उदाहरण की तरह अगर +(*(a,b), c) जैसे Prolog term को operator notation में लिखें, तो वह ऐसा होगा
expr(E) :- E = a*b + c.
तब virtual machine के global stack पर एक flattened representation बनती है। Scryer Prolog में ?- wam_instructions(expr/1, Is), maplist(portray_clause, Is). से WAM instructions देखे जा सकते हैं
परिणाम put_structure(*,2,x(3))., set_constant(a)., set_constant(b)., put_structure(+,2,x(2))., set_value(x(3))., set_constant(c)., execute(=,2). जैसा आता है
दोनों compound terms linearize हो जाते हैं और heap में functor के बाद arguments रखे जाते हैं, और उनमें से हर एक WAM के ठीक एक memory cell पर कब्ज़ा करता है। arguments दूसरे memory cells को point कर सकते हैं
heap ऐसे cells की एक array होती है, और सभी cells का concrete type एक ही होता है। उदाहरण के लिए Scryer Prolog हर cell के लिए 8 bytes इस्तेमाल करता है, इसलिए 64-bit architecture पर cell access और mutation बहुत efficient होते हैं
“heap पर Expr objects को इधर-उधर allocate करने के बजाय उन्हें एक continuous array में रखो, और children को pointers की जगह उस array के indices से refer करो” — यह flattening से ज़्यादा एक alternative heap representation जैसा है। AST का shape खुद नहीं बदला है
Lisp परिवार की भाषाओं की तरह cons cells और दूसरे objects को array में रखना, और bump allocation तथा index pointers का उपयोग करना, कई भाषाओं में पहले से होता आया है
जब objects array में होते हैं, तो mark पूरा होने के बाद garbage collector के लिए sweep phase में traversal आसान हो जाता है। mark phase graph पर चलकर reachable objects ढूंढता है, और sweep phase flat array से गुज़रते हुए GC bits साफ़ करता है और unreachable objects को reuse के लिए चिह्नित करता है
किसी भी हद तक गंभीर Lisp implementation में हर cons cell के लिए अलग से malloc बुलाया जाता हो, ऐसा ढूँढना मुश्किल होगा। अगर ऐसा किया जाए, तो GC के sweep phase के लिए या तो global linked list में डालना पड़ेगा, या सिर्फ pointers रखने वाली global array चाहिए होगी
weekend में बने toy Lisp projects में cons cells को malloc करके leak छोड़ देना और GC को एक विशाल TODO की तरह छोड़ देना मैंने कम से कम दो बार देखा है
भले ही cells compressed array heap से आएँ, global array फिर भी आखिरकार आ सकती है। उदाहरण के लिए non-copying allocator में generational garbage collection लागू करते समय young objects को इकट्ठा करके तेज़ GC cycles में sweep करने के लिए auxiliary array में जोड़ा जा सकता है, और वही array nursery को दर्शाती है
अच्छा लेख है, लेकिन इसमें दो तरह की पेचीदगियाँ हैं
1. अगर nodes को resize किए जा सकने वाले array में स्टोर किया जाए, तो input program बड़ा होने पर compiler को एक बड़ा continuous memory block चाहिए होगा। वह block उपलब्ध भी हो सकता है और नहीं भी। इसे page-size blocks allocate करके pool की तरह इस्तेमाल करने से टाला जा सकता है
2. code में AST nodes को कैसे represent किया जाता है, इस पर ध्यान देना चाहिए। उदाहरण के लिए, अगर nodes को union type में स्टोर किया जाए, तो union अपने सबसे बड़े member जितना बड़ा हो जाता है, और क्योंकि सभी AST nodes का आकार एक जैसा नहीं होता, छोटे nodes सबसे बड़े node के आकार के हिसाब से बेकार में padded हो जाते हैं
- यह बात कि छोटे AST nodes सबसे बड़े AST node के आकार की वजह से बेकार में padded हो जाते हैं, वास्तव में बहुत अच्छी point है, और मैंने user-defined bit-width integer types पर अपनी blog post में भी इसका ज़िक्र किया था: https://alic.dev/blog/custom-bitwidth
  tagged unions भी संभव हैं, लेकिन memory usage को समझदारी से संभालना पड़ेगा
- कभी-कभी लगता है, काश हम flat address space पर आकर न टिके होते
  “virtual memory” techniques बिखरे हुए physical memory regions को जोड़कर एक continuous virtual memory region बना सकती हैं। अगर virtual address space segmented होता, तो शायद fragmentation होती ही नहीं, और कोई भी memory region दूसरी region से टकराए बिना अपनी जगह पर हमेशा बढ़ सकता था
  तब realloc() implementation में memcpy() path हटाया जा सकता था, अफ़सोस
- vector को fixed-size chunks में बाँटने वाली rope जैसी structure और actual pointers के साथ इसे कम किया जा सकता है। तब reallocation की ज़रूरत नहीं रहेगी
  अंदरूनी हिस्सा सुरक्षित नहीं होगा, लेकिन read-only safe interface संभव लगता है। free करना O(n) होगा, लेकिन फिर भी tree से काफ़ी तेज़ होगा
यह जान लेने के बाद भी कि पहला pointer हमेशा ठीक अगले node की ओर इशारा करता है, यह देखकर हैरानी हुई कि node में अभी भी दो pointers (“references”) बचे हुए हैं
https://github.com/rswier/c4 को ऐसा approach इस्तेमाल करते देखा है। बेशक, code readability अच्छी नहीं है, लेकिन यह छोटा और तेज़ है
memory management में arena सुनते ही “flattening” से ज़्यादा सीधा arena allocator याद आता है
जब एक जैसी lifetime वाले बहुत सारे items allocate करने हों, तो एक या अधिक बड़े memory chunks से ज़्यादा efficient allocation किया जाता है, और shared lifetime खत्म होने पर individual items की बजाय उन बड़े chunks को free कर दिया जाता है
क्योंकि parent chunk की जगह को बस क्रम से इस्तेमाल करना होता है, इसलिए general-purpose heap allocator की तरह free list की ज़रूरत नहीं होती, और allocation ज़्यादा efficient हो सकता है
इस संदर्भ में pointers की जगह indices का इस्तेमाल करने वाली “flattening” को parent chunk के आधार पर relative pointers, यानी offsets, का उपयोग भी माना जा सकता है
memory बहुत सीमित embedded environment के लिए बने JavaScript parser और interpreter V7(https://github.com/cesanta/v7) को implement करते समय ऐसी compact AST structure का इस्तेमाल किया था
बाद में इसे AST से bytecode में compile करने वाले चरण में बदल दिया गया, लेकिन कुछ समय तक implicit AST को interpret करते हुए सीधे traverse किया गया
https://yaml2sql.netlify.app पर मौजूद मेरे Yaml to Sql compiler में भी कुछ ऐसा ही किया था
flattening process थोड़ी अजीब है, लेकिन दिलचस्प है, और अंत में यह लगाए गए effort के लायक साबित हुई
उदाहरण के लिए, boolean expression flattening इसे आज़माना चाहने वालों के लिए एक अच्छा अभ्यास है: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...

AST और compiler data structure flattening

Flattening का basic idea

सामान्य AST representation

AST को array और index में बदलना

Performance benefits

Code usability benefits

Microbenchmark results

Flattened representation का सीधे उपयोग करने वाला interpreter

Bytecode interpreter से connection

Related resources

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

1 टिप्पणियां

Hacker News की टिप्पणियाँ