तेज़ dynamic language interpreter कैसे बनाएँ

• AST को सीधे traverse करने वाला interpreter भी value representation, inline cache, object model, watchpoint, और बार-बार की गई सूक्ष्म optimization के जरिए बड़ा performance सुधार हासिल कर सकता है
• performance को लगभग नज़रअंदाज़ करके बनाया गया Zef baseline CPython 3.10 से 35 गुना, Lua 5.4.7 से 80 गुना, और QuickJS-ng 0.14.0 से 23 गुना धीमा था, लेकिन 21 चरणों की optimization के बाद 16.646 गुना speedup हासिल किया गया
• सबसे बड़ी छलांग object model के redesign और inline cache के संयोजन से आई, और Storage व Offsets आधारित access, cached AST specialization, तथा name override की निगरानी के लिए watchpoint लागू करने से आगे 4.55 गुना सुधार हुआ
• अतिरिक्त सुधारों में string-आधारित dispatch हटाना, Symbol को शामिल करना, argument passing structure बदलना, getter और setter specialization, hash table fast path, और array literal के साथ sqrt व toString specialization तक को क्रमिक रूप से लागू किया गया
• Yolo-C++ port तक शामिल करने पर baseline की तुलना में 66.962 गुना तेज़ प्रदर्शन दर्ज किया गया; यह CPython 3.10 से 1.889 गुना तेज़ और QuickJS-ng 0.14.0 से 2.968 गुना तेज़ है, लेकिन memory deallocation न होने के कारण लंबे समय तक चलने वाले workload के लिए उपयुक्त नहीं है

---

परिचय और मूल्यांकन पद्धति

• optimization का लक्ष्य AST को सीधे traverse करने वाला interpreter है, और मज़े के लिए बनाई गई dynamic language Zef को Lua, QuickJS, और CPython के साथ प्रतिस्पर्धा करने लायक स्तर तक ले जाना उद्देश्य है
  • JIT compiler या mature GC की सूक्ष्म tuning से अधिक, ऐसी optimization पर ध्यान है जिन्हें बिना मज़बूत बुनियाद वाले शुरुआती implementation पर भी लागू किया जा सके
  • जिन तकनीकों पर चर्चा है वे हैं value representation, inline caching, object model, watchpoint, और व्यावहारिक optimization का बार-बार प्रयोग
• लेख में दी गई तकनीकों से ही SSA, GC, bytecode, या machine code के बिना भी बड़ा performance सुधार हासिल किया गया
  • लेख के दायरे में 16 गुना speedup
  • अधूरे Yolo-C++ port को शामिल करने पर 67 गुना speedup
• performance evaluation के लिए ScriptBench1 benchmark suite का उपयोग किया गया
  • शामिल benchmark हैं Richards OS scheduler, DeltaBlue constraint solver, N-Body physics simulation, और Splay binary tree test
  • JavaScript, Python, और Lua के मौजूदा port का उपयोग किया गया
  • Splay के Python और Lua port Claude से बनाए गए थे
• प्रयोग का वातावरण Ubuntu 22.04.5, Intel Core Ultra 5 135U, 32GB RAM, और Fil-C++ 0.677 था
  • Lua 5.4.7 को GCC 11.4.0 से compile किया गया
  • QuickJS-ng 0.14.0 के लिए GitHub releases binary का उपयोग किया गया
  • CPython 3.10 के लिए Ubuntu का default version इस्तेमाल किया गया
• सभी प्रयोगों में random क्रम में मिलाकर किए गए 30 रन के औसत का उपयोग किया गया
• अधिकांश तुलना Fil-C++ से compile किए गए Zef interpreter और Yolo-C compiler से build किए गए अन्य interpreter के बीच की गई

मूल Zef interpreter

• इसे performance पर लगभग ध्यान दिए बिना लिखा गया था, और स्पष्ट रूप से कहा गया कि performance को ध्यान में रखकर केवल दो ही चुनाव किए गए थे

• value representation

  • 64-bit tagged value का उपयोग
    • इसमें रखे जा सकने वाले मान हैं double, 32-bit integer, और Object*
  • double को 0x1000000000000 offset तरीके से दर्शाया गया
    • इसे JavaScriptCore से सीखी गई तकनीक के रूप में बताया गया
    • साहित्य में इसे NuN tagging कहा जाता है
  • integer और pointer के लिए native representation का उपयोग
    • यह इस मान्यता पर निर्भर है कि pointer value 0x100000000 से छोटी नहीं होगी
    • इसे स्वयं एक जोखिमभरा विकल्प बताया गया
    • विकल्प के रूप में integer पर 0xffff000000000000 upper-bit tag लगाने का उल्लेख किया गया
  • इस representation से number arithmetic में bit test आधारित fast path लागू करना संभव हुआ
  • इससे भी अधिक महत्वपूर्ण लाभ था numbers के लिए heap allocation से बचाव
  • नया interpreter बनाते समय शुरुआत में सही default value representation चुनना महत्वपूर्ण है, क्योंकि बाद में इसे बदलना बहुत कठिन होता है
  • dynamic type language implementation की शुरुआत के लिए 32-bit या 64-bit tagged value का सुझाव दिया गया

