A lock-free concurrent slab.
Slabs provide pre-allocated storage for many instances of a single data type. When a large number of values of a single type are required, this can be more efficient than allocating each item individually. Since the allocated items are the same size, memory fragmentation is reduced, and creating and removing new items can be very cheap.
This crate implements a lock-free concurrent slab, indexed by
Note: This crate is currently experimental. Please feel free to use it in your projects, but bear in mind that there's still plenty of room for optimization, and there may still be some lurking bugs.
First, add this to your
This crate provides two types,
Pool, which provide slightly
different APIs for using a sharded slab.
Slab implements a slab for storing small types, sharing them between
threads, and accessing them by index. New entries are allocated by inserting
data, moving it in by value. Similarly, entries may be deallocated by taking
from the slab, moving the value out. This API is similar to a
but allowing lock-free concurrent insertion and removal.
In contrast, the
Pool type provides an object pool style API for
reusing storage. Rather than constructing values and moving them into
the pool, as with
Slab, allocating an entry from the pool
takes a closure that's provided with a mutable reference to initialize
the entry in place. When entries are deallocated, they are cleared in
place. Types which own a heap allocation can be cleared by dropping any
data they store, but retaining any previously-allocated capacity. This
means that a
Pool may be used to reuse a set of existing heap
allocations, reducing allocator load.
Inserting an item into the slab, returning an index:
use Slab; let slab = new; let key = slab.insert.unwrap; assert_eq!;
To share a slab across threads, it may be wrapped in an
use Slab; use Arc; let slab = new; let slab2 = slab.clone; let thread2 = spawn; let key1 = slab.insert.unwrap; assert_eq!; // Wait for thread 2 to complete. let key2 = thread2.join.unwrap; // The item inserted by thread 2 remains in the slab. assert_eq!;
If items in the slab must be mutated, a
RwLock may be used for
each item, providing granular locking of items rather than of the slab:
use Slab; use ; let slab = new; let key = slab.insert.unwrap; let slab2 = slab.clone; let thread2 = spawn; thread2.join.unwrap; let hello = slab.get.expect; let mut hello = hello.lock.expect; assert_eq!;
Comparison with Similar Crates
slab: Carl Lerche's
slabcrate provides a slab implementation with a similar API, implemented by storing all data in a single vector.
sharded-slab, inserting and removing elements from the slab requires mutable access. This means that if the slab is accessed concurrently by multiple threads, it is necessary for it to be protected by a
RwLock. Items may not be inserted or removed (or accessed, if a
Mutexis used) concurrently, even when they are unrelated. In many cases, the lock can become a significant bottleneck. On the other hand,
sharded-slaballows separate indices in the slab to be accessed, inserted, and removed concurrently without requiring a global lock. Therefore, when the slab is shared across multiple threads, this crate offers significantly better performance than
However, the lock free slab introduces some additional constant-factor overhead. This means that in use-cases where a slab is not shared by multiple threads and locking is not required,
sharded-slabwill likely offer slightly worse performance.
sharded-slaboffers significantly improved performance in concurrent use-cases, while
slabshould be preferred in single-threaded use-cases.
Safety and Correctness
Most implementations of lock-free data structures in Rust require some
amount of unsafe code, and this crate is not an exception. In order to catch
potential bugs in this unsafe code, we make use of
permutation-testing tool for concurrent Rust programs. All
this crate occur in accesses to
UnsafeCells. This means that when
those accesses occur in this crate's tests,
loom will assert that they are
valid under the C11 memory model across multiple permutations of concurrent
executions of those tests.
In order to guard against the ABA problem, this crate makes use of
generational indices. Each slot in the slab tracks a generation counter
which is incremented every time a value is inserted into that slot, and the
indices returned by
Slab::insert include the generation of the slot when
the value was inserted, packed into the high-order bits of the index. This
ensures that if a value is inserted, removed, and a new value is inserted
into the same slot in the slab, the key returned by the first call to
insert will not map to the new value.
Since a fixed number of bits are set aside to use for storing the generation counter, the counter will wrap around after being incremented a number of times. To avoid situations where a returned index lives long enough to see the generation counter wrap around to the same value, it is good to be fairly generous when configuring the allocation of index bits.
These graphs were produced by benchmarks of the sharded slab implementation,
The first shows the results of a benchmark where an increasing number of
items are inserted and then removed into a slab concurrently by five
threads. It compares the performance of the sharded slab implementation
The second graph shows the results of a benchmark where an increasing
number of items are inserted and then removed by a single thread. It
compares the performance of the sharded slab implementation with an
RwLock<slab::Slab> and a
These benchmarks demonstrate that, while the sharded approach introduces a small constant-factor overhead, it offers significantly better performance across concurrent accesses.
This project is licensed under the MIT license.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you, shall be licensed as MIT, without any additional terms or conditions.