बेहद तेज़ Lexer इम्प्लीमेंटेशन रणनीतियाँ

 (xnacly.me)
8 पॉइंट द्वारा GN⁺ 2025-07-24 | अभी कोई टिप्पणी नहीं है. | WhatsApp पर शेयर करें
  • purple-garden भाषा के लिए अत्यंत तेज़ Lexer को सीधे डिज़ाइन और इम्प्लीमेंट करने की रणनीतियाँ और मापी गई परफ़ॉर्मेंस डेटा साझा किया गया है
  • Threaded Lexing (jump table आधारित), 0-copy·window string, interning, bump allocator जैसी कई optimization techniques लागू की गईं
  • token hashing और keyword dictionary hash comparison के जरिए parsing speed को अधिकतम किया गया, और साधारण switch statement की तुलना में jump table CPU cache efficiency में बेहतर साबित हुआ
  • पूरी फ़ाइल को mmap करना और dynamic allocation को न्यूनतम रखना, बड़े इनपुट पर IO·memory management cost को काफ़ी कम करता है
  • मौजूदा प्रसिद्ध lexer (जैसे flex, handcoded) की तुलना में अधिकतम 10x से भी तेज़ processing speed साबित की गई, और parsing/runtime के हर चरण के micro-benchmark आँकड़े दिए गए हैं

Lexing और compile pipeline का अवलोकन

  • Lexer (tokenizer) इनपुट स्ट्रिंग को अर्थपूर्ण token list में बदलता है, जिसके बाद parser इसे लेकर AST (Abstract Syntax Tree) बनाता है
  • purple-garden भाषा में token design, TokenType enum और string·type information ही रखने वाली minimal structure पर आधारित है

न्यूनतम Lexer डिज़ाइन और कोड उदाहरण

  • Lexer struct में सिर्फ़ input string और current position स्टोर किया जाता है
  • switch statement के माध्यम से हर character के अनुसार token बनाया जाता है
  • debugging के लिए type-string mapping array और type-specific initialization का उपयोग किया जाता है

Threaded Lexing (jump table आधारित)

  • switch statement की जगह jump table से token classification process किया जाता है (computed goto)
    • 256-byte array में character value को index बनाकर हर processing label को map किया जाता है
    • वास्तविक code branch में JUMP_TARGET macro के जरिए तुरंत branch execute होती है
  • फ़ायदे:
    • cache miss कम होते हैं और branch prediction optimization के कारण execution तेज़ होता है
  • नुकसान:
    • MSVC supported नहीं है (सिर्फ़ Clang, GCC), और debugging कठिन है

Memory management और Allocator abstraction

  • bump allocator समेत विभिन्न memory allocation strategies के लिए interface परिभाषित किया गया है (Allocator struct)
  • CALL macro के जरिए verbose log और context passing को सरल बनाया गया है
  • वास्तविक allocation·deallocation·statistics structure और code examples भी दिए गए हैं

0-copy, window-आधारित string processing

  • C में efficient processing के लिए Str struct (pointer, length, hash) पेश किया गया है
  • slice, concat, eq, hashing, number conversion आदि को सीधे इम्प्लीमेंट किया गया है
  • string slice सिर्फ़ pointer move करके तुरंत बन जाती है, इसमें कोई memory allocation नहीं होता
  • number conversion के लिए character-to-integer conversion algorithm भी सीधे इम्प्लीमेंट किया गया है

Token hashing और precomputed hash keyword comparison

  • token बनाते समय hash (FNV-1a) कैलकुलेट करके duplicate comparison और interning को optimize किया जाता है
  • true/false जैसे constant keywords को hash value से तुरंत compare करके branch किया जाता है, जिससे performance बेहतर होती है
  • is_alphanum (alphabet/number/special character detection) को भी bit operations और lookup-आधारित तरीक़ों से optimize किया गया है

Number parsing को efficient बनाना और compile stage में शिफ्ट करना

  • Lexer में number token का सिर्फ़ window·hash स्टोर किया जाता है, जबकि वास्तविक integer/float conversion compile stage में duplicate work के बिना सिर्फ़ एक बार किया जाता है
  • repeated numeric value parsing में कुल throughput में 64% से अधिक सुधार देखा गया

बड़े फ़ाइल IO को तेज़ करना

  • पारंपरिक fread method की जगह mmap से पूरी फ़ाइल को सीधे memory में map किया जाता है
  • IO_read_file_to_string function पूरी input को mmap करता है, और बड़े आकार पर 6~35x performance improvement देखा गया

वास्तविक benchmark और performance comparison

  • Laptop पर: 1,000,000+ lines, 25MB input में 44ms (सिर्फ़ tokenization)
  • Desktop पर: उसी input में 30ms (अधिकतम 848MB/s)
  • अन्य lexer की तुलना में 10x से अधिक (0.3 सेकंड बनाम 2~13 सेकंड)
  • micro-benchmark में हर optimization के प्रभाव को मापा गया है (जैसे bump allocator 1.58x, string 0 alloc 1.4~1.5x, number parsing को compile stage में ले जाने पर 2.8x)

इम्प्लीमेंटेशन रणनीति का सार

  • jump table आधारित direct branching (threaded lexing)
  • 0-copy window token structure
  • constant token interning
  • bump allocator आधारित memory management
  • token hashing और precomputed hash comparison
  • number·string token का delayed parsing और interning
  • बड़ी फ़ाइलों के लिए mmap processing
  • आगे के कार्य के रूप में SIMD उपयोग, और तेज़ hashing algorithm, memory alignment·prefetch, input-specific jump table optimization आदि सुझाए गए हैं

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

अभी कोई टिप्पणी नहीं है.

अभी कोई टिप्पणी नहीं है.