• implementation language का चयन

  • ऐसी भाषा के रूप में C++ परिवार को चुना गया जिसमें optimization को पर्याप्त रूप से व्यक्त किया जा सके
  • स्पष्ट रूप से कहा गया कि Java को low-level optimization की सीमा के कारण नहीं चुना जाएगा
  • यह भी बताया गया कि Rust को GC language implementation के लिए आवश्यक global mutable state और circular reference वाले heap representation के कारण नहीं चुना जाएगा
    • हालांकि, multi-language setup स्वीकार करने या बहुत सारा unsafe code अनुमति देने पर Rust के आंशिक या पूर्ण उपयोग की संभावना का उल्लेख किया गया

• performance engineering के दृष्टिकोण से गलत विकल्प

  • Fil-C++ का उपयोग
    • इससे तेज़ी से विकास संभव हुआ और GC मुफ्त में मिला
    • memory safety violation को diagnostic information और stack trace के साथ रिपोर्ट किया जाता है
    • undefined behavior नहीं है
    • performance लागत आम तौर पर लगभग 4 गुना है
  • recursive AST-walking interpreter
    • कई जगह override होने वाली virtual Node::evaluate method संरचना
  • string का अत्यधिक उपयोग
    • Get AST node variable name बताने वाला std::string संग्रहीत करता है
    • हर variable access पर उसी string का उपयोग होता है
  • hash table का अत्यधिक उपयोग
    • Get execute होने पर string key के साथ std::unordered_map lookup किया जाता है
  • recursive call chain आधारित scope lookup
    • लगभग हर तरह की nesting और closure की अनुमति
    • function F के भीतर class A, और class B के भीतर function G जैसी nesting में A की method A field, F local variable, B field, और G local variable देख सकती है
    • मूल implementation इसे अलग-अलग scope object पर query करने वाले C++ recursive function के जरिए संभालता था

• मूल implementation की विशेषताएँ

  • गलत विकल्पों के बावजूद कम code में काफ़ी जटिल language interpreter implement करना संभव था
  • सबसे बड़ा module parser है
  • बाकी हिस्सा अपेक्षाकृत सरल और स्पष्ट है

• शुरुआती performance

  • मूल interpreter CPython 3.10 से 35 गुना धीमा था

  • Lua 5.4.7 से 80 गुना धीमा

    • QuickJS-ng 0.14.0 से 23 गुना धीमा

पूरी optimization प्रगति तालिका

• तालिका में Zef Baseline से Zef Change #21: No Asserts, और Zef in Yolo-C++ तक के performance बदलाव को संक्षेप में दिखाया गया है
  • comparison column हैं vs Zef Baseline, vs Python 3.10, vs Lua 5.4.7, और vs QuickJS-ng 0.14.0
• अंतिम पंक्ति के अनुसार Zef Change #21: No Asserts baseline की तुलना में 16.646 गुना तेज़ है

  • Python 3.10 से 2.13 गुना धीमा

  • Lua 5.4.7 से 4.781 गुना धीमा

    • QuickJS-ng 0.14.0 से 1.355 गुना धीमा

• Zef in Yolo-C++** baseline की तुलना में 66.962 गुना तेज़ है

  • Python 3.10 से 1.889 गुना तेज़

  • Lua 5.4.7 से 1.189 गुना धीमा

    • QuickJS-ng 0.14.0 से 2.968 गुना तेज़

शुरुआती optimization चरण

• Optimization #1: operator को सीधे call करना

  • parser अब operator को operator नाम वाले DotCall node के रूप में नहीं बनाता, बल्कि हर operator के लिए अलग AST node बनाता है
  • Zef में a + b और a.add(b) एक जैसे हैं
    • पहले a + b को DotCall(a, "add") और argument b के रूप में parse किया जाता था
    • हर arithmetic operation पर operator method name string lookup होता था
    • DotCall string को Value::callMethod तक भेजता था
    • Value::callMethod कई string comparison करता था
  • बदलाव के बाद parser Binary<>, Unary<> node बनाता है
    • template और lambda का उपयोग करके हर operator के लिए अलग Node::evaluate override दिया जाता है
    • हर node उस operator के लिए संबंधित Value fast path को सीधे call करता है
    • उदाहरण के लिए a + b में Binary<lambda for add>::evaluate call होता है और फिर Value::add call होता है
  • performance पर असर 17.5% सुधार
    • इस बिंदु पर performance CPython 3.10 से 30 गुना धीमा है
    • Lua 5.4.7 से 67 गुना धीमा
    • QuickJS-ng 0.14.0 से 19 गुना धीमा

• Optimization #2: RMW operator को सीधे call करना

  • सामान्य operator तेज़ हो गए, लेकिन a += b जैसे RMW रूप अब भी string-based dispatch इस्तेमाल करते थे
  • parser को हर RMW case के लिए अलग node बनाने के लिए बदला गया
  • parser, LValue node से makeRMW virtual call के ज़रिए खुद को RMW से replace करने का अनुरोध करता है
  • RMW में बदलने वाले LValue हैं Get, Dot, Subscript
    • Get variable read id से मेल खाता है
    • Dot expr.id से मेल खाता है
    • Subscript expr[index] से मेल खाता है
  • हर virtual call में SPECIALIZE_NEW_RMW macro इस्तेमाल होता है
    • SetRMW id += value के लिए है
    • DotSetRMW expr.id += value के लिए है
    • SubscriptRMW expr[index] += value के लिए है
  • बदलाव #1 में operator specialization lambda dispatch का उपयोग करती है
  • RMW में enum का उपयोग किया गया
    • get, dot, subscript तीनों path को संभालना था और enum को कई जगह पास करना पड़ता था, इसलिए यह चुना गया
    • अंत में Value::callRMW<> template function असली RMW operator call dispatch करता है
  • performance पर असर 3.7% सुधार
    • इस बिंदु पर performance CPython 3.10 से 29 गुना धीमा है
    • Lua 5.4.7 से 65 गुना धीमा
    • QuickJS-ng 0.14.0 से 18.5 गुना धीमा
    • शुरुआती बिंदु की तुलना में 1.22 गुना तेज़

