Zig में memory-efficient enum arrays

 (alic.dev)
3 पॉइंट द्वारा GN⁺ 2023-09-19 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • अलग-अलग size वाले variant के साथ enum/tagged union को बड़ी मात्रा में store करने पर, सबसे बड़े variant के हिसाब से space reserve होने की वजह से Vec·HashMap में padding और fragmentation की लागत बढ़ जाती है
  • Zig, comptime और type reflection के जरिए field size·alignment·discriminant की जांच कर सकता है, और enum container को memory layout के आधार पर generic तरीके से बदल सकता है
  • साधारण Vec<Enum> में हर element अधिकतम variant size जितनी जगह लेता है, और SoA tag padding को घटाता है, लेकिन value क्षेत्र की variant fragmentation बनी रहती है
  • समान size वाले variant को group करने वाला dense AoVA उदाहरण enum में 15 vector को 2·4·8 byte के 3 cluster तक घटा देता है, लेकिन एक ही allocation में कई variant mix होने पर type-safe iteration मुश्किल हो जाती है
  • Rust proc macro के लिए type size·alignment जानकारी तक पहुंचना कठिन है, और generic array length की गणना में भी सीमाएं हैं; इसलिए Zig का type-aware staging system code में memory-efficient composability को बेहतर ढंग से दिखाता है

Rust enum arrays जगह क्यों बर्बाद करते हैं

  • अलग-अलग size वाले variant के साथ enum/tagged union को इतना memory reserve करना पड़ता है कि वह सबसे बड़े variant को समेट सके
  • उदाहरण enum Foo में u8, u16, u32, u64 variant हैं, और tag व alignment की वजह से type size 16 byte हो जाती है
  • ऐसे enum को Vec या HashMap में बड़ी संख्या में रखने पर हर element सबसे बड़े variant के हिसाब से space लेता है, जिससे padding और fragmentation बढ़ती है
  • tag को अलग allocation में रखने वाला struct of arrays(SoA) रूपांतरण कुछ padding कम कर सकता है, लेकिन variant size के अंतर से बनने वाली value क्षेत्र की fragmentation को पूरी तरह नहीं हटाता
  • Rust में किसी खास enum के लिए data structure हाथ से बनाना संभव है, लेकिन किसी भी arbitrary enum के लिए अधिकतम memory-efficient generic data structure बनाना मुश्किल है, या व्यावहारिक रूप से लगभग असंभव के करीब है
    • proc macro के लिए third-party type या type alias पर #[derive] लगाना कठिन है और composability कम है
    • इसमें type awareness नहीं है, और generic_const_expr आधारित workaround verbose where clauses को call graph में फैला देता है और generic type parameter के साथ अच्छी तरह फिट नहीं बैठता

Compiler AST में यह समस्या ज्यादा स्पष्ट क्यों होती है

  • efficient enum arrays की बड़ी motivations में से एक compiler AST की memory usage है
  • बड़े AST compilation के दौरान memory latency और cache eviction पैदा करते हैं, जिससे frontend performance पर बड़ा cost पड़ता है
  • Chandler Carruth के Carbon compiler वीडियो में कहा गया है कि parsed clang AST कई बार मूल source code से 50 गुना ज्यादा memory consume करता है
  • Rust में expression node को दर्शाने वाला उदाहरण Expr enum से बना है
    • Unit
    • Number
    • Binary(Operation, ExprId, ExprId)
    • Ident(Symbol)
    • Eval(ExprId, ExprSlice)
    • BlockExpression(ExprId, StatementSlice)
  • OCaml में runtime system और GC memory management संभालते हैं, इसलिए explicit indirection के बिना recursive data type व्यक्त किए जा सकते हैं
  • Rust का Vec<Expr> हर element के लिए sizeof(Enum) जितनी जगह लेता है, जिसमें सबसे बड़े variant का size, tag और padding शामिल होते हैं

