9 releases (5 breaking)
0.6.2 | Nov 12, 2024 |
---|---|
0.6.0 | Aug 27, 2024 |
0.4.0 | Jul 29, 2024 |
0.2.0 | May 25, 2023 |
0.1.0 | Mar 14, 2023 |
#108 in Memory management
125 downloads per month
210KB
5K
SLoC
rust-cc
A fast garbage collector based on cycle collection for Rust programs.
This crate provides a Cc
(Cycle Collected) smart pointer, which is basically a Rc
that automatically detects and
deallocates reference cycles. If there are no reference cycles, then Cc
behaves like Rc
and deallocates
immediately when the reference counter drops to zero.
Currently, the cycle collector is not concurrent. As such, Cc
doesn't implement Send
nor Sync
.
Features
- Fully customizable with Cargo features
- Automatic execution of collections
- Finalization
- Weak pointers
- Cleaners
- No-std support (requires ELF TLS due to thread locals)
Basic usage example
#[derive(Trace, Finalize)]
struct Data {
a: Cc<u32>,
b: RefCell<Option<Cc<Data>>>,
}
// Rc-like API
let my_cc = Cc::new(Data {
a: Cc::new(42),
b: RefCell::new(None),
});
let my_cc_2 = my_cc.clone();
let pointed: &Data = &*my_cc_2;
drop(my_cc_2);
// Create a cycle!
*my_cc.b.borrow_mut() = Some(my_cc.clone());
// Here, the allocated Data instance doesn't get immediately deallocated, since there is a cycle.
drop(my_cc);
// We have to call the cycle collector
collect_cycles();
// collect_cycles() is automatically called from time to time when creating new Ccs,
// calling it directly only ensures that a collection is run (like at the end of the program)
The derive macro for the Finalize
trait generates an empty finalizer. To write custom finalizers implement the Finalize
trait manually:
impl Finalize for Data {
fn finalize(&self) {
// Finalization code called when a Data object is about to be deallocated
// to allow resource clean up (like closing file descriptors, etc)
}
}
For more information read the docs.
The collection algorithm
The main idea is to discover the roots (i.e. objects which are surely not garbage) making use of the information contained in the reference counter, instead of having them from another source.
Usually, in garbage collected languages, the runtime has always a way to know which objects are roots (knowing the roots allows
the garbage collector to know which objects are still accessible by the program and therefore which can and cannot be deallocated).
However, since Rust has no runtime, this information isn't available! For this reason, garbage collectors implemented
in Rust for Rust programs have a very difficult time figuring out which objects can be deallocated and which
cannot because they can still be accessed by the program.
rust-cc, using the reference counters, is able to find the roots at runtime while collecting, eliminating the need to
constantly keep track of them. This is also the reason why the standard RefCell
(instead of a custom one) can be
safely used inside cycle collected objects for interior mutability.
Moreover, the implemented cycle collector should be generally faster than mark-and-sweep garbage collectors on big (and fragmented) heaps, since there's no need to trace the whole heap every time it runs.
If you're interested in reading the source code, the algorithm is described more deeply in CONTRIBUTING.md.
Benchmarks
Benchmarks comparing rust-cc to other collectors can be found at https://github.com/frengor/rust-cc-benchmarks.
License
This project is licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this crate by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Dependencies
~0.3–0.8MB
~18K SLoC