• Optimization #3: IntObject जांच से बचना

  • bottleneck यह था कि Value का fast path isInt() इस्तेमाल करता है, और उसके अंदर isIntSlow() Object::isInt() virtual call करता है
  • मूल value representation में चार मामले थे
    • tagged int32
    • tagged double
    • int32 में represent न हो सकने वाले int64 के लिए IntObject
    • और बाकी सभी object
  • IntObject के मामले में भी integer method dispatch Value ही संभालता था
    • ताकि सभी arithmetic operation implementation एक ही जगह, यानी Value में रहें
  • optimization के बाद Value fast path सिर्फ int32 और double को देखता है
    • IntObject handling logic को IntObject के अंदर ले जाया गया
    • हर method dispatch पर होने वाली isInt() call से बचाव हुआ
  • performance पर असर 1% सुधार
    • इस बिंदु पर performance CPython 3.10 से 29 गुना धीमा है
    • Lua 5.4.7 से 65 गुना धीमा
    • QuickJS-ng 0.14.0 से 18 गुना धीमा
    • शुरुआती बिंदु की तुलना में 1.23 गुना तेज़

• Optimization #4: Symbol

  • मूल interpreter लगभग हर जगह std::string का उपयोग करता था
  • महंगे string उपयोग वाले स्थान थे Context::get, Context::set, Context::callFunction, Value::callMethod, Value::dot, Value::setDot, Value::callOperator<>, Object::callMethod परिवार
  • इस संरचना में यह साधारण hash table lookup नहीं था, बल्कि string key hash table lookup था, इसलिए runtime में string hashing और comparison बार-बार होते थे
  • optimization में string-based lookup को hash-consed Symbol object pointer से बदला गया
  • नया Symbol class जोड़ा गया
    • symbol.h, symbol.cpp में implementation
    • Symbol और string एक-दूसरे में बदले जा सकते हैं
    • string को Symbol में बदलते समय global hash table से hash consing की जाती है
    • नतीजतन, सिर्फ Symbol* pointer identity comparison से यह तय हो जाता है कि symbol वही है या नहीं
  • string literal की जगह पहले से तैयार symbol इस्तेमाल किए गए
    • उदाहरण के लिए "subscript" की जगह Symbol::subscript
  • कई function signature में const std::string& की जगह Symbol* इस्तेमाल होने लगा
  • performance पर असर 18% सुधार
    • इस बिंदु पर performance CPython 3.10 से 24 गुना धीमा है
    • Lua 5.4.7 से 54 गुना धीमा
    • QuickJS-ng 0.14.0 से 15 गुना धीमा
    • शुरुआती बिंदु की तुलना में 1.46 गुना तेज़

• Optimization #5: Value inlining

  • मुख्य बात थी महत्वपूर्ण function की inlining को संभव बनाना
  • लगभग सभी बदलावों का केंद्र नया header valueinlines.h जोड़ना था
  • इसे value.h से अलग header में रखने का कारण यह था कि यह उन headers का उपयोग करता है जिन्हें value.h include करना पड़ता है
  • performance पर असर 2.8% सुधार
    • इस बिंदु पर performance CPython 3.10 से 24 गुना धीमा है
    • Lua 5.4.7 से 53 गुना धीमा
    • QuickJS-ng 0.14.0 से 15 गुना धीमा
    • शुरुआती बिंदु की तुलना में 1.5 गुना तेज़

ऑब्जेक्ट मॉडल और कैश संरचना का पुनर्रचना

• ऑप्टिमाइज़ेशन #6: ऑब्जेक्ट मॉडल, inline cache, Watchpoint

  • Object, ClassObject, Context के काम करने के तरीके को बड़े पैमाने पर फिर से बनाया गया, ताकि ऑब्जेक्ट allocation लागत घटे और access के समय hash table lookup से बचा जा सके
  • यह बदलाव ऑब्जेक्ट मॉडल, inline cache, और watchpoint इन तीन फीचरों के संयोजन से बना है

• ऑब्जेक्ट मॉडल

  • पहले हर lexical scope के लिए एक Context ऑब्जेक्ट allocate किया जाता था
    • हर Context के पास उस scope के variables रखने वाली एक hash table होती थी
  • ऑब्जेक्ट की संरचना इससे भी अधिक जटिल थी
    • हर ऑब्जेक्ट के पास उन classes को Context से map करने वाली hash table होती थी जिनका वह instance होता था
  • इस तरह की संरचना inheritance और nested scopes की वजह से ज़रूरी थी
    • जब Bar, Foo को inherit करता है, तब Bar और Foo अलग-अलग scopes को close over कर सकते हैं
    • और एक ही नाम के अलग-अलग private fields भी रख सकते हैं
  • नई संरचना Storage की अवधारणा लाती है
    • डेटा को Offsets के अनुसार store किया जाता है
    • offset किस तरह होगा, यह कोई Context तय करता है
  • Context अब भी मौजूद है, लेकिन ऑब्जेक्ट या scope बनने के समय नहीं, बल्कि AST के resolve pass में पहले से बनाया जाता है
  • वास्तविक ऑब्जेक्ट या scope बनाते समय, उस Context द्वारा निकाले गए आकार के अनुसार सिर्फ Storage allocate किया जाता है

