Peredvizhnikov इंजन: C++20 में लिखा गया lock-free गेम इंजन

• C++20 में लिखा गया एक पूर्ण lock-free गेम इंजन, जो भाषा के coroutine primitives के ऊपर concurrent computation का actor model लागू करता है
• actor model abstraction का उपयोग करके threads के बीच synchronization की बारीकियों से अलग रहते हुए जटिल parallel logic विकसित किया जा सकता है
• पूर्ण lock-free implementation मनचाहे thread termination की स्थिति में भी progress guarantee, deadlock prevention, महत्वपूर्ण events पर predictable latency, और fault tolerance प्रदान करता है
• यह गारंटी देता है कि worker threads में से कोई एक asynchronous रूप से बंद हो जाए तब भी इंजन चलता रहेगा
• implementation में Software Transactional Memory, lock-free queue, lock-free serialization primitives, std::atomic_shared_ptr, lock-free scheduler, lock-free memory allocator, और compile-time DAG आदि शामिल हैं
• lock-free algorithms, design rationale, और benchmarks को Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler दस्तावेज़ में कवर किया गया है
• data-oriented design को समर्थन देने के लिए component-level access के लिए optimized और बड़े data sets को support करने वाला एक in-memory database लागू किया गया है
• in-memory database Flat Hash Map और Bitwise Trie with Bitmap data structures पर आधारित है
• वर्तमान में समर्थित platform केवल Linux है, और source build के लिए Clang++ 16 आवश्यक है
• source code GPLv3 लाइसेंस के तहत उपलब्ध है, और कुछ या पूरे code को किसी अन्य लाइसेंस के तहत उपयोग करने की अनुमति case-by-case आधार पर दी जा सकती है

[GN⁺]

Hacker News की राय