SoA और AoVA से fragmentation कम करना

  • जब एक साधारण 3-variant enum में 8·16·32-bit size के member हों, तब सामान्य Vec 32-bit variant और alignment requirement के हिसाब से हर element के लिए बड़ी space reserve करता है
  • एक आम सुधार यह है कि enum variant को खुद छोटा रखा जाए, जैसे tagged index का उपयोग करके
    • Rust compiler का tagged_index crate
    • small-string optimization के उदाहरण
    • language runtime, GC, compiler, game engine, OS kernel जैसे high-performance code में यह optimization अक्सर इस्तेमाल होती है
  • container को बदलकर discriminant और value को अलग allocation में store करने वाला SoA तरीका भी संभव है
    • self-hosted Zig compiler इसी तरीके का उपयोग करता है
    • tag से आने वाली padding घटती है, लेकिन union value collection में variant fragmentation फिर भी बनी रहती है
  • Zig का staged compilation arbitrary type के लिए SoA transformation करने वाले container को generic रूप से बना सकता है
  • Rust को soa_derive जैसे proc macro पर निर्भर होना पड़ता है, और third-party type का source बदले बिना #[derive] नहीं जोड़ा जा सकता — यह एक सीमा है

Variant-वार arrays और size-आधारित clustering

  • value क्षेत्र की fragmentation को और कम करने के लिए हर variant के लिए एक vector रखा जा सकता है
  • insert करते समय enum tag और उस variant array के index को साथ रखने वाला tagged index लौटाया जाता है
  • इस pattern को array of variant arrays(AoVA) कहा जाता है
  • AoVA को Rust में proc macro और Zig में comptime से implement किया जा सकता है
  • अगर variant बहुत हों और एक ही size वाले variant भी कई हों, तो variant-वार vector की संख्या जरूरत से ज्यादा बढ़ जाती है
    • उदाहरण Foo enum में 15 variant हैं
    • variant-वार vector approach में 15 vector और जुड़ते हैं
    • reallocation और system call की संख्या बढ़ सकती है, और naive Vec की तुलना में amortization के लिए ज्यादा memory चाहिए हो सकती है
    • vector memory में बेतरतीब बिखर सकते हैं, जिससे cache conflict की संभावना बढ़ती है
    • AoVA container खुद भी काफी memory ले सकता है, जिससे शामिल struct का आकार बढ़ जाता है
  • size के आधार पर group करने पर उदाहरण enum 2 byte, 4 byte, 8 byte के तीन cluster में बंट जाता है
    • c_2: Vec<[u8; 2]> में A से D तक store होते हैं
    • c_4: Vec<[u8; 4]> में E से I तक store होते हैं
    • c_8: Vec<[u8; 8]> में J से O तक store होते हैं
  • dense AoVA तरीका कुल vector की संख्या 80% तक घटा सकता है
  • अलग-अलग variant को एक ही allocation में साथ रखने पर vector को type-safe तरीके से iterate करना कठिन हो जाता है
    • access केवल insert के समय बने tagged pointer के जरिए संभव होता है
    • अगर blind iteration की जरूरत न हो और flattened index आधारित tree structure हो, तो यह एक स्वीकार्य trade-off हो सकता है
  • अगर type-safe iteration चाहिए, तो padding cost स्वीकार करके tag को फिर से जोड़ा जा सकता है
  • अगर padding बहुत ज्यादा हो, तो हर variant array पर SoA transformation लागू किया जा सकता है, लेकिन तब vector की संख्या दोगुनी हो जाती है