• inline cache

  • expr.name जैसे code location पर, आख़िरी बार देखे गए expr के dynamic type और name के resolve हुए आख़िरी offset को याद रखने की तकनीक
  • यह एक क्लासिक तकनीक है जिसे आमतौर पर JIT संदर्भ में समझाया जाता है, लेकिन यहाँ इसे interpreter पर लागू किया गया है
  • याद रखी गई जानकारी को सामान्य AST node के ऊपर specialized AST node को placement construct करने के तरीके से लागू किया गया

• inline cache के घटक

  • CacheRecipe
    • कोई खास access क्या कर रहा था, और क्या वह cache किया जा सकता है, यह track करता है
  • Context, ClassObject, Package आदि जगहों पर CacheRecipe calls डाले गए
    • access प्रक्रिया की जानकारी इकट्ठा करने के लिए
  • Dot::evaluate जैसी AST evaluation functions, अपने द्वारा किए गए polymorphic operation से मिले CacheRecipe को this के साथ constructCache<> को देती हैं
  • constructCache
    • CacheRecipe के आधार पर नई AST node specialization compile करता है
    • template machinery से कई तरह के specialized AST nodes बनते हैं
    • अगर local variable access है, तो दिए गए storage से direct load करता है
    • आख़िरी बार देखी गई class से समानता जांचने वाला class check करता है
    • उसके बाद आख़िरी बार देखे गए function के लिए direct function call करता है
    • ज़रूरत पड़ने पर chain step और watchpoint का संयोजन भी करता है
  • cache किए जाने वाले हर AST node के पास अपनी cached variant होती है
    • पहले cache ऑब्जेक्ट के ज़रिए तेज़ call की कोशिश की जाती है
    • cache ऑब्जेक्ट का type constructCache<> तय करता है

• watchpoint

  • एक उदाहरण दिया गया है जहाँ lexical scope में variable x है, उसके भीतर class Foo है, और Foo का method x को access करता है
  • अगर Foo के अंदर x नाम का कोई function या variable नहीं है, तो ऐसा लगता है कि वह सीधे बाहर वाले x को पढ़ सकता है
  • लेकिन subclass getter x जोड़ सकता है
  • उस स्थिति में access का परिणाम बाहर वाला x नहीं, बल्कि getter होना चाहिए
  • inline cache इस तरह के बदलाव की संभावना को संभालने के लिए runtime पर Watchpoint सेट करता है
  • इस उदाहरण में, यह नाम override हुआ है या नहीं इसे monitor करने वाला watchpoint इस्तेमाल किया गया है

• इन तीन फीचरों को साथ में लागू करने की वजह

  • सिर्फ नया ऑब्जेक्ट मॉडल होने से, अगर inline cache अच्छी तरह काम न करे, तो अर्थपूर्ण सुधार पाना मुश्किल है
  • inline cache भी watchpoint के बिना कई cache conditions को सुरक्षित रूप से संभाल नहीं सकता, इसलिए उसका व्यावहारिक लाभ कम हो जाता है
  • नया ऑब्जेक्ट मॉडल और watchpoint को साथ में ठीक से काम करना ही था

• इम्प्लिमेंटेशन की प्रगति और कठिन हिस्से

  • शुरुआत एक साधारण CacheRecipe संस्करण लिखने से हुई, और फिर अंतिम रूप के क़रीब Storage, Offsets डिज़ाइन पर काम हुआ
  • सबसे कठिन कामों में से एक था intrinsic class implementation के तरीके को बदलना
  • array उदाहरण
    • पहले ArrayObject::tryCallMethod, Object::tryCallMethod virtual call को intercept करने के तरीके से सभी methods implement करता था
    • नए ऑब्जेक्ट मॉडल में Object में न तो vtable है और न virtual methods
    • उसकी जगह Object::tryCallMethod object->classObject()->tryCallMethod(object, ...) को delegate करता है
    • इसलिए Array methods देने के लिए, उन methods वाली Array की class खुद बनानी पड़ती है
  • नतीजतन intrinsic functionality का बड़ा हिस्सा, जो पहले implementation में जगह-जगह फैला था, अब makerootcontext.cpp के केंद्र में आ गया
  • इसे सकारात्मक परिणाम इसलिए माना गया क्योंकि ऑब्जेक्ट की native/intrinsic functions पर भी inline cache वैसे ही लागू हो जाता है
  • performance प्रभाव 4.55 गुना सुधार था
    • इस बिंदु पर performance CPython 3.10 से 5.2 गुना धीमी थी
    • Lua 5.4.7 से 11.7 गुना धीमी थी
    • QuickJS-ng 0.14.0 से 3.3 गुना धीमी थी
    • शुरुआती बिंदु की तुलना में 6.8 गुना तेज़ थी
    • मूल्यांकन यह था कि दूसरे interpreters की तुलना में Fil-C++ का घाटा कुल मिलाकर Fil-C लागत के स्तर तक सिमट गया था

कॉल और access path optimization

