Fil'in İnanılmaz Çöp Toplayıcısı

• Fil-C dilinin FUGC'si, paralel ve eşzamanlı çalışmayı destekleyen gelişmiş bir çöp toplayıcıdır
• Programın tamamını durdurmadan on-the-fly (anında) ve grey-stack Dijkstra yaklaşımını kullanır
• Kesin bellek izleme ve nesneleri taşımadan çalışan bir tasarım uygular
• Safepoint kullanımı sayesinde çok iş parçacıklı ortamlarda güvenli ve verimli bellek yönetimi sağlar
• Serbest bırakılmış nesneye erişim / çift serbest bırakma durumlarında istisna üretme gibi C/Java/JavaScript tarzı çeşitli bellek yönetimi özellikleri sunar

---

Fil'in FUGC'sine (İnanılmaz Çöp Toplayıcısı) genel bakış

Fil-C, paralel eşzamanlı on-the-fly grey-stack Dijkstra kesin ve taşımayan bir çöp toplayıcı olan FUGC'yi (Fil's Unbelievable Garbage Collector) kullanır.
FUGC kaynak kodu fugc.c içinde görülebilir, ancak çalışma zamanı ve derleyicinin çeşitli destek mantıkları olmadan çalışmaz.

FUGC'nin başlıca özellikleri

• Paralel işleme: İşaretleme ve süpürme işlemleri birden fazla iş parçacığında aynı anda yürütülür; CPU çekirdeği arttıkça toplama hızı da artar
• Eşzamanlılık desteği: Çöp toplayıcı iş parçacıkları mutator'lardan (yani kullanıcı programı iş parçacıklarından) ayrı çalışır; uygulama iş parçacıkları durmadan çalışabilir
• on-the-fly (anında): Küresel stop-the-world olmadan, "soft handshake" (=ragged safepoint) ile her iş parçacığı yığın tarama gibi belirli işleri asenkron olarak yürütür
• grey-stack yaklaşımı: İş parçacığı yığınları sabit noktaya ulaşana kadar tekrar tekrar incelenir ve işaretleme yinelenir; bu sırada ek nesneler çıkarsa işaretleme yeniden sürdürülür
• Basit bir store barrier kullanır; load barrier gerekmez
• Dijkstra barrier: İşaretleme sırasında heap'e veya global değişkenlere bir işaretçi yazılırsa hedef nesne de aynı anda işaretlenir
• Kesin toplama: Çalışma zamanı tüm işaretçi konumlarını tam olarak izlediği için GC yalnızca gerçek nesneleri gezer
• Nesneleri taşımayan yapı: Nesnelerin bellek adresleri değişmez; bu da çok iş parçacıklı eşzamanlı toplama ve senkronizasyonu kolaylaştırır
• Advancing wavefront tasarımı: Mutator, toplayıcının iş yükünü artıramaz; işaretlenmiş nesneler o toplama çevrimi boyunca işaretli kalır
• Artımlı toplama: Bazı nesneler, toplama başladığında hayatta olsalar bile çevrim sırasında serbest bırakılabilir

Safepoint (güvenli nokta) ve iş parçacığı yönetimi

• Pollcheck: Derleyici düzenli aralıklarla pollcheck ekler; hızlı yolda bu yalnızca basit bir dallanmadır, yavaş yolda ise GC ile ilgili callback'ler çalıştırılır
• Soft handshake: Tüm iş parçacıklarından pollcheck callback'lerini çalıştırmaları istenir ve tamamlanmaları beklenir
• enter/exit durum yönetimi: Uzun süre bloklayan fonksiyonlarda / sistem çağrılarında pollcheck atlanıyorsa collector ilgili callback'i doğrudan çalıştırır
• Çok iş parçacıklı ortamlarda yarış koşullarını önler ve güvenli işaretçi erişimini garanti eder
• stop-the-world modu ile hata ayıklama, fork gibi özel işler desteklenir; signal işleme de kararlı biçimde uygulanır

FUGC toplayıcı döngüsü

