Crate dumpster

A cycle-tracking concurrent garbage collector with an easy-to-use API.

Most garbage collectors are tracing garbage collectors, meaning that they keep track of a set of roots which are directly accessible from the stack, and then use those roots to find the set of all accessible allocations. However, because Rust does not allow us to hook into when a value is moved, it’s quite difficult to detect when a garbage-collected value stops being a root.

dumpster takes a different approach. It begins by using simple reference counting, then automatically detects cycles. Allocations are freed when their reference count reaches zero or when they are only accessible via their descendants.

Garbage-collected pointers can be created and destroyed in O(1) amortized time, but destroying a garbage-collected pointer may take O(r), where r is the number of existing garbage-collected references, on occasion. However, the cleanups that require O(r) performance are performed once every O(1/r) times a reference is dropped, yielding an amortized O(1) runtime.

Why should you use this crate?

In short, dumpster offers a great mix of usability, performance, and flexibility.

• dumpster’s API is a drop-in replacement for std’s reference-counted shared allocations (Rc and Arc).
• It’s very performant and has builtin implementations of both thread-local and concurrent garbage collection.
• There are no restrictions on the reference structure within a garbage-collected allocation (references may point in any way you like).
• It’s trivial to make a custom type Trace using the provided derive macros.
• You can even store ?Sized data in a garbage-collected pointer!

Module structure

dumpster contains 3 core modules: the root (this module), as well as sync and unsync. sync contains an implementation of thread-safe garbage-collected pointers, while unsync contains an implementation of thread-local garbage-collected pointers which cannot be shared across threads. Thread-safety requires some synchronization overhead, so for a single-threaded application, it is recommended to use unsync.

The project root contains common definitions across both sync and unsync. Types which implement Trace can immediately be used in unsync, but in order to use sync’s garbage collector, the types must also implement Sync.

Examples

If your code is meant to run as a single thread, or if your data doesn’t need to be shared across threads, you should use unsync::Gc to store your allocations.

use dumpster::unsync::Gc;
use std::cell::Cell;

let my_gc = Gc::new(Cell::new(0451));

let other_gc = my_gc.clone(); // shallow copy
other_gc.set(512);

assert_eq!(my_gc.get(), 512);

For data which is shared across threads, you can use sync::Gc with the exact same API.

use dumpster::sync::Gc;
use std::sync::Mutex;

let my_shared_gc = Gc::new(Mutex::new(25));
let other_shared_gc = my_shared_gc.clone();

std::thread::scope(|s| {
    s.spawn(move || {
        *other_shared_gc.lock().unwrap() = 35;
    });
});

println!("{}", *my_shared_gc.lock().unwrap());

It’s trivial to use custom data structures with the provided derive macro.

use dumpster::{unsync::Gc, Trace};
use std::cell::RefCell;

#[derive(Trace)]
struct Foo {
    refs: RefCell<Vec<Gc<Foo>>>,
}

let foo = Gc::new(Foo {
    refs: RefCell::new(Vec::new()),
});

foo.refs.borrow_mut().push(foo.clone());

drop(foo);

// even though foo had a self reference, it still got collected!

Installation

To use dumpster, add the following lines to your Cargo.toml.

[dependencies]
dumpster = "1.1.0"

Optional features

derive

derive is enabled by default. It enables the derive macro for Trace, which makes it easy for users to implement their own Trace types.

use dumpster::{unsync::Gc, Trace};
use std::cell::RefCell;

#[derive(Trace)] // no manual implementation required
struct Foo(RefCell<Option<Gc<Foo>>>);

let my_foo = Gc::new(Foo(RefCell::new(None)));
*my_foo.0.borrow_mut() = Some(my_foo.clone());

drop(my_foo); // my_foo will be automatically cleaned up

either

either is disabled by default. It adds support for the either crate, specifically by implementing Trace for either::Either.

coerce-unsized

coerce-unsized is disabled by default. This enables the implementation of std::ops::CoerceUnsized for each garbage collector, making it possible to use Gc with !Sized types conveniently. To use coerce-unsized, edit your installation to Cargo.toml to include the feature.

[dependencies]
dumpster = { version = "1.1.0", features = ["coerce-unsized"]}

License

dumpster is licensed under the Mozilla Public License, version 2.0. For more details, refer to LICENSE.md.

Modules

sync

Thread-safe shared garbage collection.

unsync

Thread-local garbage collection.

Traits

Trace

The trait that any garbage-Trace data must implement.

Visitor

A visitor for a garbage collected value.

Derive Macros

Trace

The derive macro for implementing Trace.