• Actor framework में method pointer queue के लिए साधारण std::deque का इस्तेमाल किया गया है, और message को queue में डालते समय Benaphore तरीके से lock किया जाता है
  असल में Futex की तरह atomic operations और lock primitives को साथ इस्तेमाल किया जाता है, लेकिन मेरा lock primitive retry count के आधार पर spinlock/mutex के combination की तरह काम करता है। Benchmarks में message push function का block होना बेहद दुर्लभ है, और operating system context switch की संभावना भी कम है, इसलिए कभी-कभार locked thread swap out हो भी जाए तो यह lock-free algorithm की लागत को सही ठहराने जितनी बार नहीं होता
  संक्षेप में, non-lock-free queue lock-free queue से कहीं तेज़ होती है, लेकिन यह स्वीकार करना होगा कि context switch की वजह से, जिसमें किसी को lock नहीं मिलता, बहुत दुर्लभ मौकों पर लंबी latency आ सकती है। आधुनिक hardware पर प्रति worker thread प्रति सेकंड 1 करोड़ messages queue में डाले जा सकते हैं

  • “असल में Futex” कहा गया, लेकिन Benaphore काफी पुराना idea है और Futex बस “Linux-style Benaphore” नहीं है
    मुख्य बात यह है कि kernel object, यानी अलग lock primitive, वास्तव में जरूरी नहीं होता। यही वह बिंदु है जहां यह idea “सबको पता तरीका” से “operating system में तुरंत जोड़ी जाने वाली feature” में बदल जाता है
    Futex design में collision handling के लिए operating system synchronization object के बजाय, operating system address→thread mapping की list बनाए रखता है। जब thread T address X के futex पर sleep करता है, तो list में X को T की ओर point करने के लिए जोड़ा जाता है, और जब X futex को wake करने का request आता है, तो operating system list scan करके T को wake करता है
    फर्क limitations में दिखता है। Benaphore जैसी चीज़ें महंगे system-wide resources थीं, इसलिए मुझे याद है कि BeOS प्रति machine सिर्फ करीब 65536 की अनुमति देता था। लेकिन Futex तो बस memory है, इसलिए उस पर limit लगाने की कोई वजह नहीं है
  • ऐसे दिलचस्प लेख में code link होना चाहिए। इससे दावे भी साबित होंगे, और मेरे जैसे लोग, जिन्हें idea रोचक लगता है, तुरंत implementation देखना चाहेंगे
  • यह details पर बहुत निर्भर करता है। contention ज्यादा हो तो performance तेजी से गिरती है, और atomic instruction तक bottleneck बन सकता है(https://stackoverflow.com/q/2538070)
    कई मामलों में बस lock इस्तेमाल करके चिंता न करना ठीक है—यह observation सही लगता है। लेकिन कुछ applications या situations में इससे बेहतर किया जा सकता है। अगर consumer एक ही lock operation में queue के सभी items निकाल ले, और producers consumer को signal भेजें, तो सावधानी रखने पर queue efficiency और throughput बढ़ सकती है। उदाहरण के लिए, हर item डालने पर signal न भेजें; केवल तब भेजें जब queue खाली से non-empty हो जाए
  • क्या lock-free data structures का मतलब low contention में throughput बढ़ाने से ज्यादा contention के असर को कम करना नहीं है?
  • “लागत स्वीकार्य है” वाली बात उन लोगों के लिए exception है जिनकी strong requirement है कि ऊपर बताई गई unpredictable और दुर्लभ लंबी latency बिल्कुल भी नहीं होनी चाहिए

• Lock-free scheduler निश्चित रूप से दिलचस्प दिखता है, खासकर event broadcast की linearizability ध्यान खींचती है। हालांकि paper benchmark में 12 actor pairs (और 12 cores?) के लिए peak 43,500 messages per second है, और single-core graph भी करीब 5,000 messages per second दिखाता है, जो इस तरह के benchmark के लिए हैरान करने वाला कम है
  Engine Linux और, इससे भी महत्वपूर्ण, x86 की मांग करता है (assembly instructions के कारण), इसलिए अभी reproduce नहीं कर पाया हूं, लेकिन एक actor pair से कम से कम करीब 10 लाख requests per second की उम्मीद करूंगा। Erlang जैसे मामलों को सोचें तो इससे कम होने पर overhead निषिद्ध स्तर तक बड़ा हो जाता है
  यह engine message passing पर focus करता है, लेकिन अनुभव के आधार पर यह तरीका संभालना बहुत मुश्किल है। State machines कठिन होती हैं, और कई sub-actors के साथ काम करते समय और कठिन हो जाती हैं। मूल रूप से मुझे लगता है कि actors message passing से ज्यादा बिना locks के state को isolate करने के बारे में हैं। Swift actors ने यह सही किया है: message के बजाय method calls इस्तेमाल करने से reasoning आसान होती है, साथ ही runtime को उन points की अतिरिक्त जानकारी मिलती है जहां context बदल सकता है, और scheduler को जरूरी तौर पर बीच में लाना नहीं पड़ता। Shared state धीमी होती है और scalability को नुकसान पहुंचाती है
  हाल ही में C++20 coroutines से Swift actors जैसी चीज़ implement करने वाली header-only library बनाई है। दिलचस्पी हो तो “coroactors” खोज सकते हैं। Contention न होने पर करीब 1 करोड़ requests per second, और contention होने व scheduler पर निर्भर रहने पर 10 लाख–30 लाख requests per second को भी मैंने बहुत ज्यादा overhead माना। खासकर mutex-protected shared state के normal method calls से तुलना करें तो। Coroutines आसानी से फैल जाती हैं—धीरे-धीरे अधिक functions async coroutines बन जाते हैं, और non-trivial codebase में coroutine calls या message passing बहुत बढ़ जाती है। इसलिए overhead जितना हो सके उतना कम होना चाहिए, वरना useful काम करने के बजाय ज्यादा समय task switching में खर्च होगा

• इसे actor आधारित बताया गया है, और समझाया गया है कि actor को message भेजना mutex के तहत actor function चलाने के बराबर है। यानी N threads message भेजें तब भी actor code चलाने वाला thread 1 ही होता है, इसलिए mutex की तरह serialized हो जाता है
  इसलिए तकनीकी रूप से यह “पूरी तरह lock-free” हो सकता है, लेकिन actor इस्तेमाल करने तक parallelization improvement नहीं है

  • ज़रूरी नहीं कि ऐसा ही हो। mutex आधारित actor में, अगर actor thread रुक जाए तो जब तक मूल thread resume नहीं होता, वह mutex, यानी actor code, locked ही रहता है। रुके हुए thread के owned mutex के locked होने की वजह से, parallelism ज्यादा होने पर भी उस actor code को “restart” या “resume” नहीं किया जा सकता
    यह implementation पहले से चल रहे लेकिन रुके हुए actor के काम को किसी दूसरे parallel thread द्वारा उठाकर आगे बढ़ाने देने के लिए restartable functions पर काफी निर्भर करता है। बेहतरीन design document के पेज 3 को देखें: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
    इसलिए सख्ती से कहें तो यह “अधिक parallel” नहीं भी हो सकता (क्योंकि actors की संख्या वही है), लेकिन ऐसा लगता है कि same work set पूरा करने के लिए यह ज्यादा parallelism का बेहतर उपयोग करता है
  • “actor को message भेजना mutex के तहत actor function चलाने के बराबर है” यह बात कहाँ है? मेरी समझ में actor model message passing और asynchronous execution का मतलब है। बल्कि अगर N actors हों, तो N threads parallel में चल सकते हैं
  • यह सही है कि parallelization improvement नहीं है, लेकिन यह parallelism घटाता भी नहीं है। यह concurrency के बारे में सोचने का अलग तरीका है, और मेरे हिसाब से आसान तरीका है
    अगर सोचना आसान हो, तो यह भी बेहतर दिखता है कि same resources पर contention कहाँ पैदा होगा, और असल में potential parallelism सुधारने में मदद मिलती है। अगर SMP speed बढ़ाने का कोई खास मौका दिखे, तो actor model से थोड़ा हटकर message queue को multiple threads से receive कराया जा सकता है, और अगर यह संभव न हो तो और actors जोड़कर data को बेहतर split किया जा सकता है

• क्या किसी ने STM के highly contended critical sections को traditional mutex implementation से compare करते हुए debug या profile किया है? आखिर shared memory concurrent access को mediate करने वाली कोई चीज तो चाहिए, और free lunch नहीं है। mutex बहुत अच्छी तरह optimize, profile और समझे जाते हैं
  वहीं STM भी उसी स्तर पर है या नहीं, यह मुझे पक्का नहीं पता। क्या transactions अनिश्चित काल तक(?) retry हो सकते हैं?

  • इस case में mediator scheduler है। असल में वही async blocks को call करता है और fail होने पर potentially retry करता है। original code में एक बार में एक access guarantee करने के लिए atomic blocks, blocks का sequential execution, state वाले blocks आदि हैं
    मुख्य हिस्सा scheduler.cpp है और यह std::coroutines का उपयोग करता है
    यह दूसरी languages के async/await जैसा है। scheduler में tasks (coroutines) की queue और उन्हें चलाने के लिए thread pool (N>0) होता है
    यहाँ data वाले tasks आपस में messages exchange करते हैं। memory usage बढ़ने की कीमत पर locks की जरूरत नहीं पड़ती
  • असल में starvation-free STM में transaction retry count सीमित होता है। एक उदाहरण 2PLSF है, और इसके अलावा भी कई तरीके हैं https://zenodo.org/record/7886718

• BEAM जैसा लगता है?
  https://youtu.be/bo5WL5IQAd0?feature=shared

• ऐसे engine को debug करना कितना मुश्किल होगा, इसका ज़िक्र मैंने नहीं देखा

• implementation पढ़ने का समय नहीं है, लेकिन README देखकर यह game threads के बीच classic distributed system जैसा लगता है। retry-backoff जैसे patterns common होंगे

  • paper implementation में गहराई तक गए बिना ज्यादा विस्तार से समझाता है, और यह उससे काफी अधिक advanced दिखता है
    https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...

• lock-free सुनने में cool लगता है, लेकिन मेरे हिसाब से meaningful level पर atomic operations इस्तेमाल करने वाले code के साथ formal और हो सके तो machine-verified proof होना चाहिए। sequential consistency न होने पर atomic ordering को सही तरीके से इस्तेमाल करना बहुत कठिन है। मैंने कई बार गलत लिखा code देखा है, और उससे बनने वाले bugs सबसे खराब होते हैं

• game demo कहाँ है? आजकल game engine मानने के लिए actual tools, Maya या 3DSMax जैसे exporters, और collaboration tools, metrics, notifications जैसी चीजें भी चाहिए

  • सहमत नहीं हूँ। “game engine” का मतलब जरूरी नहीं कि “Unity या Unreal को replace कर सकने वाली चीज” हो

• “lock-free” कहा गया है, लेकिन अभी ऐसा लगता नहीं
  export std::mutex iolock{};
export std::mutex errlock{};
SDL_PollEvent