#memory #garbage #graph #data-structure #graph-algorithms

no-std moving_gc_arena

Lightweight Garbage-collectable regions using indices and explicit roots

8 releases

new 0.3.2 Nov 22, 2020
0.3.1 Jun 27, 2020
0.2.6 May 12, 2020
0.2.4 Apr 20, 2020
0.1.1 Jan 7, 2020

#40 in Memory management

27 downloads per month

MPL-2.0 license

100KB
2.5K SLoC

Version 0.3.2 Badge MPL License Badge

Moving GC Arena

This is a library for indexed regions supporting blazingly fast allocation, with efficient garbage collection, traversals, and deep cloning.

You should use this library if you want to keep a safe cyclic graph data structure, with simple, performant garbage collection. Access to GC operations exposes efficient traversals and cloning. This library does not read the Rust stack, instead, roots are acquired resources, which can be used like any other resource and dropped as normal. It compiles on stable 2018 Rust and requires only minimal unsafe code for most operations. Dereferencing indices uses a reference to the region, giving strong safety guarantees.

You should not use this library if you have very hard real-time requirements, and cannot handle amortized costs on the order of Vec-reallocation. In the current version, only single-threaded use is possible. Because of the algorithms chosen, this library is well-suited for frequent allocations, much like arena allocation.

Details of features and limitations

  • Members are a fixed type and size.
  • Regions and most indices are not Send/Sync in the current version.
  • Drop implementations are called as normal whenever an object is collected. There are no finalizers which can read the region state.
  • Garbage collection may be performed both automatically and manually. Every buffer reallocation triggers a garbage collection for the best performance.
  • Garbage collection is quick: It does not scan the stack, and requires no extra allocation.
  • Size cannot yet be tuned: We always double the size at least. Calling a manual gc will shrink the allocation.
  • An optional features allows indices to check region and generation information.

Example Usage

use moving_gc_arena as gc;

let mut r = gc::Region::new();

struct Adj(Vec<gc::Ix<Adj>>);
impl gc::HasIx<Adj> for Adj {
 fn foreach_ix<'b, 'a : 'b, F>(&'a mut self, mut f: F) where
     F: FnMut(&'b mut gc::Ix<T>)
 {
     self.0.foreach_ix(f);
 }
}
impl Adj {
    fn new() -> Self {
        Adj(Vec::new())
    }
}

let mut obj1 = r.alloc(|_|{Adj::new()}).root();
let mut obj2 = r.alloc(|_|{Adj::new()}).root();
let mut obj3 = r.alloc(|_|{Adj::new()}).root();

// mutual cycle
obj1.get_mut(&mut r).0.push(obj2.ix());
obj2.get_mut(&mut r).0.push(obj1.ix());

// self-cycle
obj3.get_mut(&mut r).0.push(obj3.ix());

std::mem::drop(obj1);
std::mem::drop(obj3);

r.gc(); // manually-triggered collection
//obj3 now collected but obj1 and obj2 are live

No runtime deps

Features

  • debug-arena
  • packed-headers