Garbage Collector Implementer

Implements tracing garbage collectors (mark-compact, generational, etc.).

When to Use

• Building language runtimes
• Implementing interpreters/compilers
• Learning memory management
• Optimizing memory allocation

What This Skill Does

1. Implements heap allocation - Object layout and allocation
2. Builds tracing collectors - Mark-sweep, mark-compact, copying
3. Handles roots - Stack and global roots
4. Optimizes - Generational, incremental collection

Key Concepts

GC Algorithms Comparison

Tips

• Track all root pointers carefully
• Handle weak references specially
• Consider write barriers for incremental collection
• Profile pause times in production
• Use thread-local allocation for speed

Related Skills

• jit-compiler-builder - Build VM runtime
• lambda-calculus-interpreter - Bytecode interpreter

Canonical References

Tradeoffs and Limitations

Algorithm Tradeoffs

When NOT to Use GC

• For real-time systems: Use real-time GC or custom allocators
• For memory-constrained: Use manual memory management or arenas
• For deterministic timing: Avoid GC pauses; use pooling
• For bare metal: Use static allocation or custom allocators

Complexity Analysis

• Mark-Sweep: O(n + m) where n = heap objects, m = marks
• Copying: O(n) where n = live objects
• Generational: O(n) for minor collections (young gen), full O(n) for major
• Space overhead: Forwarding pointers, remembered sets

Limitations

• Pause times: Stop-the-world collectors cause latency spikes
• Fragmentation: Mark-sweep causes internal/external fragmentation
• Overhead: GC costs 5-20% CPU time typically
• Weak references: Need special handling for finalizers
• Debugging: Memory leaks harder to find ( GC bugs are subtle)
• Portability: GC depends on memory layout, pointer formats

Assessment Criteria

A high-quality GC implementation should have:

Quality Indicators

✅ Good: Correct, low pause, efficient ⚠️ Warning: Memory bloat, occasional pauses ❌ Bad: Collects live objects (memory corruption), doesn't terminate

Research Tools & Artifacts

Real-world garbage collectors to study:

Academic/Research GCs

• Immix (Blackburn et al.) - High throughput
• ZGC (Oracle) - Sub-millisecond pauses
• Shenandoah (Red Hat) - Concurrent compaction
• MMTk (Oxford) - Memory management tool kit

Research Frontiers

1. Concurrent GC

• Goal: Reduce pause times by running concurrently
• Techniques: Write barriers, dirty bits, concurrent marking
• Papers: "Garbage Collection in Java 11" (Google I/O)
• Tools: ZGC, Shenandoah, Go GC

2. Region-Based Allocation

• Goal: Region-based memory management
• Techniques: Regions with different lifetimes
• Papers: "Memory Management with Regions" (Gay & Aiken)
• Application: Rust's arena allocator

3. GC for Functional Languages

• Goal: Efficient for immutable data
• Techniques: Generational, incremental, persistent data structures
• Papers: "The Design of Cryptographic Applications"
• Application: Haskell, Clojure, OCaml

4. Real-Time GC

• Goal: Predictable pause times
• Techniques: Incremental, concurrent, hybrid
• Papers: "Real-Time Garbage Collection" (Lieberman & Hewitt)
• Application: Embedded systems, games

Implementation Pitfalls

The "Write Barrier" Problem

Concurrent GC needs write barriers:

// Write barrier for generational GC
void write_barrier(void* obj, void* field, void* new_value) {
    // If storing old->new ref and new is in older gen
    if (is_heap_object(new_value) && 
        generation(new_value) < generation(obj)) {
        // Remember this store for minor GC
        remember_set_add(obj);
    }
    // Perform actual write
    *field = new_value;
}

The "Stack Scanning" Challenge

Must scan all threads' stacks:

void scan_roots() {
    for (Thread* t = all_threads; t != NULL; t = t->next) {
        // Get stack boundaries
        void* stack_top = t->stack_top;
        void* stack_bottom = t->stack_bottom;
        
        // Scan stack for pointers
        for (void* p = stack_bottom; p < stack_top; p += sizeof(void*)) {
            void* obj = *p;
            if (is_heap_object(obj)) {
                mark(obj);
            }
        }
    }
}

This is why GC pause times vary with stack depth!