• optimization #7: argument passing structure में सुधार

  • बदलाव से पहले Zef interpreter function arguments को const std::optional<std::vector<Value>>& के रूप में पास करता था
  • optional की ज़रूरत इसलिए थी क्योंकि कुछ edge cases में नीचे दिए गए दोनों को अलग करना पड़ता था
    • o.getter
    • o.function()
  • Zef में आम तौर पर दोनों ही function call हैं, लेकिन अपवाद के तौर पर नीचे दिया गया कोड मौजूद है
    • o.NestedClass
    • o.NestedClass()
  • पहला NestedClass object खुद return करता है
  • दूसरा instance बनाता है
  • इसलिए बिना arguments वाला function call और getter-जैसे call के रूप में empty argument array वाला case अलग करना ज़रूरी है
  • लेकिन पुरानी संरचना inefficient थी
    • caller vector allocate करता था
    • callee उस vector को copy करके arguments scope फिर से allocate करता था
  • बदलाव के तहत Arguments type जोड़ा गया
    • इसका रूप callee द्वारा बनाए जा रहे arguments scope के बिल्कुल समान है
    • अब caller सीधे उसी रूप में allocate करता है
  • Yolo-C++ में भी vector backing store malloc हटने से allocations की संख्या घटी
  • Fil-C++ में std::optional खुद heap allocation करता है
    • std::optional न हो तब भी const std::vector<>& पास करना भी allocation करता है
    • जो stack allocation दिखता है, उसे भी heap allocation माना जाता है
    • यह भी बताया गया कि caller side vector का size पहले से तय नहीं कर रहा था, इसलिए कई बार reallocation हो रहा था
  • बदलाव का बड़ा हिस्सा function signatures को Arguments* से बदलने का काम था
  • performance effect 1.33x सुधार
    • इस बिंदु पर performance CPython 3.10 से 3.9x धीमी थी
    • Lua 5.4.7 से 8.8x धीमी
    • QuickJS-ng 0.14.0 से 2.5x धीमी
    • शुरुआती बिंदु की तुलना में 9.05x तेज़

• optimization #8: Getter specialization

  • Zef, Ruby की तरह, instance fields को default रूप से private रखता है
  • उदाहरण class Foo { my f fn (inF) f = inF }
    • constructor में मिला मान instance को ही दिखने वाले local variable f में store होता है
  • एक ही type के instances भी दूसरे object के f तक access नहीं कर सकते
    • उदाहरण fn nope(o) o.f
    • println(Foo(42).nope(Foo(666)))
    • nope के अंदर o.f, o के f तक access नहीं कर सकता
  • वजह यह है कि field class member की scope chain में दिखाई देने के तरीके से काम करता है
    • o.f field read नहीं बल्कि f नाम के method call का अनुरोध है
  • इसलिए नीचे दिया गया pattern अक्सर दिखता है
    • my f
    • fn f f
    • यानी local variable f return करने वाला f नाम का method
  • इसके लिए छोटा syntax readable f है
    • my f और fn f f का shorthand
  • कई method calls असल में getter call होते हैं
  • हर getter का AST evaluate करके चलना wasteful है
  • optimization है getter specialization
    • इसका केंद्र UserFunction है
    • नए Node::inferGetter method से यह infer किया जाता है कि function body simple getter है या नहीं
  • inference rules
    • Block::inferGetter तभी getter infer करता है जब उसके भीतर की सारी चीज़ें getter के रूप में infer की जा सकें
    • Get::inferGetter खुद को getter के रूप में infer करता है और load किए जाने वाला offset लौटाता है
    • Context::tryGetFieldOffsets तभी non-empty Offsets लौटाता है जब getter के चलने वाले lexical scope में वह field पक्का मौजूद हो
    • UserFunction function body को getter के रूप में infer किया जा सके तो ज्ञात offset से सीधे read करने वाली special Function subclass में resolve होता है
  • performance effect 5.6% सुधार
    • इस बिंदु पर performance CPython 3.10 से 3.7x धीमी थी
    • Lua 5.4.7 से 8.3x धीमी
    • QuickJS-ng 0.14.0 से 2.4x धीमी
    • शुरुआती बिंदु की तुलना में 9.55x तेज़

• optimization #9: Setter specialization

  • setter inference में fn set_fieldName(newValue) fieldName = newValue pattern matching की ज़रूरत होती है
  • UserFunction के inference stage में setter के parameter name को पास करना पड़ता है
  • Set के inference stage में यह जाँचना होता है कि यह ClassObject पर write नहीं है, और साथ ही यह भी कि setter parameter set के source के रूप में इस्तेमाल हो रहा है या नहीं
  • performance effect 3.4% सुधार
    • इस बिंदु पर Zef CPython 3.10 से 3.6x धीमा था
    • Lua 5.4.7 से 8x धीमा
    • QuickJS-ng 0.14.0 से 2.3x धीमा
    • शुरुआती बिंदु की तुलना में 9.87x तेज़

• optimization #10: callMethod का inlining

  • एक महत्वपूर्ण function को एक पंक्ति के बदलाव से inline किया गया
  • performance effect 3.2% सुधार
    • इस बिंदु पर Zef CPython 3.10 से 3.5x धीमा था
    • Lua 5.4.7 से 7.8x धीमा
    • QuickJS-ng 0.14.0 से 2.2x धीमा
    • शुरुआती बिंदु की तुलना में 10.2x तेज़