Zig comptime से बनती memory layout composability

  • Zig prototype osmium में implement किया गया है
  • इसका core compiler built-in के जरिए field type, byte size, bit size और discriminant की जांच करने वाली compile-time reflection है
  • उदाहरण code @typeInfo(inner) से type kind जांचता है और केवल union होने पर ही process करता है
    • union field पर iterate करता है
    • @max(field.alignment, @sizeOf(field.type)) से जरूरी space की गणना करता है
    • size जानकारी को stack-allocated vector में store करता है
    • union field से cluster index तक mapping बनाता है
    • union न होने पर compile error देता है
  • सटीक code snippet इस source में है
  • Rust proc macro से यही उदाहरण बनाना मूलतः संभव नहीं है
    • proc macro type के size या alignment की जानकारी तक पहुंच नहीं पाता
    • किसी खास enum के लिए cluster calculation करने वाला const fn बनाया जा सकता है, लेकिन generic type की array length तय करने में उसका उपयोग नहीं किया जा सकता
  • Rust में generic container implementation को दिए गए type के enum या struct होने के आधार पर conditionally बदलना कठिन है
  • Zig में वैचारिक रूप से T.isEnum() के अनुसार EfficientEnumArray<T> और EfficientStructArray<T> चुनना संभव है
  • AoVA implementation भी enum की विशेषताओं के अनुसार चुनी जा सकती है
    • जैसे, अलग-अलग variant को साथ रखने का लाभ तभी माना जाए जब vector की संख्या 90% से ज्यादा कम हो
  • अगर maximum capacity compile time पर पता हो, तो type generation function tagged index के लिए जरूरी bitwidth तय कर सकता है
  • अगर यही tagged index किसी दूसरे data structure, जैसे किसी और enum, के अंदर शामिल हो, तो बचे हुए bit को discriminant के लिए इस्तेमाल किया जा सकता है
  • Zig जरूरी bit count को सटीक रूप से specify करने देता है, जिससे code के दूसरे हिस्से उस जानकारी का स्वाभाविक रूप से उपयोग कर सकते हैं — यह composable memory efficiency देता है
  • implicit widening integer coercion की वजह से अलग bitwidth वाले API के साथ काम करते समय भी usability बनी रहती है
  • जो system programming language efficiency और zero-cost abstraction को महत्व देती है, उसके लिए staged programming, खासकर Zig का comptime, फिर से देखने लायक है

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

