Fil का अविश्वसनीय Garbage Collector

• Fil-C भाषा का FUGC एक उन्नत garbage collector है जो parallel और concurrent processing को सपोर्ट करता है
• यह पूरे प्रोग्राम को रोके बिना on-the-fly और grey-stack Dijkstra method का उपयोग करता है
• यह सटीक memory tracking और object relocation के बिना processing वाला डिज़ाइन लागू करता है
• Safepoint के उपयोग से multi-threaded environment में भी सुरक्षित और कुशल memory management संभव होता है
• freed object access/double free होने पर exception handling सहित C/Java/JavaScript शैली की विभिन्न memory management सुविधाएँ देता है

---

Fil के FUGC (अविश्वसनीय Garbage Collector) का अवलोकन

Fil-C एक parallel concurrent on-the-fly grey-stack Dijkstra precise non-moving garbage collector FUGC (Fil's Unbelievable Garbage Collector) का उपयोग करता है
FUGC का source code fugc.c में देखा जा सकता है, लेकिन runtime और compiler की विभिन्न support logic के बिना यह काम नहीं करता

FUGC की मुख्य विशेषताएँ

• Parallel processing: marking और sweep काम कई threads पर एक साथ चलते हैं, और CPU core जितने अधिक हों, collection उतना तेज़ होता है
• Concurrency support: garbage collector thread, mutator (यानी user program thread) से अलग काम करता है, इसलिए application threads बिना रुके चल सकती हैं
• on-the-fly: global stop-the-world के बिना "soft handshake (=ragged safepoint)" के जरिए हर thread stack scanning जैसे खास काम asynchronous तरीके से संभालता है
• Grey-stack method: thread stacks को fixed point तक कई बार दोबारा जाँचा जाता है और marking दोहराई जाती है; इस दौरान नए objects मिलें तो फिर marking की जाती है
• सरल store barrier का उपयोग होता है, और load barrier की ज़रूरत नहीं होती
• Dijkstra barrier: marking के दौरान heap या global variable में pointer store करने पर target object को भी साथ में mark किया जाता है
• Precise collection: runtime सभी pointer locations को सटीक रूप से track करता है, इसलिए GC सिर्फ वास्तविक objects को ही traverse करता है
• Non-moving object handling: objects की memory location नहीं बदलती, इसलिए multi-threaded concurrent collection और synchronization आसान होता है
• Advancing wavefront design: mutator collector के workload को बढ़ा नहीं सकता, और marked objects उस collection cycle के दौरान बने रहते हैं
• Incremental collection: कुछ objects collection शुरू होते समय live हों, फिर भी cycle के दौरान free किए जा सकते हैं

Safepoint और thread management

• Pollcheck: compiler समय-समय पर pollcheck insert करता है; fast path में यह सिर्फ एक branch होता है, जबकि slow path में GC-related callback चलता है
• Soft handshake: सभी threads से pollcheck callback चलाने का अनुरोध किया जाता है और उसके पूरा होने तक इंतज़ार किया जाता है
• enter/exit state management: लंबे blocking function/system call आदि में pollcheck छूट जाए तो collector खुद संबंधित callback चला देता है
• multi-threading सपोर्ट वाले environment में race condition की रोकथाम और सुरक्षित pointer access सुनिश्चित होता है
• stop-the-world mode का उपयोग debugging या fork जैसी विशेष operations के लिए किया जाता है, और signal handling भी स्थिर रूप से लागू की जाती है

FUGC collector loop

1. GC trigger का इंतज़ार
2. store barrier को enable करने के बाद soft handshake (no-op callback)
3. black allocation (नए objects को pre-mark करना) enable करना, cache reset callback चलाना
4. global roots को mark करना
5. soft handshake (stack scan और cache reset callback); अगर mark stack खाली हो तो 7 पर जाएँ
6. tracing (mark stack के हर object के लिए references mark करना, mark stack खाली होने तक दोहराना, फिर 5 पर लौटना)
7. store barrier disable करना, sweep की तैयारी, cache re-reset soft handshake
8. sweep (जिन pages का अभी sweep नहीं हुआ उन्हें black, और जिनका हो चुका है उन्हें white के रूप में allocate करना)
9. loop में फिर प्रवेश

मौजूदा शोध से अंतर और optimization

• FUGC, DLG (Doligez-Leroy-Gonthier) collector से मिलता-जुलता है, लेकिन सरल Dijkstra barrier और grey stack के उपयोग से store barrier implementation अधिक सहज और performance में बेहतर है
• fixed-point method से यह जल्दी converge करता है और लागत कम रहती है
• bitvector SIMD-based sweep के जरिए free processing बहुत तेज़ होती है, और कुल GC समय का 5% से भी कम लेती है
• Verse heap config आदि का उपयोग कर performance optimization किया गया है

बोनस सुविधाएँ (memory management extensibility)

Object free

• C में free कॉल होने पर object को तुरंत free के रूप में flag किया जाता है, और बाद में access होने पर trap होता है
• dangling pointer के कारण GC के गलत व्यवहार को रोका जाता है
• freed object की references को singleton free object पर redirect किया जाता है, जिससे memory reallocation के बाद भी निश्चित पहचान संभव रहती है
• उपयोग में न आने वाले pointers के कारण GC-triggered memory leak को रोका जाता है

Finalizer

• Java-style finalizer queue को custom queue और thread handling के जरिए लचीले ढंग से implement किया जा सकता है

Weak reference

• Java के weak reference की तरह ही काम करता है; अलग reference queue नहीं है (phantom, soft reference समर्थित नहीं हैं)

Weak map

• JavaScript WeakMap जैसा, लेकिन सभी elements पर iteration और elements की संख्या जाँचना संभव है

निष्कर्ष और महत्व

FUGC के जरिए Fil-C, free के दुरुपयोग के खिलाफ मज़बूत सुरक्षा और सहज exception handling प्रदान करता है

• freed object access या double free होने पर ज़रूर trap हो ऐसा डिज़ाइन किया गया है
• अगर object को free न किया जाए तो GC खुद उसे ठीक से reclaim कर लेता है
• यह विभिन्न memory management patterns को सपोर्ट करता है और मौजूदा C/Java/JavaScript developers के लिए भी परिचित environment देता है

[GN⁺]

Hacker News राय

• हम्म, लगता है Fil-C वाकई काफ़ी अहम साबित हो सकता है। बहुत-सा software ऐसा है जो सिर्फ़ C code में मौजूद है, इसलिए उसे बनाए रखने का कोई तरीका होना चाहिए। मौजूदा C compiler single-core performance को अधिकतम करने के लिए बड़े security risk उठाते हैं, और अब ऐसा trade-off काफ़ी पुराना लगने लगा है। CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash आदि की support list सच में प्रभावशाली है। मुझे नहीं लगता कि उन software में से किसी को भी Rust में फिर से लिखे जाने की संभावना ज़्यादा है। यह जानने की जिज्ञासा है कि क्या Fil-C को MMU-रहित environment में आपस में अविश्वसनीय processes के बीच multitasking के लिए भी इस्तेमाल किया जा सकता है। capability-based security, non-blocking synchronization वगैरह में इसकी दिशा सही लगती है। जानना चाहूँगा कि क्या किसी ने इसे सच में इस्तेमाल किया है। रिपोर्ट के मुताबिक़ worst case में भी speed लगभग 4 गुना घटती है, और इसका नाम तो वाकई मज़ेदार है। Fil this way! Fil this way!

  • Fil-C से MMU-रहित कंप्यूटर पर अविश्वसनीय processes के बीच multitasking संभव है या नहीं, इस सवाल पर मेरा मानना है कि मूल रूप से FUGC OS की MMU-निर्भर सुविधाओं पर आधारित है, लेकिन शायद इसका ऐसा version भी बनाया जा सकता है जिसमें यह निर्भरता हटा दी जाए। performance के बारे में, 4 गुना धीमापन सबसे बुरा हाल है, और वही आँकड़ा मैंने खुद बताया था। मैं हमेशा performance को यथार्थवादी तरीके से मापने और जिद के साथ performance issues को सुधारने की कोशिश करता हूँ। असल में Fil-C version वाले software के साथ भी मैं अपने रोज़मर्रा के पसंदीदा programs बिना किसी खास दिक्कत के इस्तेमाल कर पाता हूँ

  • आपने support software list को प्रभावशाली कहा, इस सामान्य बात से मैं सहमत हूँ, लेकिन दिए गए उदाहरणों को मैं थोड़ा अलग तरह से देखता हूँ। CPython, Perl5 आदि तो वैसे भी ऐसे language runtimes हैं जिनकी GC के कारण धीमे होने की बदनामी पहले से है, इसलिए उन पर एक और GC चढ़ाना बहुत elegant design नहीं लगता, बल्कि इससे speed loss और बढ़ सकता है। और Rust या Go जैसी भाषाओं में उन्हें दोबारा implement करने या replace करने की कोशिशें कुछ हद तक पहले से चल भी रही हैं, जैसे SQLite के लिए Turso है। साथ ही, ये software इतने सक्रिय रूप से maintain होने वाले बुनियादी projects हैं कि संभव है किसी दिन ये खुद refactoring या Rust porting कर लें। उल्टा, मुझे लगता है Fil-C वहाँ ज़्यादा उपयुक्त है जहाँ maintenance कम है, performance sensitivity कम है, फिर भी लोग उसे इस्तेमाल करते रहते हैं—जैसे 50 साल पुराने C programs, जिन्हें कोई कभी-कभी निकालकर चला लेता है

  • SQLite के C में लिखे होने की बड़ी ताकत इसकी non-standard OS पर portability है। उदाहरण के लिए, मैंने इसे embedded RTOS μC/OS-II पर सीधे इस्तेमाल किया है। embedded environment का design PC/server से काफ़ी अलग होता है; performance और memory fragmentation से बचने के लिए वहाँ कई बार memory free ही नहीं की जाती, बल्कि objects/structs को reuse करने लायक़ चिह्नित किया जाता है। यह custom heap allocation या pooling जैसा concept है। SQLite का VFS दस्तावेज़, Micro-Controller OS परिचय

  • आपने कहा कि उदाहरण के तौर पर दिए गए C software को Rust में फिर से लिखने की नौबत नहीं आएगी, लेकिन मुझे जिज्ञासा है कि AI-आधारित static analysis tools इस स्तर तक पहुँचने में कितना समय लेंगे जहाँ वे C code की समस्याएँ ठीक-ठीक पकड़ सकें और इस तरह feedback दे सकें: “इस हिस्से में error होगा, इसे ऐसे ठीक करें।” अगर ऐसे tools सच में आ गए, तो शायद C का इस्तेमाल जारी रखना भी ठीक हो जाएगा

  • ध्यान रहे कि Fil-C अभी 32-bit (या उससे कम) systems को support नहीं करता। Fil-C में Invisicaps से संबंधित दस्तावेज़

• ऐसा लगता है कि यह उन दुर्लभ projects में से है जो research और practicality दोनों को साथ लेकर चलते हैं। आम तौर पर इस तरह की चीज़ें बड़ी IT companies की टीमों के जरिए, ad revenue जैसे मॉडल पर चलती हैं, इसलिए जिज्ञासा है कि Fil-C किस पृष्ठभूमि से शुरू हुआ। अगर यह सिर्फ़ कोई व्यक्तिगत passion project नहीं है, तो funding किसने दी, इसमें कितने वर्षों का manpower लगा, और इसका अंतिम लक्ष्य क्या है?

  • मेरी नज़र में यह एक passion project लगता है

  • अंतिम लक्ष्य के बारे में पूछे गए सवाल पर, project copyright में 2024-2025 Epic Games, Inc. लिखा हुआ है

• Fil-C का अस्तित्व ही अच्छा लग रहा है। ऐसी तकनीकें असल programs में कारगर होने के बावजूद developers अक्सर मानते हैं कि “ऐसी चीज़ चल ही नहीं सकती,” और सिर्फ़ इसका implement हो जाना ही कई बहसों को एक झटके में ख़त्म कर देता है

  • benchmark results जानने की इच्छा है। इस approach को लेकर सबसे बड़ी चिंता यही है कि जिन खास use cases में C/C++ अब भी लोकप्रिय हैं, वहाँ performance बहुत बुरी तरह गिर न जाए। अगर throughput, latency, और memory usage Go जैसी भाषाओं के बहुत क़रीब पहुँच जाएँ, तो फिर इसे चुनने की वजह काफ़ी कम रह जाएगी

  • programming languages में performance बनाम बाकी बातों की बहस assembly के ज़माने से चली आ रही है। लेकिन ज़्यादातर developers Ivan Suntherland, Alan Kay, Steve Jobs, Bret Victor जैसे असाधारण vision वाले लोग नहीं होते; वे आम लोग होते हैं जो अपने सामने कुछ चलता हुआ देखकर ही भरोसा करते हैं। शायद इसी वजह से आज भी UNIX और C की नकलें भरी पड़ी हैं, और लोग कुछ नया रचने के बजाय अतीत के vision को दोहराते हुए जीते रहते हैं। बेशक, 1970 के दशक में UNIX और C बनाने वाले वे दो लोग भी असाधारण visionaries थे

• यह जानना दिलचस्प होगा कि advancing wavefront method की जगह retreating wavefront strategy क्यों नहीं अपनाई गई

• अगर मौजूदा C programs में free(...) calls पहले से ठीक तरह से डाले गए हैं, और हर pointer के लिए अलग से bounds information भी रखी जा रही है, तो फिर full GC क्यों चुना गया? इसके बजाय lock-and-key style की temporal checking technique (संदर्भ: paper link) memory usage predictability, performance, और scheduling के लिहाज़ से बेहतर हो सकती है। मेरा अनुमान है कि शायद key store करने की लागत बहुत बड़ी हो, या checking में ज़्यादा समय लगे, या multithreading environment में race condition की समस्या आए

  • lock and key approach में Fil-C जैसा कोई खास चतुर पहलू नहीं है। Fil-C का capability model पूरी तरह thread-safe है, और इसकी बड़ी ताकत यह है कि ज़्यादातर मामलों में किसी special atomics या locking की ज़रूरत नहीं पड़ती

  • यह भी रोचक है कि pointer dereference के बिना out-of-bounds pointer arithmetic की अनुमति दी जाती है। compilers कभी-कभी ऐसी UB का इस्तेमाल optimization के लिए करते हैं (Stack Overflow से संबंधित सवाल), इसलिए जिज्ञासा है कि Fil-C के अंदर LLVM में ऐसे optimizations बंद किए जाते हैं, या pointers को “base + offset” रूप में track किया जाता है जिससे ऐसी संभावना ही खत्म हो जाए। और अगर ऐसा है, तो क्या इससे सामान्य pointers पर लागू होने वाले कुछ optimizations छूट नहीं जाते?

• project सच में बहुत शानदार लग रहा है। यह बात खास ध्यान खींचती है कि pollcheck का fast path बस load-and-branch है। branch के बदले इस्तेमाल की जाने वाली एक दिलचस्प technique है, जिसे Android official blog के "implicit suspend checks" लेख में अच्छी तरह समझाया गया है

  • poll check में ऐसी optimization आम तौर पर काफ़ी इस्तेमाल होती है। वास्तव में ज़्यादातर production JVMs में यह पहले से लागू है। लेकिन मैं अभी उस स्तर की low-level optimization की चिंता करने की स्थिति में नहीं हूँ। अभी तो मेरे पास बचे हुए high-level बुनियादी optimizations पर काम करना ज़्यादा ज़रूरी है

• GC के साथ concurrency support वाला C, और वह भी non-moving GC—यह सच में चौंकाने वाला है। अगर किसी मध्यम आकार के C project में 2~3 गुना runtime performance loss के बदले memory bugs कम किए जा सकें, तो मैं वह सौदा स्वीकार करने को तैयार हूँ। जिज्ञासा है कि incremental adoption कितना आसान है। क्या यह हर target पर संभव है, या पूरा toolchain बदलना पड़ता है?

• मेरे लिए C, performance, और security तीनों अहम हैं। यह GC और capability संरचना आकर्षक लगती है। “ज़्यादा सुरक्षित C” कैसा दिख सकता है, इस बारे में मैंने कई बार सोचा है; capability concept को भी कुछ बार देखा है, लेकिन compiler code में मेरी पकड़ कमज़ोर है। जिज्ञासा है कि Windows support कितना कठिन है

  • एक छोटी-सी बात, लेकिन पहले वाक्य में Oxford comma न होने की वजह से उसका मतलब समझने में मुझे काफ़ी समय लगा। ऐसा इतना साफ़ उदाहरण कम ही मिलता है

• जिज्ञासा है कि GC root objects को कैसे track करता है। क्या compile phase में GC scan के लिए roots को mark किया जाता है, या कोई जानकार इसे समझा सकता है?

  • LLVM stack map भरने के लिए instructions insert करके यह काम कर देता है

• यह project सच में हैरान कर देने वाला है। अब तक इसके बारे में न सुना होना अजीब लगता है। इसे खुद आज़माने का उत्साह है। performance limits की वजह से शायद production service में यह मुश्किल हो, लेकिन कुछ programs की safety को सीधे verify करने के तरीके के रूप में यह बेहद उपयोगी दिखता है। मुझे यह रोज़मर्रा में इस्तेमाल होने वाले sanitizers से भी ज़्यादा व्यापक लगता है