C भाषा में कोरूटीन (2000)
(chiark.greenend.org.uk)- जब producer और consumer कोड आपस में डेटा पास करते हैं, और एक पक्ष को callee के रूप में उलटकर लिखा जाता है, तो मूल रूप से दिखने वाला algorithmic structure state transitions में दब जाना आसान होता है
- Knuth-शैली के coroutine एक ऐसा मॉडल है जिसमें दो routines अपनी execution position सहेजते हुए control एक-दूसरे को देते हैं, लेकिन C की stack-based call structure में इसे portable तरीके से सीधे लागू करना कठिन है
- इस लेख की मुख्य trick C syntax का उपयोग करती है, जिसमें
switchके sub-block मेंcaseरखा जा सकता है, और__LINE__macro के जरिएreturnके बाद वाली position पर फिर से enter करने वाली implicit state machine बनाई जाती है crBegin,crReturn,crFinishmacros से decompressor और parser की मूल loop structure बनाए रखी जा सकती है, लेकिन जिन local variables को preserve करना हो वेstaticहोने चाहिए, औरcrReturnको explicitswitchके अंदर या उसी line पर नहीं रखना चाहिए- वास्तविक code में re-entrancy और multithread constraints के कारण context struct पास करने वाला improved form चाहिए;
coroutine.hsimplescrmacros और re-entrantccrmacros दोनों देता है
producer और consumer को जोड़ते समय पैदा होने वाली structural समस्या
- बड़े programs में अक्सर एक code डेटा बनाता है और दूसरा code उसे consume करता है; ऐसे में कौन-सा पक्ष caller होगा और कौन-सा callee, यह design को कठिन बना देता है
- उदाहरण दो छोटे routines से बना है
- run-length decompression code
getchar()से input पढ़ता है औरemit()से characters को एक-एक करके output करता है - parser code
getchar()से characters पढ़कर alphabetic continuous runs कोWORD, और बाकी characters कोPUNCTके रूप में process करता है
- run-length decompression code
- दोनों routines को अलग-अलग देखें तो वे natural लगते हैं, लेकिन decompressor का
emit()output सीधे parser केgetchar()input में जाना हो, तो दोनों के बीच जोड़ने के लिए कोई structure चाहिए - इसे दो processes या दो threads के बीच pipe से भी हल किया जा सकता है
- decompressor का
emit()pipe में लिखता है, और parser काgetchar()दूसरी तरफ से पढ़ता है - यह तरीका simple और robust है, लेकिन heavy और कम portable है, इसलिए simple काम के लिए अक्सर लोग threads में बांटना नहीं चाहते
- decompressor का
function rewrite से होने वाला readability loss
- पारंपरिक solution communication channel के एक end को callable function form में rewrite करना है
- decompressor को हर call पर एक character return करने वाले function में बदल दें, तो existing parser
getchar()की जगहdecompressor()call कर सकता है - उल्टा, parser को ऐसा function बना दें जो हर character मिलने पर call हो, तो existing decompression code
emit()की जगहparser()call कर सकता है - दोनों को बदलना जरूरी नहीं; केवल एक पक्ष बदलने से भी उन्हें जोड़ा जा सकता है, लेकिन rewritten code original की तुलना में कहीं ज्यादा पढ़ने में कठिन हो जाता है
- original decompressor और parser में algorithm flow loops के भीतर natural तरीके से दिखता है
- rewritten form
staticstate variables औरswitchstate transitions पर निर्भर करता है, जिससे compression format या parser grammar को code से पढ़ना कठिन हो जाता है
- लक्ष्य है कि किसी भी पक्ष को explicit state machine की तरह उलटकर लिखे बिना उन्हें जोड़ा जाए
Knuth-शैली के coroutine और C की सीमाएँ
- Donald Knuth का coroutine solution caller और callee का फर्क छोड़कर, दो processes को सहयोग करने वाली बराबर entities के रूप में देखता है
- इस model का call principle सामान्य function call से अलग है
- current execution position को stack में नहीं, बल्कि किसी अलग जगह में save किया जाता है
- दूसरी routine की आखिरी saved execution position पर jump किया जाता है
- decompressor जब character emit करता है, तो अपना program counter save करके parser की saved position पर जाता है
- parser को अगला character चाहिए होने पर वह अपना program counter save करके decompressor की saved position पर जाता है
- control दोनों routines के बीच जरूरत के अनुसार आगे-पीछे जाता रहता है
- यह तरीका theoretically अच्छा है, लेकिन practically केवल assembly language में ही संभव है
- C जैसी high-level language stack-based structure पर निर्भर करती है, इसलिए functions के बीच control transfer में एक पक्ष caller और दूसरा callee होना ही चाहिए
- portable C code में pure coroutine approach Unix pipe solution जितनी ही कम practical है
C में “return and continue” की नकल
- C में जरूरी behavior यह है कि callee function
returnकरने के बाद, अगली call में उसीreturnके ठीक बाद वाली position से execution जारी रखे — यानी return and continue - उदाहरण के लिए, अगर
for (i = 0; i < 10; i++) return i;जैसी function 10 बार call होने पर 0 से 9 तक क्रम से return करे, तो यह ideal होगा - पहला implementation state variable और
gotoका उपयोग करता है- function start और हर
returnके बाद labels रखे जाते हैं - calls के बीच कायम रहने वाला
statevariable अगले resume label की ओर इशारा करता है - function start पर
switch(state)से appropriate label पर जाया जाता है returnसे ठीक पहले अगली call में लौटने वाला labelstateमें save किया जाता है
- function start और हर
- यह तरीका काम करता है, लेकिन label management manual होने के कारण maintenance burden बड़ा है
- हर बार
returnजोड़ने पर नया label बनाना और initialswitchमें भी जोड़ना पड़ता है returnहटाने पर corresponding label भी हटाना पड़ता है- function body और
switchlist की consistency लगातार बनाए रखनी पड़ती है
- हर बार
Duff’s device से छिपी हुई state machine
- C का प्रसिद्ध Duff’s device इस syntax का उपयोग करता है कि
switchसे संबंधितcasestatements उसके sub-block के भीतर भी रखे जा सकते हैं - इस property को coroutine trick पर लागू करने से,
switchकिसgotoको execute करना है यह चुनने के बजायswitchखुद re-entry jump की तरह काम करता है - basic form इस प्रकार है
static int stateअगले resume point को save करता है- function start पर
switch(state) { case 0: ... }से entry होती है returnसे ठीक पहलेstateमें अगलाcasevalue save किया जाता हैreturnके ठीक बाद संबंधितcaselabel रखा जाता है
- इसे macro में wrap करने पर coroutine जैसा दिखने वाला interface बन जाता है
crBegin:static int state=0; switch(state) { case 0:को hide करता हैcrReturn:statesave करता है, value return करता है, फिर उसी position परcaselabel रखता हैcrFinish: open block को close करता है
crReturnकोdo ... while(0)में wrap किया गया है, इसलिएifऔरelseके बीच braces के बिना use करने पर भी syntax problem नहीं होती- शुरुआत में
crReturn(1, i)की तरह state number manually देना पड़ता है, लेकिन ANSI C के__LINE__macro का उपयोग करने पर current source line number को state value के रूप में use किया जा सकता है - इस improvement के बाद केवल
crReturn(x)लिखना काफी है, लेकिन यह rule जुड़ता है कि एक ही line में दोcrReturnनहीं रखने चाहिए
macro usage rules और examples
- macro-based coroutine कुछ rules पर आधारित हैं
- function body को
crBeginऔरcrFinishसे wrap करें crReturnके पार preserve किए जाने वाले local variables कोstaticdeclare करें- explicit
switchstatement के अंदर कभी भीcrReturnन रखें __LINE__-based implementation में same line पर दोcrReturnन रखें
- function body को
- decompressor example में original loop structure बनाए रखते हुए, character emit करते समय
emit(c)की जगहcrReturn(c)use किया जाता है - parser example में नया character चाहिए होने पर
crReturn()से caller को लौटा जाता है, और अगली call में parametercमें नया character मिल चुके state से execution जारी रहता है - parser में एक छोटा structural change है
- पहला character function entry के समय पहले से
cमें है, इसलिए original loop की शुरुआत वालेgetchar()के बराबरcrReturnको loop के अंत में move किया जाता है - चाहें तो parser के लिए initialization call जरूरी है, ऐसा भी तय किया जा सकता है
- पहला character function entry के समय पहले से
- दोनों routines को coroutine macros से बदलना जरूरी नहीं; केवल एक पक्ष को बदलकर दूसरे को caller के रूप में रखा जा सकता है
- नतीजतन, ANSI C, preprocessor, और
switchके कम इस्तेमाल होने वाले syntax को मिलाकर producer और consumer के बीच data transfer को explicit state machine rewrite के बिना संभाला जाता है
coding standard और algorithmic clarity का टकराव
- यह technique सामान्य coding standards का काफी उल्लंघन करती है
- macro के अंदर unmatched braces आते हैं
- sub-block के अंदर
caseuse होता है crReturnएक ही macro मेंswitch,return,caseको hide करता है
- syntax structure छिपाने वाले macros को coding standards के हिसाब से clarity को नुकसान पहुंचाने वाला माना जा सकता है
- लेकिन explicit state machine में rewritten function भी छोटे
case STATEblocks और state transitions से बना होता है, इसलिए उसकी visual structuregotolabel blocks सूचीबद्ध करने वाले function से बहुत अलग नहीं होती - function जितना लंबा होता है, state machine rewrite original algorithmic structure को उतना ज्यादा बिगाड़ता है
- यह technique कुछ syntactic structure छिपाने के बदले algorithmic structure को बेहतर दिखाने की कोशिश वाला trade-off है
re-entrant improved form और provided code
- simple toy implementation
staticvariables पर निर्भर करता है, इसलिए re-entrant नहीं है और multithreaded use के लिए भी suitable नहीं है - real applications में same function को कई contexts से call करना और हर context के लिए last
returnके बाद से execution जारी रखना संभव होना चाहिए - improvement method context struct pointer को extra parameter के रूप में पास करना है
- local state और coroutine state variables दोनों को struct members बनाया जाता है
- loop counter जैसे variables को भी
iकी जगहctx->iकी तरह access करना पड़ता है - code थोड़ा और ugly हो जाता है, लेकिन re-entrancy problem हटाते हुए routine की overall structure बनाए रखता है
- C++ users coroutine को class member बना सकते हैं और local variables के बराबर state को class के अंदर रखकर scope को अधिक natural तरीके से handle कर सकते हैं
- उपलब्ध
coroutine.hइस coroutine trick को predefined macro set के रूप में implement करता हैscrprefix वाले macrosstaticvariables इस्तेमाल करने वाला simple form हैंccrprefix वाले macros re-entrant advanced form हैं- detailed documentation header file के comments में शामिल है
- Visual C++ 6 default debug setting “Program Database for Edit and Continue” में
__LINE__macro को अजीब तरीके से handle करता है, इसलिए यह trick उसे पसंद नहीं आती- VC++ 6 में coroutine use करने वाले program को compile करने के लिए Edit and Continue को बंद करना होगा
- project settings के “C/C++” tab, “General” category, “Debug info” setting में “Program Database for Edit and Continue” के अलावा कोई option चुनना होगा
- header file MIT license के तहत उपलब्ध है
related references और actual use
- Donald Knuth की The Art of Computer Programming, Volume 1, Section 1.4.2 pure form के coroutines को cover करती है
- Tom Duff की Duff’s device discussion में ऐसा संकेत है कि उन्होंने independently मिलती-जुलती coroutine trick सोची हो सकती है, और 2005-03-07 update में Tom Duff ने blog comment में इसकी पुष्टि की
- PuTTY का SSH protocol code इस coroutine trick को वास्तव में use करता है
- PuTTY case serious production code में दुर्लभ, strong C hacking level का है
1 टिप्पणियां
Hacker News की राय
C प्रोजेक्ट में API की complexity घटाने की कोशिश करते हुए मैं इस पेज पर कई बार वापस आया, और मुझे लगता है कि control flow की व्याख्या बेहतरीन है
इससे stack के अंदर-बाहर state को save करने और access के तरीकों के हिसाब से readability के फर्क को ज्यादा स्पष्ट रूप से सोचने में भी मदद मिली
अभी मेरा निष्कर्ष यह है कि C coroutines इस्तेमाल करनी हैं या नहीं, यह library user पर छोड़ना बेहतर है। उदाहरण के लिए Mongoose(https://github.com/cesanta/mongoose) async को event callbacks से handle करता है; ऐसी libraries को किसी पौराणिक cross-platform C coroutine या उससे भी खराब
std::threadमें port करने की कोशिश करने के बजाय, हर system के thread/task primitives से wrap करना कहीं ज्यादा सुविधाजनक है[1] https://www.chiark.greenend.org.uk/~sgtatham/putty/
[2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
Coroutines सचमुच शानदार concept हैं, और खासकर Microsoft वाले लोगों द्वारा प्रमुख रूप से प्रस्तुत CppCon के C++ coroutines videos देखना भी मजेदार है। “negative-cost abstraction” वाला hook भी काफी अच्छा है
कुछ साल पहले Meta के दोस्तों ने C++ coroutines इस्तेमाल करना शुरू किया था, और उन्होंने बताया कि आखिर में यह बड़ी गलती निकली। उन्हें compiler implementation bugs से जूझना पड़ा, और उनका trace करना काफी गंदा रहा होगा। Google में हम इंतजार कर रहे हैं कि google3/ में इसे ठीक से integrate करने वाले बेहतरीन लोग कब बताएंगे कि अब इसका इस्तेमाल किया जा सकता है
यह लेख Duff's device [1] के जरिए macro-based structured
gotoको C coroutine implementation strategy के रूप में समझाता है। मुख्य बात यह है किswitchblock के अंदर लगभग कहीं भीcasestatement रख सकते हैं; पूरी function कोswitchसे wrap करकेstaticvariable में coroutine की आखिरी return position save की जाती है और हरcoReturnकोcaseसे label किया जाता हैSustrik का C coroutines पर लेख भी रोचक हो सकता है [2]
[1] https://en.wikipedia.org/wiki/Duff%27s_device
[2] https://250bpm.com/blog:48/index.html
co_yield,co_return,co_awaitजैसा async code फायदे और नुकसान दोनों रखता हैgoogle3 के internal तरीके की तुलना में फायदा यह है कि code पढ़ते समय हर हिस्से की asynchronous प्रकृति साफ दिखती है। Google के कुछ programmers branch-level से आगे threading model जाने बिना ही काम करते रहे और बाद में गंभीर bugs बना बैठे
नुकसान ज्यादा सरल है। बहुत सारा code “शायद async हो सकता है” होने के कारण, समय के साथ सिर्फ इसलिए पूरा code async होता जाता है क्योंकि programmer उस mode में लिख रहा है। spinlock और yielding mutex में से क्या इस्तेमाल करना है, यह critical section के size और उस समय की threading situation के आधार पर तय होना चाहिए, लेकिन readability और consistency मिलाते-मिलाते पूरा project आसानी से एक तरफ झुक जाता है
मैं ऐसी threading language implementation के बारे में और जानना चाहूंगा जो default को किसी एक तरफ न रखे, और पिछले run की profile के आधार पर अगले run को code changes या bugs के बिना ज्यादा optimize करे
lc-addrlabels.hमें हैGCC की local labels feature भी इस्तेमाल की, जिससे
__LINE__का उपयोग पूरी तरह टल गया, और एक ही line में कईcoReturnभी रखे जा सकेswitchblock के अंदर लगभग कहीं भीcasestatement इस्तेमाल की जा सकती है, लेकिन यह feature खुद लगभग निश्चित रूप से intended feature हैलेख के नीचे भी लिखा है कि Duff ने यह भी समझ लिया था कि इसके ऊपर coroutines बनाई जा सकती हैं, लेकिन उन्होंने इस विचार को “घिनौना” माना
अगर C के
switchको कम expressive pattern matching की तरह सोचें तो “fallthrough” bug जैसा लगना आसान है, लेकिन ऐसा नहीं है। यह Fortran जैसी computedgotoकी ही श्रेणी का है; values का contiguous होना जरूरी नहीं और labels को ऊपर ही सब list करना भी जरूरी नहीं, इसलिए यह ज्यादा सुविधाजनक है। लिखते-लिखते लगता है कि यह computedCOMEFROMके ज्यादा करीब भी हो सकता है“व्यापक रूप से इस्तेमाल होने वाली high-level languages coroutines support नहीं करतीं” वाली बात 2000 में सही रही होगी, लेकिन आज C++20, Lua, Python, Ruby समेत कई languages support करती हैं
yieldkeyword भी शायद उसी समय या उसके ज्यादा देर बाद नहीं आया होगालेख के अंत में दिया गया सुधार—“context struct pointer को अतिरिक्त function argument के रूप में रखें, और सभी local state और coroutine state variables को उस struct के elements के रूप में declare करें”—closure implementation जैसा लगता है। जैसे callee को lambda बनाकर external variables/context/state का इस्तेमाल करने दिया जाए ताकि वह तय करे कि क्या करना है या किस value से करना है; मैं इसे इस तरह समझ रहा हूं, क्या यह सही है?
switchवाला तरीका बहुत दुर्लभ तो नहीं है, लेकिन आम तौर पर initialization function और coroutine function को पास किया जाने वाला state pointer रखा जाता हैembedded projects में मैंने यह तरीका काफी इस्तेमाल किया है; जैसे एक coroutine motor acceleration/deceleration संभालता था और दूसरा coroutine सिर्फ यह बताता था कि किस दिशा में जाना है। network library[1] में भी इसे इस्तेमाल किया है। standard library में भी
strtok()[2] जैसे coroutine functions हैंइसे manageable बनाने के लिए macro hell तक जाने की जरूरत नहीं है, लेकिन
switch/caseflow पढ़ना कभी मजेदार नहीं लगा[1]: https://github.com/REONTeam/libmobile/blob/master/relay.c#L3...
[2]: https://manpages.debian.org/bookworm/manpages-dev/strtok.3.e...
उसी लेखक का Simon Tatham's Portable Puzzle Collection भी है
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
अगर यह C की काली विद्या जैसा दिखता है, तो उसी लेखक का macros से मनमाने control structures बनाने वाला लेख भी पढ़ने लायक है: https://www.chiark.greenend.org.uk/~sgtatham/mp/
coroutines मजेदार हैं, लेकिन वास्तविक code में real threads के इस्तेमाल पर भी विचार करना चाहिए। आधुनिक processors में कई cores होते हैं, लेकिन coroutines अक्सर सिर्फ single core इस्तेमाल करते हैं
यह वास्तविक समस्या भी है। हाल तक coroutines का बहुत इस्तेमाल करने वाला qemu block device I/O का बड़ा हिस्सा single thread में भेजता था, और इससे performance समस्याएं थीं। Kevin Wolf और अन्य लोगों ने कई सालों में इसे ठीक किया, इसलिए modern qemu I/O के लिए कई threads इस्तेमाल करने लगा है, और यह काम RHEL 9.4 में शामिल होने वाला है
coroutines single-threaded execution को structure करने का तरीका हैं और अपने-आप में उपयोगी हैं। मुख्य लेख का producer-consumer pattern इसका अच्छा उदाहरण है; stream को parser से जोड़ना parallel algorithm नहीं है, इसलिए उसे लिखने में threads काम के नहीं हैं
parallel रूप से किए जा सकने वाले काम पर single-threaded paradigm इस्तेमाल करना स्वाभाविक रूप से inefficient है, लेकिन coroutines गरीब आदमी की parallelism नहीं, बल्कि अपने-आप में अर्थपूर्ण control structure हैं। web server में event loop जैसे dispatcher के साथ कई blocking events के बीच coroutines को पिरोता है, वैसे इन्हें threads के साथ productive तरीके से जोड़ा भी जा सकता है; और अगर runtime हर core पर thread चलाकर parallelize करे, तो threads के बीच coordination सिर्फ हर work queue की depth जांचने और कम भीड़ वाले side पर request भेजने जितना रह जाता है
coroutines का idea तब काम आता है जब आपके पास कोई local task और synchronous data हो, और उसे caller द्वारा inner loop को “खींचने” वाले functional paradigm की बजाय, उल्टे रूप में व्यक्त करना आसान हो—जहां function किसी चीज पर loop चलाकर result को कहीं और मौजूद abstracted consumer की ओर “धकेलता” है
फिर schedulers के बीच coroutines को शायद ही कभी move किया जाता है, और अलग schedulers की coroutines के बीच data share करना भी शायद ही होता है
coroutines cooperative scheduling के जरिए ऐसा सुविधाजनक concurrency programming style संभव बनाते हैं जिसमें locks की जरूरत बिल्कुल नहीं होती। आम तौर पर scheduling latency बढ़ जाती है, लेकिन atomic operations/lock overhead खत्म हो जाता है और preemptive scheduling के लिए timer लगातार execution को interrupt नहीं करता, इसलिए throughput काफी ज्यादा हो सकता है
इस approach का C++ version: https://www.codeproject.com/Tips/29524/Generators-in-C
मैं अपने Sciter में भी एहतियातन इसका इस्तेमाल कर रहा हूं, और यह काफी अच्छी तरह काम करता है और सुविधाजनक है
इसे modular और safe तरीके से हासिल करने का तरीका शायद effect handlers होगा। यह Python के
yieldजैसा है, लेकिन values return कर सकता है, और function calls तक सीमित नहीं होता बल्कि exceptions की तरह scope में बंधता है। अगर आप इससे परिचित नहीं हैं, तो यह लेख अच्छा motivation देता हैdirect style में लिखी हर function control को कहीं और जाना हो तो “effect” perform कर सकती है। यहां
c=getchar()औरemit(c)ऐसे ही मामले हैंतब control effect handler के पास जाता है, और इस मामले में शायद दोनों functions का caller तय करता है कि आगे क्या करना है। decompressor जब character emit करे, तो उस character को parser code को देकर resume किया जाए, फिर parser को और चाहिए कहने तक आगे बढ़ा जाए, और फिर decompressor को resume किया जाए—ऐसा कुछ
effects को efficiently implement किया जा सकता है, खासकर अगर continuation को सिर्फ एक बार call करने तक सीमित कर दिया जाए। OCaml में ऐसा ही है। यह direct style code और type/memory safety दोनों की अनुमति देता है, और concurrent environments में भी बहुत उपयोगी है
उदाहरण यहां है: https://effekt-lang.org/docs/casestudies/lexer
“यह ट्रिक ज़ाहिर तौर पर सभी coding standards का उल्लंघन करती है… मैं कहूंगा कि coding standards ही गलत हैं” वाले हिस्से से मैं बिल्कुल सहमत नहीं हूं
coding standards का इस code को reject करना गलत नहीं है; यह code बस एक प्यारी-सी trick भर है। बड़े पैमाने की software engineering का काम surprises हटाना और ऐसा code बनाना है जिसे सुबह 3 बजे call पर उठाकर debug करने वाले नींद से वंचित व्यक्ति भी पढ़ सके। यह उम्मीद नहीं की जा सकती कि programmer हमेशा चार बुनियादी नियम याद रखेगा
switch,return,caseजैसे अहम elements को “obfuscation” macros के अंदर छिपाकर syntax structure को धुंधला किया गया, लेकिन algorithm structure को सामने लाया गया—यह दावा भी मानना मुश्किल है। अच्छे program में syntax structure और algorithm structure दोनों साफ़ होने चाहिए, और यह तरीका उस कसौटी पर खरा नहीं उतरता। मेरे हिसाब से Rust जिस तरहasyncfunctions में implicit state machine बनाता है, वही यहां model होना चाहिएC दुनिया में ternary conditional operator भी बहुत उत्तेजक माना जाता है और C99 भी नई चीज़ की तरह treat होता है। C++ दुनिया में template metaprogramming से रोकने की इकलौती वजह यह होती है कि जिस standard का इस्तेमाल हो रहा है, उसमें वही काम
constexprसे किया जा सकता है