1 टिप्पणियां

 
GN⁺ 2023-09-19
Hacker News टिप्पणियाँ

  • बेहतर storage efficiency और element iteration को बनाए रखने वाली एक और strategy है। पहला vector tags की list, दूसरा vector हर element का byte offset, और तीसरा vector से ज़्यादा उस compressed variant data की तरह रखा जाता है जिसकी ओर दूसरा vector इशारा करता है।
    इससे लेखक के final solution की तुलना में vectors की संख्या आधी हो जाती है (6 vs 3), sorting के कारण ज़रूरी मामलों को छोड़कर padding bytes बर्बाद नहीं होते, और type से स्वतंत्र रूप से data memory में क्रम से रखा होता है, इसलिए cache-friendly तरीके से iterate किया जा सकता है। Index से elements तक O(1) access भी संभव है। कुल मिलाकर heterogeneous data के लिए इसकी performance characteristics Vec जैसी हैं।

    • Byte offsets को inline store करना अच्छा idea है। हालांकि, अगर offsets memory में store हों, तो iteration के दौरान data dependency बनती है, जिससे cache-friendly होने के बावजूद processor pipeline में गंभीर memory stalls आ सकते हैं।
    • अगर ऐसी collection को modify करना हो, तो delete, बड़े variant में बदलाव, और fragmentation संभालने के लिए आखिरकार संभव है कि आप सीधे memory allocator इस्तेमाल करने लगें।
    • Offset size को optimize न किया जाए तो छोटे T की तुलना में यह काफी जगह ले सकता है। उदाहरण के लिए 64-bit size_t और uint8_t T का combination ऐसा है; सिर्फ offset size का ध्यान रखा जाए तो यह approach reasonable लगती है।

  • यह AoVA data structure असल में कैसे काम करता है, यह जानने की उत्सुकता है। Array के नजरिए से index arithmetic अब शायद मायने नहीं रखता, इस लिहाज़ से क्या हम index-based access खो नहीं देते? Iteration भी insertion order preserve नहीं करेगा, ऐसा लगता है।
    इस context में बेहतर caching characteristics वाला TLV(tag-length-value) ज़्यादा commonly used लगता है। Length tag से implied भी हो सकती है, और कम से कम meaningful forward iteration देती है। getdents, inotify, Netlink messaging देखें।

    • Figure 4 के caption को देखें तो AoVA pattern उन cases के लिए ठीक नहीं माना जाना चाहिए जहाँ inserted elements का पूरा order बनाए रखना ज़रूरी हो।
      पहले वाले SoA layout से तुलना करें तो total order नहीं, बल्कि partial order बनता है। Insert करते समय enum tag और उस variant array के अंदर का index—दोनों रखने वाला tagged index return होता है। इसलिए ordered access यहाँ scope से बाहर माना जा रहा लगता है। हर element में global index store करें तो sorted iteration वापस लाई जा सकती है, लेकिन sorted random access में फिर भी मदद नहीं मिलेगी और code में काफी branching होने की संभावना है।
    • Insert करते समय return होने वाला “enum tag और उस variant array के अंदर का index” मूल रूप से pointer है। अगर iterate करना हो, तो जिस usage order में चाहें, pointers को array में store कर दें। यह वही है जो heap में memory allocate करने वाला program करता है।
      चीज़ों को size के हिसाब से store करने का तरीका garbage collectors और general-purpose allocators में भी इस्तेमाल होता है। सभी possible object sizes पता होने से efficiency मिल सकती है, और arena जैसी सरल deallocation strategy से भी efficiency मिल सकती है।
    • AoVA का indices पर अपना total order न होना कुछ use cases में समस्या हो सकता है, लेकिन यहाँ propose किए गए AST nodes के लिए यह ज़रूरी नहीं कि समस्या हो।
      ऐसे cases में arrays को heap जैसी structure का एक component, यानी arena की तरह देखा जा सकता है। Cost यह है कि index को (tag_idx, va_for_tag_idx) जैसा 2-dimensional होना होगा। लेकिन tags की संख्या compile time पर पता होती है, इसलिए tag_idx को upper 4~5 bits में रखकर और va_for_tag_idx को बाकी bits इस्तेमाल करने देकर packing के जरिए storage optimize किया जा सकता है। संदर्भ: https://www.cs.cornell.edu/~asampson/blog/flattening.html
    • Index का type बदलने वाली array writes बेहद महंगी लगती हैं।

  • थोड़ी निराशा है कि Rust की pattern matching अपने storage structure वाला explicit first-class hardcoded object type होने के बजाय, किसी भी struct द्वारा follow किए जा सकने वाले type system के trait जैसे रूप में ज़्यादा express नहीं की जा सकती।
    हाल में मैंने भी इस article की तरह AST implement किया और opcode/bytecode interpreter भी implement किया, लेकिन लगा कि Rust के enums दोनों के लिए पूरी तरह ideal नहीं हैं। AST में मैं सभी statement nodes में line number/column attributes जोड़ना चाहता था, लेकिन Stmt enum के हर case में line/column डालने से boilerplate गंदा हो गया; और enum को original enum तथा line/column attributes साथ रखने वाली नई Stmt struct में wrap करने से बहुत refactoring करनी पड़ी और वह elegant नहीं था। Opcode side पर भी pattern-matched Rust enum VM opcode interpreter performance के लिहाज़ से ideal encoding नहीं कहा जा सकता, लेकिन language इसी दिशा में encourage करती है और destructuring pattern features बहुत आकर्षक हैं। ऐसा लगता है कि type system में सुधार की गुंजाइश है, ताकि मनचाहा low-level implementation इस्तेमाल करते हुए भी pattern matching features मिल सकें।

    • कोई और concrete example हो तो अच्छा होगा। पहले जो चीज़ दिमाग में आती है वह किसी तरह का structural type system है, लेकिन पक्का नहीं कि मैंने ठीक यही समझा है या नहीं।
      https://en.wikipedia.org/wiki/Structural_type_system
    • Bytecode interpreter की एक पुरानी technique है कि अगले opcode implementation पर जाने के लिए indirect jump इस्तेमाल किया जाए। gcc में इसके लिए computed goto extension था, और Rust में शायद function pointers और tail call optimization को force करने वाली किसी चीज़ की जरूरत होगी।
      अगर हर opcode implementation की शुरुआत में ऐसा indirect jump रखा जाए, तो CPU के पास OOP के कारण मौजूद indirect jump predictor अलग-अलग opcode endings के लिए अलग models रख सकता है, जिससे prediction success rate बढ़ सकता है। Next instruction खुद predict करना मुश्किल हो सकता है, लेकिन उदाहरण के लिए test के बाद branch आने की संभावना कहीं ज़्यादा हो सकती है। हालांकि stack machine में stack top को register में store करने जैसी दूसरी techniques शायद ज़्यादा महत्वपूर्ण होंगी, और यह technique आज भी meaningful है या नहीं, मुझे ठीक से नहीं पता।
    • कई languages में आपकी चाहत से मिलते-जुलते features हैं। Scala के extractor या F# के active view देखें।

  • “पार्स किया गया clang AST मूल source code की तुलना में नियमित रूप से 50 गुना ज़्यादा memory खाता है” यह बात काफ़ी बड़ी लगती है, लेकिन छूटा हुआ context यह है कि यह कितना बेहतर हो सकता है। अगर हर token की source location को सुरक्षित रखना है और AST से ठीक से recover किया जा सके, इसके लिए पर्याप्त information encode करनी है, तो मूल के मुकाबले ideal बढ़ोतरी 1.5 गुना है या 15 गुना—यह जानना चाहूंगा

    • उदाहरण के लिए अगर memory में 30% कमी संभव हो तो यह काफ़ी बड़ी खबर है। हालांकि अगर compiler को आगे maintain करना मुश्किल बनाकर सिर्फ़ 30% घटाया जाए, तो शायद इसकी बहुत कीमत न हो। इसके उलट, compiler के साथ थोड़ा rough तरीके से पेश आकर भी अगर 80% कमी मिलती है, तो कोशिश करने लायक है
      user-friendly और compiler developers के लिए भी friendly भाषा में ideal source→AST expansion rate कितना होना चाहिए, यह कहना मुश्किल है, लेकिन 50 गुना भी काम करता है। मूल लेख में 50 गुना expansion rate को किसी खास optimization को automate करने की प्रेरणा के तौर पर इस्तेमाल किया गया है। अगर Rust का enum vector enum values को अपने-आप tag और opaque value में तोड़ दे, और Zig में मूल लेख जैसा किया गया है वैसे array-of-structs रूप में store कर सके, तो यह दिलचस्प होगा। unsafe के इस्तेमाल को छिपाने की बहुत जगहें भी शायद नहीं होंगी
    • तुलना के लिए simdjson tape मूल document से लगभग सिर्फ़ 3 गुना बड़ा है। numbers को सिर्फ़ एक tape slot में रखने, या escape sequence न होने वाली strings को copy न करके मूल document location को reference करने से इसका काफ़ी हिस्सा घटाया जा सकता है
      जिन documents का ज़्यादातर हिस्सा [] characters या 0, characters से बना हो, उनमें maximum overhead करीब 8 गुना दिखता है
    • source code हैरान करने लायक compact होता है। यह कितना बेहतर हो सकता है, इसके एक data point के तौर पर Zig के अपने parser ने Zig के अपने parser को parse किया हुआ result है
      source bytes: 139 KiB, tokens: 24646 (120 KiB), AST nodes: 10998 (140 KiB)। हर token 5 bytes में काफ़ी न्यूनतम किया गया है (1-byte tag + 4-byte file offset), और AST nodes भी compact तथा non-uniform तरीके से encode किए गए हैं, इस case में लगभग 13 bytes प्रति node। ऐसे minimal encoding के बावजूद parse tree source file size का लगभग 2 गुना हो जाता है। फिर भी 2 गुना, 50 गुना से कहीं बेहतर है। स्रोत: zig ast-check -t lib/std/zig/Parse.zig | head -n7
    • linked presentation को बस देख लेना बेहतर है। शानदार presentation है। मेरी याद में उसने सटीक numbers नहीं दिए थे, और शायद अभी निश्चित होने के लिए शुरुआती चरण था। ऐसा data छूटा हो सकता है जिसकी ज़रूरत का अभी एहसास नहीं हुआ, इसलिए numbers छोटे निकल सकते हैं

  • यह problem space packing problem के एक variant जैसा लगता है
    अगर अंतिम result—मनुष्यों के लिए संभालने में आसान structure—से शुरू करके, memory waste घटाने, alignment rules का पालन करने और spatial locality बढ़ाने वाले data structure recommendations generate किए जा सकें, तो अच्छा होगा। https://en.wikipedia.org/wiki/Packing_problems

  • अच्छा होगा अगर proc macro इतना विकसित हो कि वह compiler से information query कर सके। इसके लिए compile stages जोड़ने पर सावधानी से design चाहिए होगा, लेकिन “क्या यह struct यह trait implement करता है”, “सभी concretely implemented traits की list दो” जैसी चीज़ें proc macro में अक्सर बहुत उपयोगी होती हैं

    • अगर मेरी याद सही है, compiler plugins को दो stages में चलाता है। पहला stage type checking से पहले AST पाता है और AST को modify कर सकता है; macro और कुछ clippy lint यहां चलते हैं। दूसरा stage type checking के बाद होता है, इसलिए type information मिलती है लेकिन modify नहीं कर सकता, और दूसरे clippy lints यहां चलते हैं

  • लेख को मैंने आंशिक रूप से ही समझा, लेकिन Rust में spreadsheet engine लिखने के नज़रिये से यह बहुत relevant लगता है। cell values को इस तरह का form चाहिए
    pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box, char, Box), Function(String, Vec), }
    इसे पढ़ना और study करना जारी रखूंगा, और कोई reference material हो तो स्वागत है

    • यहां जिस समस्या पर ज़ोर है, वह यह है कि variants के sizes बहुत अलग हैं और अगर ऐसे values array में बहुत ज़्यादा हों, तो padding में waste होने वाली space की वजह से performance खराब होती है
      games की दुनिया से आई common technique है array of structs (AoS) को struct of arrays (SoA) में तोड़ना। उदाहरण के लिए struct Humans { healths: Vec, ammo: Vec, … } रखने पर हर vector का i-th index AoS layout के i-th Human के बराबर होता है। ऐसे parallel vectors सिर्फ़ example हैं, optimal efficiency नहीं, क्योंकि हर field के लिए length और capacity bookkeeping duplicate होकर waste होती है। यह लेख मूल रूप से enum के लिए ऐसी ही idea को automatically apply करने की कोशिश है, और Rust में इसे जस का तस करना मुश्किल है। यह समस्या असल में कितनी बड़ी है, शायद कुछ बढ़ा-चढ़ाकर भी कहा गया हो। spreadsheet में इसे फिलहाल सिर्फ़ एक possible optimization के तौर पर ध्यान में रखना चाहिए, और पहले यह तय करना चाहिए कि आप speed के लिए बना रहे हैं या simplicity और समझने में आसानी के लिए
    • project दिलचस्प लगता है। अगर यह general users के लिए है, तो यह expect करना चाहिए कि user sheet के चार extreme corners में content डालकर देखेगा कि engine गिरता है या नहीं
      अगर 10 लाख × 10 लाख cells allow करते हैं और हर unfilled cell में null store करते हैं, तो memory खत्म हो जाएगी। इसलिए cell contents को sparse तरीके से store करने पर विचार कर सकते हैं। एक तरीका hashbrown जैसे hash map implementation का इस्तेमाल है। इस लेख का point low-level details है, इसलिए अगर शुरू से hash map के साथ शुरू करके शुरुआती memory constraints से बच जाते हैं, तो फिलहाल इस पर बहुत गहराई से सोचने की ज़रूरत नहीं है
    • मैंने सच में Rust में spreadsheet engine बनाया है। source public नहीं है, लेकिन कुछ सलाह दे सकता हूं। इस लेख के तरीके से फायदा मिलने से पहले आपको बहुत सारी performance problems मिलेंगी
      सबसे मुश्किल single problem evaluation strategy है

  • https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers कैसा रहेगा

  • example code में bug लगता है
    field_map[idx] = svec.len - 1;
    अगर svec में पहले से last entry के अलावा कहीं size शामिल है, तो यह गलत होगा