#heap #data-structures #reference-counting #immutability #slot #handle #thread-sharable

yanked garbo

Global reference-counted, thread-sharable, immutable heap

0.2.0 Jul 3, 2019
0.1.0 Jul 2, 2019

#51 in #slot

GPL-3.0 license

16KB
181 lines

Garbo

A global reference-counted, thread-sharable, immutable heap

Rationale

This crate provides a reference-counted global heap for values that can be referenced from multiple threads. It sidesteps most of the problems with thread-concurrent access by disallowing mutation of the stored values.

How it works

The crate exports only one function; garbo::put, which puts a value on the shared heap, and returns a Handle.

The handle is reference counted, and can be freely cloned and sent between threads. When the last Handle goes out of scope, the corresponding slot in the heap is marked as free, and will be re-used on the next call to put.

Only the calls to put that needs to allocate a new slot actually have to wait for a mutex.

Example (from the tests)

// write in one thread, read in the other

let (sender, receiver) = crossbeam_channel::unbounded();

handles.push(std::thread::spawn(move || {
    for i in 0..n {
        let handle = garbo::put(i);
        sender.send((handle, i)).unwrap()
    }
}));

handles.push(std::thread::spawn(move || {
    for _ in 0..n {
        match receiver.recv() {
            Ok((handle, i)) => assert_eq!(*handle, i),
            Err(_) => panic!(),
        }
    }
}));

Dependencies

~1.5MB
~25K SLoC