Breadth-first Cycle Collection Reference Counting: Theory and a Rust Smart Pointer Implementation

We present a new garbage collection reference counting algorithm capable of collecting reference cycles—overcoming a known limitation of traditional reference counting. The algorithm's key features include resilience to errors during tracing, support for object finalisation, no need for supplementary heap memory during collection, and a fast breadth-first tracing approach that avoids stack overflows. We implement the algorithm as a Rust library that is idiomatic and highly compatible with the Rust ecosystem and that leverages Rust's type system and borrow checker to minimise unsafe code and prevent undefined behaviour. We report benchmarks that show that our proposal performs comparably to popular Rust alternatives and outperforms them when dealing with garbage cycles.