2GB/s से अधिक की गति से protobuf पार्स करना: C भाषा में tail calls से प्यार होने की वजह (2021)

• Tail Call: फ़ंक्शन के return होने से ठीक पहले किया गया फ़ंक्शन कॉल। जब Tail Call optimization होती है, तो jmp निर्देश का उपयोग होता है और call stack कम हो जाता है.
• फायदे:
  • stack memory का उपयोग O(n) से O(1) तक घट जाता है.
  • फ़ंक्शन कॉल के performance overhead को हटाकर इसे एक कुशल iterative control structure की तरह इस्तेमाल किया जा सकता है.

इंटरप्रेटर लूप की समस्याएँ

• समस्याएँ:
  • जैसे-जैसे फ़ंक्शन बड़ा होता है और control flow अधिक जटिल होता है, महत्वपूर्ण डेटा को register में बनाए रखना कठिन हो जाता है.
  • अगर fast path और slow path आपस में मिले हुए हों, तो code quality गिर जाती है.

Tail Call का उपयोग करके इंटरप्रेटर लूप में सुधार

• समाधान: Tail Call का उपयोग करके हर काम को छोटे फ़ंक्शनों में बाँटा जाता है, और हर फ़ंक्शन अगले काम को Tail Call के रूप में कॉल करता है.
• फायदे:
  • register allocation को नियंत्रित किया जा सकता है.
  • fast path और slow path को अलग रखकर code quality बनाए रखी जा सकती है.
  • स्वतंत्र instruction sequence का optimization किया जा सकता है.

सीमाएँ

• non-Tail Call होने पर समस्या: अगर non-Tail Call मौजूद हो, तो stack frame बनता है और डेटा stack में सेव होता है, जिससे performance गिरती है.
• जटिल exception handling: अगर exception handling जटिल हो, तो code duplication और complexity बढ़ जाती है.
• portability समस्या: musttail attribute standard नहीं है, इसलिए सभी compilers में इसका समर्थन नहीं मिलता.

GN⁺ का सार

• Tail Call optimization performance सुधार में महत्वपूर्ण भूमिका निभाती है, और खासकर Protobuf parsing में बड़े परिणाम दिखाती है.
• यह तकनीक C में लिखे गए प्रमुख language interpreters (Python, Ruby, PHP, Lua आदि) पर भी लागू की जा सकती है.
• musttail attribute की portability समस्या एक ऐसी चुनौती है जिसे हल किया जाना बाकी है.
• समान प्रकार की सुविधा देने वाले प्रोजेक्ट्स में LuaJIT, wasm3 WebAssembly interpreter आदि शामिल हैं.

[GN⁺]

Hacker News राय

• C मानक प्रस्ताव में "return goto (expression);" के रूप में tail call शामिल है

  • [[musttail]] को standardize करने की तुलना में इसमें local objects की lifetime सुनिश्चित रहती है और व्यापक escape analysis की आवश्यकता नहीं होती

• Rust उत्साही लोगों के लिए "become" keyword जोड़ने वाला एक पुराना RFC था

  • 2018 edition के लक्ष्यों पर ध्यान केंद्रित करने के लिए इसे टाल दिया गया था, लेकिन हाल में इस पर फिर चर्चा हो रही है
  • इसके फिर से आने की संभावना है

• C++ में interpreter की गति बढ़ाने का तरीका मुख्यतः computed goto का उपयोग करना है

  • इससे calling convention की समस्याओं से बचा जा सकता है
  • computed goto style या tail style का उपयोग करने पर branch predictor पर दबाव कम हो सकता है

• tail call का उपयोग करके context switch करने की समस्या यह है कि calling convention का उपयोग करने वाले functions की आवश्यकता होती है

  • function के अंत में state बहाल करने के लिए registers व्यर्थ जाते हैं
  • luajit remake ब्लॉग में विकल्प और विश्लेषण दिया गया है

• आशा है कि [[musttail]] attribute GCC, Visual C++, और अन्य लोकप्रिय compilers तक फैलेगा

  • [[musttail]] attribute को GCC में जोड़ने की प्रक्रिया चल रही है

• C++ support का उल्लेख करते हुए कहा गया कि C++ में tail calls लगभग नहीं के बराबर हैं

  • उदाहरण के लिए, destructor वाले class के object को return करना tail call नहीं है

• यह जानने की जिज्ञासा है कि C++ [[musttail]] function में exception फेंकने पर क्या होता है

  • पूछा गया है कि क्या exception stack पूरी तरह अलग हो जाती है

• उल्लेख है कि साधारण उदाहरणों में अच्छे code generation के लिए __attribute__((musttail)) की आवश्यकता नहीं होती

  • error handling function call की गति की इतनी अधिक चिंता नहीं होगी
  • एक विशेष संरचना भरोसेमंद jump table बनाती है

• trampoline का उपयोग करके return होने वाले function pointer को बाहरी loop में call करने वाली विधि की गति को लेकर जिज्ञासा है

  • इस विधि का लाभ यह है कि यह portable C के फायदे रखती है

• [[musttail]] से wrap किए गए exception path के उदाहरण को और स्पष्ट करने का अनुरोध है

  • यह समझाया गया है कि [[musttail]] stack frame setup और register spilling को क्यों रोकता है
  • stack frame setup और register spilling तभी होते हैं जब exception path वास्तव में call किया जाता है
  • exception path बहुत कम call होता है, इसलिए performance पर इसका बड़ा असर नहीं पड़ता
  • branch prediction के प्रभाव के कारण अतिरिक्त काम की संभावना fast path को धीमा कर सकती है