1. GC tetiklenmesini bekle
2. store barrier'ı etkinleştir, ardından soft handshake (no-op callback) yap
3. Siyah tahsisi (yeni nesneleri önceden işaretleme) etkinleştir, cache sıfırlama callback'lerini çalıştır
4. Global kökleri işaretle
5. Soft handshake yap (yığın tarama ve cache sıfırlama callback'leri); mark stack boşsa 7'ye git
6. İzleme yap (mark stack'teki her nesne için başvuruları işaretle; mark stack boşalana kadar tekrarla, sonra 5'e dön)
7. store barrier'ı kapat, süpürmeye hazırlan, cache'i yeniden sıfırlamak için soft handshake yap
8. Süpürme yap (henüz süpürülmemiş sayfalarda black, zaten süpürülmüş olanlarda white tahsis et)
9. Döngüye yeniden gir

Mevcut araştırmalardan farkı ve optimizasyonlar

• FUGC, DLG (Doligez-Leroy-Gonthier) collector'a benzer; ancak basit Dijkstra barrier ve grey stack kullanımı sayesinde store barrier uygulaması daha sezgiseldir ve performansı yüksektir
• Sabit nokta yaklaşımıyla hızla yakınsar ve maliyeti düşüktür
• Bitvector SIMD tabanlı süpürme ile çok hızlı serbest bırakma yapılır; toplam GC süresinin %5'inden azını tüketir
• Verse heap config kullanımı gibi yöntemlerle performans optimize edilir

Bonus özellikler (bellek yönetimi genişletilebilirliği)

Nesne serbest bırakma

• C'deki free çağrısında nesne hemen serbest bırakılmış olarak işaretlenir; sonrasında erişim olursa trap oluşur
• Dangling pointer nedeniyle GC'nin hatalı çalışması önlenir
• Serbest bırakılmış nesnenin başvuruları singleton free nesnesine yönlendirilir; böylece bellek yeniden tahsis edildikten sonra bile kesin tespit mümkün olur
• Kullanılmayan işaretçilerin GC kaynaklı bellek sızıntısı üretmesi önlenir

Finalizer

• Java tarzı finalizer kuyruğu, kullanıcı tanımlı kuyruk ve iş parçacığı işleme ile esnek biçimde uygulanabilir

Zayıf başvurular

• Java'daki weak reference ile aynı şekilde çalışır; ayrı bir reference queue yoktur (phantom, soft reference desteklenmez)

Zayıf map

• JavaScript WeakMap'e benzer; ancak tüm öğeleri yinelemek ve öğe sayısını görmek mümkündür

Sonuç ve anlamı

FUGC sayesinde Fil-C, free yanlış kullanımına karşı güçlü güvenlik ve sezgisel istisna işleme sunar.

• Serbest bırakılmış nesneye erişimde veya çift serbest bırakmada mutlaka trap oluşacak şekilde tasarlanmıştır
• Nesne serbest bırakılmazsa onu düzgün biçimde geri kazanma sorumluluğunu GC üstlenir
• Çeşitli bellek yönetimi kalıplarını destekler; C/Java/JavaScript geliştiricileri için de tanıdık bir ortam sunar

[GN⁺]

Hacker News görüşleri

• Hm, Fil-C gerçekten önemli bir anlam taşıyabilir gibi görünüyor. Yalnızca C kodundan oluşan çok fazla yazılım var ve bunları sürdürebilmek için bir yaklaşıma ihtiyaç olduğunu düşünüyorum. Mevcut C derleyicileri, tek çekirdek performansını en üst düzeye çıkarmak için büyük güvenlik risklerini göze alıyor; bu tür ödünleşimler artık çağın gerisinde kalmış gibi hissettiriyor. CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash gibi destek listesi gerçekten etkileyici. Bu yazılımlardan hiçbirinin Rust ile yeniden yazılmasının pek olası olduğunu sanmıyorum. Fil-C'nin, MMU olmayan ortamlarda birbirine güvenmeyen süreçler arasında çoklu görev için de kullanılıp kullanılamayacağını merak ediyorum. Yetenek tabanlı güvenlik, non-blocking senkronizasyon gibi alanlarda doğru yöne gidiyor gibi görünüyor. Bunu gerçekten kullanmış biri var mı öğrenmek isterim. Gerçekte, en kötü durumda bile hızın yaklaşık 4 kat düştüğü bildiriliyor ama adı gerçekten çok eğlenceli. Filthisway! Filthisway!

  • Fil-C ile MMU olmayan bir bilgisayarda güvenilmeyen süreçler arasında çoklu görev mümkün mü sorusuna yanıt olarak, temelde FUGC'nin OS'nin MMU'ya bağımlı özelliklerine dayandığını ama bu bağımlılıkları kaldıran bir sürümün de yapılabileceğini düşünüyorum. Performans konusunda ise 4 kat yavaşlama en kötü durum ve bu rakamı bizzat ben rapor ettim. Her zaman performansı gerçekçi şekilde ölçme ve performans sorunlarını inatla iyileştirme eğilimim var. Nitekim Fil-C sürümü yazılımlarla da günlük kullandığım programları sorunsuz biçimde kullanabiliyorum

  • Desteklenen yazılım listesinin etkileyici olduğu yorumuna genel olarak katılıyorum ama verilen örnekleri biraz farklı görüyorum. CPython, Perl5 gibi şeyler zaten GC yüzünden yavaş olmakla ünlü dillerin çalışma zamanları; bunların üstüne bir GC daha koymak pek zarif bir tasarım gibi görünmüyor ve performans düşüşü de büyük olabilir. Ayrıca Rust ya da Go gibi dillerle yeniden uygulama veya ikame girişimleri bazı alanlarda zaten var; örneğin SQLite için Turso var. Bir de bu yazılımlar çok aktif biçimde bakımı yapılan, köklü projeler olduğu için günün birinde kendi içlerinde refaktör veya Rust'a taşıma da yapabilirler diye düşünüyorum. Bence Fil-C'nin daha uygun olduğu yerler, daha az bakımı yapılan, performansa daha az duyarlı ama kullanılmaya devam eden, birilerinin zaman zaman çıkarıp kullandığı 50 yıllık C programları gibi kodlar

  • SQLite'ın C ile yazılmış olmasının avantajı, standart dışı işletim sistemlerine kolay taşınabilmesi. Örneğin gömülü RTOS olan μC/OS-II üzerinde doğrudan kullanma deneyimim oldu. Gömülü sistem tasarımı, PC/sunucu dünyasından oldukça farklı; performans ve bellek parçalanmasını önlemek için bellek serbest bırakmayı hiç yapmayıp nesne/yapıların yeniden kullanılacağını işaretliyorsunuz. Bu, özel heap allocation ya da pooling gibi bir kavram. SQLite'ın VFS belgeleri, Micro-Controller OS tanıtımı

  • Örnek verilen listedeki C yazılımlarının Rust ile yeniden yazılmayacağını söylemişsiniz ama yapay zeka tabanlı statik analiz araçlarının gelişip C kodundaki sorunları doğru biçimde bulacak ve “bu bölüm hata veriyor, bunu şöyle düzelt” diye geri bildirim verecek seviyeye gelmesine daha ne kadar kaldığını merak ediyorum. Böyle araçlar gerçekten çıkarsa C kullanmaya devam etmek de gayet makul olabilir

  • Fil-C'nin henüz 32 bit (veya daha düşük) sistemleri desteklemediğini not düşmek isterim. Fil-C'de Invisicaps ile ilgili belge

• Bu tür projeler, araştırma ile pratik kullanımı aynı anda takip eden nadir örnekler gibi geliyor. Bu tür işler genelde büyük IT şirketlerinde ekiplerle ve reklam geliriyle yürütülür; Fil-C'nin nasıl bir arka plandan çıktığını merak ediyorum. Basit bir kişisel tutku projesi değilse, finansmanı kim sağladı, kaç yıllık insan gücü harcandı ve nihai hedef ne, bunları merak ediyorum

  • Bana göre bu bir tutku projesi gibi görünüyor

  • Nihai hedefin ne olduğu sorusuna karşılık, proje telif hakkının 2024-2025 Epic Games, Inc. olarak belirtildiği söyleniyor

• Fil-C'nin varlığı başlı başına sevindirici. Böyle tekniklerin gerçek programlarda etkili olmasına rağmen geliştiricilerin sık sık “öyle bir şey olmaz” diye inandığı durumlar var; bunun gerçekten uygulanabilir olduğunu göstermesi bile sayısız tartışmayı tek başına bitirmeye yetiyor

  • Benchmark sonuçlarını merak ediyorum. Bu yaklaşımın en büyük endişesi, C/C++'ın hâlâ popüler olduğu belirli kullanım alanlarında performansın korkunç derecede düşmesi olabilir. Throughput, latency veya bellek kullanımı Go gibi dillere fazlasıyla yaklaşırsa, sonunda bunu seçmek için pek bir neden kalmayabilir

  • Programlama dillerinde assembly günlerinden beri performans eksenli söylem hep vardı. Ama geliştiricilerin çoğu Ivan Suntherland, Alan Kay, Steve Jobs, Bret Victor gibi olağanüstü vizyoner insanlar değil; gözünün önünde çalışan şeyi görüp ona güvenen sıradan insanlar. Bu yüzden bugün bile UNIX ve C'nin kopyaları etrafta dolu ve birçok kişi yeni bir şey yaratmaktan ziyade geçmişin vizyonunu tekrar ederek yaşamayı sürdürüyor gibi. Tabii 1970'lerde UNIX ve C'yi yaratan o iki kişi de büyük vizyonerlerdi

• advancing wavefront yöntemi yerine neden retreating wavefront stratejisi kullanılmadığını merak ediyorum

• Mevcut C programlarındaki free(...) çağrıları zaten uygun biçimde yerleştirilmişse ve tüm pointer'lar için ayrıca sınır bilgisi de tutuluyorsa, neden tam bir GC tercih edildiğini merak ediyorum. Bunun yerine temporal checking için lock-and-key tekniğinin (bkz: makale bağlantısı) bellek kullanımının öngörülebilirliği, performans ve scheduling açısından daha iyi olabileceğini düşünüyorum. Muhtemelen key saklama alanı fazla büyüyor ya da kontrol süresi uzuyor veya çok iş parçacıklı ortamda race condition sorunları çıkıyor olabilir

  • lock and key yaklaşımında Fil-C'ye özgü akıllı özellikler yok. Fil-C'nin capability modeli tamamen thread-safe ve çoğu durumda özel atomics ya da locking gerektirmemesi önemli bir avantaj

  • Ayrıca pointer dereference olmadan sınır dışı pointer aritmetiğine izin vermesi de ilginç. Derleyiciler bazen böyle UB durumlarını optimizasyon için kullanıyor (Stack Overflow ilgili soru); Fil-C'nin içindeki LLVM'de bu optimizasyonlar kapatılıyor mu, yoksa pointer'lar “base + offset” çifti olarak tutulup bunun önü tamamen mi kesiliyor, merak ediyorum. Eğer öyleyse normal pointer'lara uygulanabilen bazı optimizasyonlar da kaçırılmış olmuyor mu diye de düşünüyorum

• Gerçekten harika bir proje gibi görünüyor. pollcheck'in fast path'inin sadece load-and-branch olmasına dikkat çektim. Bu tür branch'lerin yerine kullanılan ilginç bir teknik var; Android resmî blogundaki "örtük suspend kontrolü" yazısında iyi açıklanıyor

  • poll check için böyle optimizasyonlar sık kullanılır. Hatta çoğu production JVM bunu zaten uyguluyor. Ama ben hâlâ bu kadar düşük seviyeli optimizasyonları dert edecek aşamada değilim. Şu anda önce geriye kalan yüksek seviyeli, temel optimizasyonları yapmam gerekiyor

• GC eklenmiş eşzamanlı C, üstelik non-moving GC olması gerçekten şaşırtıcı. Orta ölçekli bir C projesinde çalışma zamanı performansında 2-3 kat kayıp karşılığında bellek hatalarını azaltabiliyorsam, bunu kabul etmeye oldukça razıyım. Kademeli geçişin ne kadar kolay olduğunu merak ediyorum. Hedef başına mı mümkün, yoksa tüm toolchain'in değişmesi mi gerekiyor?

• Benim için C, performans ve güvenlik üçü de önemli. Bu GC ve capability yapısı çekici geliyor. “Daha güvenli C”nin nasıl görüneceğini birçok kez düşündüm; capability kavramını da birkaç kez değerlendirdim ama derleyici kodu konusunda çok iyi değilim. Windows desteğinin zor olup olmadığını merak ediyorum

  • Konu dışı olacak ama ilk cümlede Oxford virgülü olmayınca ne demek istediğini anlamam epey zaman aldı. Böyle net bir örneğe sık rastlanmıyor

• GC'nin root object'leri nasıl izlediğini merak ediyorum. GC'nin tarayacağı root'ları önceden işaretleyen bir derleme aşaması mı var, bilen biri açıklayabilir mi?

  • LLVM, stack map'i doldurmak için komutlar ekleyerek bunu çözüyor

• Bu proje gerçekten şaşırtıcı. Şimdiye kadar hiç duymamış olmam garip gelecek kadar ilginç. Bir kez doğrudan denemeyi dört gözle bekliyorum. Performans sınırları yüzünden gerçek servislerde zor olabilir ama bazı programların güvenliğini doğrudan doğrulamanın bir yolu olarak gerçekten çok faydalı görünüyor. Günlük kullandığım sanitizer'lara göre daha kapsamlı bir yaklaşım gibi duruyor