• optimization #11: hash table

  • method call में inline cache miss होने पर ClassObject::tryCallMethod और ClassObject::TryCallMethodDirect तक नीचे जाना पड़ता था, और दोनों paths बड़े और जटिल थे
  • पहले lookup cost hierarchy depth के अनुपात में O(hierarchy depth) थी
    • hierarchy की हर class में यह देखने के लिए hash table lookup होता था कि call को member function के रूप में resolve किया जा सकता है या नहीं
    • hierarchy की हर class में यह देखने के लिए भी hash table lookup होता था कि call को nested class के रूप में resolve किया जा सकता है या नहीं
  • नए बदलाव में receiver class और symbol को key के रूप में इस्तेमाल करने वाली global hash table जोड़ी गई
    • एक ही lookup में callee सीधे return हो जाता है
    • classobject.h में पूरे tryCallMethodSlow path पर जाने से पहले इस global table को पहले lookup किया जाता है
    • classobject.cpp में सफल lookup result को global table में record किया जाता है
    • global hash table खुद अपेक्षाकृत simple implementation है
  • performance effect 15% सुधार
    • इस बिंदु पर Zef CPython 3.10 से 3x धीमा था
    • Lua 5.4.7 से 6.8x धीमा
    • QuickJS-ng 0.14.0 से 1.9x धीमा
    • शुरुआती बिंदु की तुलना में 11.8x तेज़

• optimization #12: std::optional से बचाव

  • Fil-C++ में union से जुड़ी compiler pathology के कारण std::optional के लिए heap allocation की ज़रूरत पड़ती है
  • आम तौर पर LLVM union memory access type को ढीले ढंग से संभालता है, लेकिन यह invisicaps के साथ टकराता है
    • union के भीतर pointer, programmer के नज़रिए से अनुमान लगाना मुश्किल हो ऐसे तरीके से capability खो सकता है
    • नतीजतन Fil-C में programmer की गलती न होने पर भी null capability वाले object dereference पर panic हो सकता है
  • इसे कम करने के लिए Fil-C++ compiler union type local variables को संभालते समय LLVM को अधिक conservative तरीके से काम कराने हेतु intrinsics insert करता है
  • इसके बाद FilPizlonator pass अपनी escape analysis चलाकर union type local variables को register allocation योग्य बनाने की कोशिश करता है
    • हालांकि यह analysis सामान्य LLVM की SROA analysis जितनी पूर्ण नहीं है
  • नतीजतन std::optional जैसे union शामिल करने वाले class passing के मामले Fil-C++ में अक्सर memory allocation तक पहुँच जाते हैं
  • इस बदलाव में hot path में std::optional तक जाने वाले code path से बचा गया
  • performance effect 1.7% सुधार
    • इस बिंदु पर Zef CPython 3.10 से 3x धीमा था
    • Lua 5.4.7 से 6.65x धीमा
    • QuickJS-ng 0.14.0 से 1.9x धीमा

• शुरुआती बिंदु की तुलना में 12 गुना तेज़

• अनुकूलन #13: specialized arguments

  • Zef के सभी built-in functions 1 या 2 arguments लेते हैं, और native implementation में इन्हें रखने के लिए Arguments object allocate करने की ज़रूरत नहीं
  • setter भी हमेशा एक argument लेता है, और अगर setter inference हो चुका हो तो specialized setter implementation भी Arguments object के बिना केवल value argument को सीधे ले लेना पर्याप्त है
  • इस बदलाव के साथ ZeroArguments, OneArgument, TwoArguments specialized argument types जोड़े गए
    • जब callee को इसकी ज़रूरत न हो, तो caller Arguments object allocation से बच सकता है
  • ZeroArguments की ज़रूरत (Arguments*)nullptr से अलग पहचान के लिए है
    • पहले (Arguments*)nullptr का उपयोग getter call के अर्थ में किया जाता था, और वही logic बरकरार रखा गया
    • अब ZeroArguments का अर्थ है बिना argument वाला function call
  • कई बदलावों में arguments लेने वाले functions को template बनाना शामिल था
    • ZeroArguments, OneArgument, TwoArguments, Arguments* में से प्रत्येक के लिए explicit instantiation किया गया
    • मौजूदा code का बड़ा हिस्सा argument extraction helper के रूप में Value::getArg इस्तेमाल करता था, और इसमें specialized argument overloads जोड़े गए
    • arguments इस्तेमाल करने वाले native code में बदलाव अपेक्षाकृत सीधे थे
  • प्रदर्शन प्रभाव 3.8% सुधार
    • इस बिंदु पर Zef CPython 3.10 से 2.9 गुना धीमा है
    • Lua 5.4.7 से 6.4 गुना धीमा है
    • QuickJS-ng 0.14.0 से 1.8 गुना धीमा है
    • शुरुआती बिंदु की तुलना में 12.4 गुना तेज़

Fil-C pathologies को बायपास करना और detailed specialization

• ऑप्टिमाइज़ेशन #14: बेहतर Value slow path

  • एक और Fil-C pathology workaround से बड़ी speedup मिली
  • बदलाव से पहले Value का out-of-line slow path, Value का member function था और उसे implicit const Value* argument चाहिए था
  • इस संरचना में caller को Value को stack पर allocate करना पड़ता था
  • Fil-C++ में हर stack allocation, heap allocation होती है
    • इसलिए slow path को call करने वाला code, Value को heap पर allocate करता था
  • बदलाव के बाद इन methods को static बनाया गया और Value को by value pass किया गया
    • नतीजतन अलग allocation की ज़रूरत नहीं रही
  • performance प्रभाव 10% improvement रहा
    • इस बिंदु पर Zef, CPython 3.10 से 2.6 गुना धीमा था
    • Lua 5.4.7 से 5.8 गुना धीमा
    • QuickJS-ng 0.14.0 से 1.65 गुना धीमा
    • शुरुआती बिंदु की तुलना में 13.6 गुना तेज़

