FUGC milik Fil yang Sulit Dipercaya

• FUGC pada bahasa Fil-C adalah garbage collector canggih yang mendukung pemrosesan paralel dan konkurensi
• Menggunakan on-the-fly (eksekusi langsung) dan metode grey-stack Dijkstra tanpa menghentikan seluruh program
• Menerapkan desain dengan pelacakan memori akurat dan pemrosesan tanpa memindahkan objek
• Dengan memanfaatkan safepoint, manajemen memori yang aman dan efisien dimungkinkan bahkan di lingkungan multithread
• Menyediakan beragam fitur manajemen memori bergaya C/Java/JavaScript, termasuk penanganan pengecualian saat akses ke objek yang sudah dibebaskan/pembebasan ganda

---

Gambaran umum FUGC (garbage collector yang sulit dipercaya) milik Fil

Fil-C menggunakan FUGC (Fil's Unbelievable Garbage Collector), sebuah garbage collector paralel, konkuren, on-the-fly, grey-stack Dijkstra, akurat, non-moving
Kode sumber FUGC dapat dilihat di fugc.c, tetapi tidak dapat berjalan tanpa berbagai logika pendukung dari runtime dan compiler

Fitur utama FUGC

• Pemrosesan paralel: pekerjaan marking dan sweeping dijalankan serentak di beberapa thread; semakin banyak core CPU, semakin cepat pengumpulan
• Dukungan konkurensi: thread garbage collector bekerja terpisah dari mutator (yakni thread program pengguna), sehingga thread aplikasi dapat tetap berjalan tanpa henti
• on-the-fly (eksekusi langsung): tanpa stop-the-world global, setiap thread menangani tugas tertentu seperti stack scan secara asinkron melalui "soft handshake (=ragged safepoint)"
• Metode grey-stack: stack thread diperiksa ulang berkali-kali hingga mencapai titik tetap untuk mengulang marking; jika muncul objek tambahan selama proses ini, pekerjaan marking dilanjutkan lagi
• Memanfaatkan store barrier yang sederhana, dan tidak memerlukan load barrier
• Dijkstra barrier: saat pointer disimpan ke heap atau variabel global selama marking, objek target juga ditandai secara bersamaan
• Pengumpulan akurat: runtime melacak semua lokasi pointer secara tepat, sehingga GC hanya menelusuri objek yang benar-benar nyata
• Pemrosesan objek non-moving: lokasi memori objek tidak berubah, sehingga pengumpulan konkuren multithread dan sinkronisasi menjadi lebih mudah
• Desain advancing wavefront: mutator tidak dapat menambah beban kerja collector; objek yang sudah ditandai akan tetap dipertahankan selama siklus pengumpulan itu
• Pengumpulan inkremental: sebagian objek dapat dibebaskan di tengah siklus meski merupakan objek hidup saat pengumpulan dimulai

Safepoint (titik aman) dan manajemen thread

• Pollcheck: compiler secara berkala menyisipkan pollcheck; pada jalur cepat hanya berupa branch sederhana, sedangkan pada jalur lambat callback terkait GC dijalankan
• Soft handshake: meminta semua thread menjalankan callback pollcheck lalu menunggu hingga selesai
• Manajemen status enter/exit: saat fungsi blocking jangka panjang/panggilan sistem dan sebagainya melewati pollcheck, collector akan menjalankan callback terkait secara langsung
• Menjamin pencegahan race condition dan akses pointer yang aman di lingkungan yang mendukung multithread
• Mendukung pekerjaan khusus seperti debugging atau fork dengan mode stop-the-world, dan penanganan signal juga diimplementasikan secara stabil

Loop collector FUGC

1. Menunggu pemicu GC
2. Mengaktifkan store barrier lalu melakukan soft handshake (callback no-op)
3. Mengaktifkan black allocation (penandaan awal untuk objek baru), menjalankan callback reset cache
4. Menandai global root
5. Soft handshake (callback stack scan dan reset cache); jika mark stack kosong, lanjut ke 7
6. Tracing (menandai referensi untuk setiap objek di mark stack, mengulang hingga mark stack kosong lalu kembali ke 5)
7. Menonaktifkan store barrier, menyiapkan sweep, soft handshake reset cache ulang
8. Sweep (halaman yang belum disweep dialokasikan sebagai black, yang sudah disweep sebagai white)
9. Masuk kembali ke loop

Perbedaan dari riset sebelumnya dan optimisasi

• FUGC mirip dengan collector DLG (Doligez-Leroy-Gonthier), tetapi implementasi store barrier lebih intuitif dan berkinerja lebih baik berkat Dijkstra barrier yang sederhana serta pemanfaatan grey stack
• Pendekatan titik tetap membuatnya cepat konvergen dan berbiaya rendah
• Sweep yang sangat cepat melalui sweep berbasis bitvector SIMD, menghabiskan kurang dari 5% total waktu GC
• Optimalisasi performa dengan memanfaatkan Verse heap config dan lainnya

Fitur bonus (ekstensibilitas manajemen memori)

Pembebasan objek

• Saat free dipanggil di C, objek langsung ditandai sebagai sudah dibebaskan, dan trap akan terjadi jika kemudian diakses
• Mencegah malfungsi GC akibat dangling pointer
• Referensi ke objek yang sudah dibebaskan dialihkan ke singleton free object, sehingga pendeteksian tetap pasti bahkan setelah realokasi memori
• Mencegah kebocoran memori yang memicu GC akibat pointer yang tidak terpakai

Finalizer

• Finalizer queue bergaya Java dapat diimplementasikan secara fleksibel melalui queue yang ditentukan pengguna dan pemrosesan thread

Referensi lemah

• Berperilaku sama seperti weak reference di Java, tanpa reference queue terpisah (phantom dan soft reference tidak didukung)

Weak map

• Mirip JavaScript WeakMap, tetapi semua elemen dapat diiterasi dan jumlah elemennya dapat diperiksa

Kesimpulan dan makna

Melalui FUGC, Fil-C memberikan keamanan yang kuat dan penanganan pengecualian yang intuitif terhadap penyalahgunaan free

• Dirancang agar akses ke objek yang sudah dibebaskan atau pembebasan ganda pasti memicu trap
• Jika objek tidak dibebaskan, GC akan bertanggung jawab mengumpulkannya dengan baik
• Mendukung beragam pola manajemen memori, sehingga tetap terasa akrab bagi pengembang C/Java/JavaScript

[GN⁺]

Opini Hacker News

• Hmm, Fil-C tampaknya bisa punya arti yang sangat penting. Ada banyak perangkat lunak yang hanya eksis sebagai kode C, jadi menurut saya perlu ada pendekatan untuk mempertahankannya. Kompiler C yang ada sekarang mengambil risiko keamanan besar demi memaksimalkan performa single-core, dan trade-off seperti ini rasanya sudah ketinggalan zaman. Daftar dukungannya benar-benar mengesankan: CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash, dan lain-lain. Menurut saya kecil kemungkinan perangkat lunak itu akan ditulis ulang ke Rust. Saya penasaran apakah Fil-C juga bisa dipakai untuk multitasking antarproses yang saling tidak tepercaya di lingkungan tanpa MMU. Arah yang diambil juga tampaknya tepat, seperti keamanan berbasis capability dan sinkronisasi non-blocking. Ingin tahu apakah ada yang sudah benar-benar pernah memakainya. Katanya bahkan dalam skenario terburuk pun penurunan kecepatannya hanya sekitar 4x, dan namanya juga lucu sekali. Filthsway! Filthsway!

  • Menanggapi pertanyaan apakah Fil-C memungkinkan multitasking antarproses yang tidak saling tepercaya pada komputer tanpa MMU, pada dasarnya FUGC memang dibangun di atas fitur OS yang bergantung pada MMU, tetapi saya rasa versi yang menghapus ketergantungan itu juga bisa dibuat. Soal performa, perlambatan 4x itu memang kasus terburuk, dan saya sendiri yang melaporkan angka tersebut. Saya cenderung selalu mengukur performa secara realistis dan sangat gigih memperbaiki masalah performa. Faktanya, saya juga bisa memakai program yang biasa saya gunakan sehari-hari tanpa masalah dalam versi perangkat lunak berbasis Fil-C

  • Anda bilang daftar perangkat lunak yang didukung itu mengesankan; saya setuju secara umum, tetapi saya melihat contoh-contoh itu sedikit berbeda. CPython, Perl5, dan sejenisnya adalah runtime untuk bahasa yang memang sudah terkenal punya GC lambat, jadi menambahkan satu GC lagi di atasnya rasanya bukan desain yang elegan, dan justru bisa memperbesar penurunan performa. Selain itu, sudah ada sebagian upaya untuk mengimplementasikan ulang atau menggantinya dengan Rust atau Go, misalnya SQLite dengan Turso. Dan perangkat lunak seperti ini adalah proyek fundamental yang sangat aktif dirawat, jadi bukan tidak mungkin suatu hari mereka sendiri melakukan refactoring atau porting ke Rust. Menurut saya, tempat yang lebih cocok untuk Fil-C justru kode yang kurang terawat, tidak terlalu sensitif terhadap performa tetapi masih terus dipakai, seperti program C berusia 50 tahun yang sesekali masih dijalankan seseorang

  • Kekuatan SQLite yang ditulis dalam C adalah portabilitasnya yang tinggi ke OS non-standar. Misalnya, saya pernah langsung memakainya di μC/OS-II, RTOS untuk embedded. Desain lingkungan embedded cukup berbeda dari PC/server, sehingga demi performa dan untuk mencegah fragmentasi memori, memori kadang memang sama sekali tidak dibebaskan dan objek/struktur cukup ditandai untuk digunakan ulang. Semacam custom heap allocation atau pooling. Dokumentasi VFS SQLite, pengantar Micro-Controller OS

  • Anda bilang tidak akan ada penulisan ulang perangkat lunak C dalam daftar contoh itu ke Rust, tetapi saya penasaran berapa lama lagi sampai alat static analysis berbasis AI berkembang cukup jauh untuk bisa menemukan masalah dalam kode C secara akurat dan memberi umpan balik seperti, “bagian ini akan menimbulkan error, perbaikannya begini.” Kalau alat seperti itu benar-benar muncul, mungkin terus memakai C saja juga akan jadi masuk akal

  • Perlu dicatat bahwa Fil-C saat ini belum mendukung sistem 32-bit (atau yang lebih rendah). Dokumen terkait Invisicaps di Fil-C

• Proyek seperti ini terasa sebagai kasus langka yang berjalan di antara riset dan praktik sekaligus. Hal seperti ini biasanya ditangani tim di perusahaan IT besar dan dijalankan lewat pendapatan iklan, jadi saya penasaran Fil-C bermula dari latar belakang seperti apa. Jika ini bukan sekadar proyek passion pribadi, siapa yang mendanainya, berapa tahun tenaga kerja yang sudah masuk, dan apa tujuan akhirnya

  • Menurut saya pribadi, ini memang terlihat seperti proyek passion

  • Menjawab pertanyaan soal tujuan akhir, hak cipta proyek ini tercantum sebagai 2024-2025 Epic Games, Inc.

• Senang sekali Fil-C itu ada. Meski teknologi seperti ini efektif untuk program nyata, sering kali para developer percaya bahwa “hal seperti itu tidak mungkin dilakukan”, jadi fakta bahwa ini benar-benar bisa diimplementasikan saja sudah cukup untuk memotong banyak perdebatan sekaligus

  • Saya penasaran dengan hasil benchmark. Kekhawatiran terbesar dari pendekatan seperti ini adalah jangan-jangan performanya jatuh sangat drastis pada use case tertentu yang masih membuat C/C++ populer. Jika throughput, latensi, dan penggunaan memorinya jadi terlalu mirip dengan bahasa seperti Go, pada akhirnya alasan untuk memilihnya mungkin jadi sangat sedikit

  • Dalam bahasa pemrograman, perdebatan performa versus hal lain sudah ada sejak zaman assembly. Hanya saja kebanyakan developer bukanlah visioner luar biasa seperti Ivan Suntherland, Alan Kay, Steve Jobs, atau Bret Victor, melainkan orang biasa yang baru percaya setelah melihat sesuatu berjalan langsung di depan mata. Mungkin karena itu sampai sekarang dunia masih dipenuhi tiruan UNIX dan C, dan alih-alih menciptakan sesuatu yang baru, banyak orang hidup dengan sekadar mengulang visi masa lalu. Tentu saja, dua orang yang membuat UNIX dan C pada 1970-an itu sendiri juga visioner hebat

• Saya penasaran kenapa menggunakan strategi retreating wavefront alih-alih advancing wavefront

• Jika pemanggilan free(...) dalam program C yang ada sebenarnya sudah ditempatkan dengan semestinya, dan untuk setiap pointer juga sudah dikelola informasi batas terpisah, kenapa memilih GC penuh? Saya malah merasa teknik temporal checking model lock-and-key (referensi: tautan paper) mungkin lebih baik dari sisi prediktabilitas penggunaan memori, performa, dan scheduling. Dugaan saya mungkin ruang penyimpanan key terlalu besar, waktu pengecekan terlalu lama, atau ada masalah race condition di lingkungan multithread

  • Pendekatan lock-and-key tidak punya karakteristik pintar khas Fil-C. Kekuatan model capability Fil-C adalah bahwa ia sepenuhnya thread-safe dan, dalam kebanyakan kasus, tidak memerlukan atomics khusus atau locking

  • Menarik juga bahwa ia mengizinkan operasi pointer di luar batas selama tidak didereferensikan. Kompiler kadang memanfaatkan UB semacam ini untuk optimisasi (pertanyaan terkait di Stack Overflow), jadi saya penasaran apakah LLVM internal Fil-C menonaktifkan optimisasi seperti itu, atau malah mengelola pointer sebagai kombinasi “base + offset” sehingga kemungkinan itu tertutup sejak awal. Kalau begitu, apakah ada optimisasi tertentu untuk pointer biasa yang jadi terlewat

• Benar-benar tampak seperti proyek yang keren. Saya memperhatikan bahwa fast path dari pollcheck hanyalah load-and-branch. Ada teknik menarik yang dipakai sebagai pengganti branch seperti ini, dan dijelaskan dengan baik dalam dokumen "pemeriksaan suspend implisit" di blog resmi Android

  • Optimisasi seperti itu memang umum dipakai untuk poll check. Faktanya, sebagian besar JVM production sudah menerapkannya. Tetapi saya sendiri belum sampai di tahap perlu memikirkan optimisasi serendah itu. Saat ini saya masih harus mengerjakan dulu optimisasi dasar tingkat tinggi yang masih tersisa

• C dengan dukungan konkurensi plus GC, dan itu pun GC non-moving, benar-benar mengejutkan. Kalau proyek C ukuran menengah bisa menukar bug memori dengan kerugian performa runtime 2~3x, saya cukup rela menerimanya. Saya penasaran seberapa mudah adopsinya secara bertahap. Apakah bisa dilakukan per target, atau harus mengganti seluruh toolchain

• Saya peduli pada C, performa, dan keamanan sekaligus. Struktur GC dan capability ini menarik. Saya sudah berkali-kali memikirkan seperti apa “C yang lebih aman” itu, dan sempat beberapa kali mempertimbangkan konsep capability, tetapi saya memang tidak terlalu bisa menangani kode kompiler. Saya penasaran apakah dukungan Windows sulit diwujudkan

  • Sedikit di luar topik, tetapi karena kalimat pertama tidak memakai Oxford comma, saya butuh waktu cukup lama untuk memahami maksudnya. Jarang ada contoh sejelas ini

• Saya penasaran bagaimana GC melacak root object. Apakah ada tahap kompilasi yang menandai root yang harus dipindai GC, atau kalau ada yang tahu bisa menjelaskan

  • LLVM menyelesaikannya dengan menyisipkan instruksi untuk mengisi stack map

• Proyek ini benar-benar luar biasa. Aneh rasanya saya belum pernah mendengarnya sampai sekarang. Saya tidak sabar untuk mencobanya sendiri. Mungkin keterbatasan performa membuatnya sulit dipakai untuk layanan produksi, tetapi sebagai cara untuk memverifikasi langsung keamanan sebagian program, ini tampak sangat berguna. Rasanya lebih menyeluruh daripada sanitizer yang biasa saya pakai