Fil's Unbelievable Garbage Collector

Original Article ↗ Hacker News Discussion ↗

Algorithm & Design

  • Fil-C compiles C into a memory-safe dialect using “InvisiCaps” capabilities and a concurrent, non‑moving, Dijkstra‑barrier GC (FUGC).
  • The collector is precise/accurate: LLVM is instrumented to emit stack maps and metadata so the GC knows exactly where pointers are, rather than scanning conservatively.
  • Pointer–integer casts are allowed but “laundered”: if a pointer goes through an integer and is stored, it loses its capability; later dereference traps instead of becoming a hidden root.
  • GC uses a grey-stack, concurrent marking and a sweeping phase based on bitvector SIMD; dead objects can be reclaimed via bitmaps without touching their contents.
  • Stack scanning is bounded by stack depth; in practice, participants argue typical stacks are small enough that scans are rarely the main bottleneck.

Performance, Overheads & Latency

  • Reported slowdowns range widely:
    • Some programs near 1×, many in the ~2–4× band.
    • Pathological cases observed: ~9× and up to ~49× for STL/SIMD‑heavy or QuickJS workloads (a recent bug made unions particularly bad; fixing it improved one QuickJS case ~6×).
  • Author’s rough targets: worst‑case ~2×, average ~1.5×, with SIMD/array‑heavy code close to 1× and pointer‑chasey tree/graph code >2×.
  • Memory overhead is estimated around 2× for GC alone, with additional overhead from capabilities; code size is currently very bloated (guessed ~5×) due to unoptimized metadata and ELF constraints.
  • Debate on “perf‑sensitive” C/C++:
    • One side: most user‑facing C/C++ could be 2–4× slower without noticeable UX impact, especially IO‑bound tools.
    • Other side: many domains (compilers, browsers, games, DAWs, scientific computing, embedded) would notice even 2×.
  • Latency: FUGC is concurrent; pauses are limited to safepoint callbacks (poll checks) and stack scans. For latency‑critical workloads (games, audio, hard real‑time), this may still be unacceptable; ideas like end‑of‑frame safepoints are mentioned but not implemented.

Use Cases, Compatibility & Adoption

  • Fil-C has been used to run substantial existing C code (e.g., shells, interpreters, build tools, editors). It can “just work” on many real programs, sometimes uncovering bugs.
  • Strong fit: large legacy C where rewrites are unlikely and absolute peak performance isn’t critical; poor fit: embedded/hard real‑time, JITs (no PROT_EXEC), current 32‑bit targets.
  • Some see it as evidence that “memory-safe C” for existing code is practically achievable, providing an existence proof against claims that such systems can’t work.

Safety Model vs Alternatives

  • Capability system is designed to be thread‑safe without pervasive atomics/locks.
  • Undefined‑behavior‑driven optimizations are disabled via LLVM flags and patches; the compiler runs a controlled opt pipeline before instrumentation, aiming for “garbage in, memory safety out”.
  • Compared with:
    • Lock‑and‑key temporal checking: would miss Fil‑C’s thread‑safety properties.
    • RLBox: provides sandboxing but not memory safety inside the sandbox; some argue performance comparisons are still relevant, others say they solve different threat models.
    • Rust: can still rely on unsafe; Fil‑C is positioned as slower/heavier but with no escape hatches.

GC vs Ownership Philosophy

  • One camp calls GC an “evolutionary dead end” and prefers compile‑time resource management with no runtime cost.
  • Others counter:
    • All memory management has costs (runtime, compile‑time and cognitive).
    • Tracing GC is often faster than malloc/free or refcounting under some workloads, at the cost of more memory.
    • For complex, cyclic, graph‑like structures, tracing GC is very natural; simulating it with ownership+RC can be more complex and sometimes slower.
  • Broad agreement that this is all about tradeoffs, not absolutes.