• ऑप्टिमाइज़ेशन #15: DotSetRMW duplication हटाना

  • कुछ duplicate code हटाया गया
  • उम्मीद थी कि constructCache<> द्वारा specialize होने वाले template functions में machine code reduction फायदेमंद हो सकता है
  • वास्तविक नतीजा: performance पर कोई असर नहीं

• ऑप्टिमाइज़ेशन #16: sqrt specialization

  • inline cache call को सही function तक अच्छी तरह route करता है, लेकिन सिर्फ objects पर काम करता है
  • non-object मामलों में Binary<>, Unary<>, Value::callRMW<> fast path इस बात पर निर्भर करते हैं कि receiver int या double है या नहीं
  • यह तरीका सिर्फ parser द्वारा पहचाने जाने वाले operators पर लागू होता है
    • value.sqrt जैसे रूपों पर लागू नहीं होता
  • इस बदलाव से Dot, value.sqrt के लिए specialize कर सकता है
  • performance प्रभाव 1.6% improvement रहा
    • इस बिंदु पर Zef, CPython 3.10 से 2.6 गुना धीमा था
    • Lua 5.4.7 से 5.75 गुना धीमा
    • QuickJS-ng 0.14.0 से 1.6 गुना धीमा
    • शुरुआती बिंदु की तुलना में 13.8 गुना तेज़

• ऑप्टिमाइज़ेशन #17: toString specialization

  • लगभग पिछले optimization जैसी ही विधि से toString specialization लागू की गई
  • इस बदलाव में int को string में बदलते समय होने वाली allocation count reduction logic भी शामिल थी
  • performance प्रभाव 2.7% improvement रहा
    • इस बिंदु पर Zef, CPython 3.10 से 2.5 गुना धीमा था
    • Lua 5.4.7 से 5.6 गुना धीमा
    • QuickJS-ng 0.14.0 से 1.6 गुना धीमा
    • शुरुआती बिंदु की तुलना में 14.2 गुना तेज़

• ऑप्टिमाइज़ेशन #18: array literal specialization

  • my whatever = [1, 2, 3] जैसे code में Zef में array aliasable और mutable होने के कारण नया array allocate करना ज़रूरी है
  • बदलाव से पहले हर execution पर AST के अंदर उतरकर 1, 2, 3 को हर बार recursively evaluate किया जाता था
  • इस बदलाव में ArrayLiteral node को constant array allocation cases के लिए specialize किया गया
  • performance प्रभाव 8.1% improvement रहा
    • इस बिंदु पर Zef, CPython 3.10 से 2.3 गुना धीमा था
    • Lua 5.4.7 से 5.2 गुना धीमा
    • QuickJS-ng 0.14.0 से 1.5 गुना धीमा
    • शुरुआती बिंदु की तुलना में 15.35 गुना तेज़

• ऑप्टिमाइज़ेशन #19: Value::callOperator में सुधार

  • पहले Value को reference से pass न करने पर जो speedup मिला था, वही optimization callOperator slow path पर भी लागू किया गया
  • performance प्रभाव 6.5% improvement रहा
    • इस बिंदु पर Zef, CPython 3.10 से 2.2 गुना धीमा था
    • Lua 5.4.7 से 4.9 गुना धीमा
    • QuickJS-ng 0.14.0 से 1.4 गुना धीमा
    • शुरुआती बिंदु की तुलना में 16.3 गुना तेज़

• ऑप्टिमाइज़ेशन #20: बेहतर C++ options

  • Fil-C++ में अनावश्यक RTTI और libc++ hardening को disable किया गया
  • C++ code में खुद कोई बदलाव नहीं था, सिर्फ build system configuration changes शामिल थे
  • performance प्रभाव 1.8% improvement रहा
    • इस बिंदु पर Zef, CPython 3.10 से 2.1 गुना धीमा था
    • Lua 5.4.7 से 4.8 गुना धीमा
    • QuickJS-ng 0.14.0 से 1.35 गुना धीमा
    • शुरुआती बिंदु की तुलना में 16.6 गुना तेज़

• ऑप्टिमाइज़ेशन #21: assert disable करना

  • आख़िरी optimization के रूप में assertion को default रूप से disable किया गया
  • मौजूदा code, Fil-C-विशिष्ट ZASSERT macro का इस्तेमाल करता था
    • यानी assert हमेशा चलती थी
  • बदलाव के बाद अंदरूनी ASSERT macro का उपयोग किया गया
    • assert सिर्फ तब चलती है जब ASSERTS_ENABLED सेट हो
  • इस बदलाव में code को Yolo-C++ में build होने लायक बनाने वाले अन्य fixes भी शामिल थे
  • उम्मीद के उलट कोई speedup नहीं मिली

Yolo-C++ के नतीजे और सीमाएँ

• code को Yolo-C++ से compile करने पर 4 गुना speedup मिली
• लेकिन यह तरीका sound नहीं है और suboptimal है
  • sound न होने की वजह यह है कि मौजूदा Fil-C++ GC calls, calloc calls में बदल जाती हैं
  • नतीजतन memory free नहीं होती, और काफ़ी देर तक चलने वाले workloads में interpreter memory exhaustion तक पहुँच जाता है
  • ScriptBench1 में test duration छोटी होने के कारण memory exhaustion नहीं हुई
• suboptimal होने की वजह यह है कि असली GC allocator, glibc 2.35 के calloc से तेज़ है
• इसलिए कहा गया कि अगर Yolo-C++ port में real GC जोड़ दी जाए, तो 4 गुना से भी ज़्यादा speedup संभव हो सकती है
• इस प्रयोग में GCC 11.4.0 का उपयोग किया गया
• इस बिंदु पर Zef

  • CPython 3.10 से 1.9 गुना तेज़

  • Lua 5.4.7 से 1.2 गुना धीमा

  • QuickJS-ng 0.14.0 से 3 गुना तेज़

    • शुरुआती बिंदु की तुलना में 67 गुना तेज़

कच्चा benchmark डेटा

• benchmark के execution time की इकाई सेकंड है
• तालिका में प्रत्येक interpreter के लिए nbody, splay, richards, deltablue, geomean शामिल हैं

• Python 3.10

  • nbody 0.0364
  • splay 0.8326
  • richards 0.0822
  • deltablue 0.1135
  • geomean 0.1296

• Lua 5.4.7

  • nbody 0.0142
  • splay 0.4393
  • richards 0.0217
  • deltablue 0.0832
  • geomean 0.0577

• QuickJS-ng 0.14.0

  • nbody 0.0214
  • splay 0.7090
  • richards 0.7193
  • deltablue 0.1585
  • geomean 0.2036

• Zef Baseline

  • nbody 2.9573
  • splay 13.0286
  • richards 1.9251
  • deltablue 5.9997
  • geomean 4.5927

• Zef Change #1: Direct Operators

  • nbody 2.1891
  • splay 12.0233
  • richards 1.6935
  • deltablue 5.2331
  • geomean 3.9076

• Zef Change #2: Direct RMWs

  • nbody 2.0130
  • splay 11.9987
  • richards 1.6367
  • deltablue 5.0994
  • geomean 3.7677

• Zef Change #3: Avoid IntObject

  • nbody 1.9922
  • splay 11.8824
  • richards 1.6220
  • deltablue 5.0646
  • geomean 3.7339

• Zef Change #4: Symbols

  • nbody 1.5782
  • splay 9.9577
  • richards 1.4116
  • deltablue 4.4593
  • geomean 3.1533

• Zef Change #5: Value Inline

  • nbody 1.4982
  • splay 9.7723
  • richards 1.3890
  • deltablue 4.3536
  • geomean 3.0671

• Zef Change #6: Object Model and Inline Caches

  • nbody 0.3884
  • splay 3.3609
  • richards 0.2321
  • deltablue 0.6805
  • geomean 0.6736

• Zef Change #7: Arguments

  • nbody 0.3160
  • splay 2.6890
  • richards 0.1653
  • deltablue 0.4738
  • geomean 0.5077

• Zef Change #8: Getters

  • nbody 0.2988
  • splay 2.6919
  • richards 0.1564
  • deltablue 0.4260
  • geomean 0.4809

• Zef Change #9: Setters

  • nbody 0.2850
  • splay 2.6690
  • richards 0.1514
  • deltablue 0.4072
  • geomean 0.4651

• Zef Change #10: callMethod inline

  • nbody 0.2533
  • splay 2.6711
  • richards 0.1513
  • deltablue 0.4032
  • geomean 0.4506

• Zef Change #11: Hashtable

  • nbody 0.1796
  • splay 2.6528
  • richards 0.1379
  • deltablue 0.3551
  • geomean 0.3906

• Zef Change #12: std::optional से बचाव

  • nbody 0.1689
  • splay 2.6563
  • richards 0.1379
  • deltablue 0.3518
  • geomean 0.3839

• Zef Change #13: Specialized Arguments

  • nbody 0.1610
  • splay 2.5823
  • richards 0.1350
  • deltablue 0.3372
  • geomean 0.3707

• Zef Change #14: Improved Value Slow Paths

  • nbody 0.1348
  • splay 2.5062
  • richards 0.1241
  • deltablue 0.3076
  • geomean 0.3367

• Zef Change #15: DotSetRMW::evaluate का deduplication

  • nbody 0.1342
  • splay 2.5047
  • richards 0.1256
  • deltablue 0.3079
  • geomean 0.3375

• Zef Change #16: Fast sqrt

  • nbody 0.1274
  • splay 2.5045
  • richards 0.1251
  • deltablue 0.3060
  • geomean 0.3322

• Zef Change #17: Fast toString

  • nbody 0.1282
  • splay 2.2664
  • richards 0.1275
  • deltablue 0.2964
  • geomean 0.3235

• Zef Change #18: Array Literal Specialization

  • nbody 0.1295
  • splay 1.6661
  • richards 0.1250
  • deltablue 0.2979
  • geomean 0.2992

• Zef Change #19: Value callOperator Optimization

  • nbody 0.1208
  • splay 1.6698
  • richards 0.1143
  • deltablue 0.2713
  • geomean 0.2810

• Zef Change #20: Better C++ Configuration

  • nbody 0.1186
  • splay 1.6521
  • richards 0.1127
  • deltablue 0.2635
  • geomean 0.2760

• Zef Change #21: No Asserts

  • nbody 0.1194
  • splay 1.6504
  • richards 0.1127
  • deltablue 0.2619
  • geomean 0.2759

• Zef in Yolo-C++

  • nbody 0.0233
  • splay 0.3992
  • richards 0.0309
  • deltablue 0.0784
  • geomean 0.0686