1# sharded-slab
2
3A lock-free concurrent slab.
4
5[![Crates.io][crates-badge]][crates-url]
6[![Documentation][docs-badge]][docs-url]
7[![CI Status][ci-badge]][ci-url]
8[![GitHub License][license-badge]][license]
9![maintenance status][maint-badge]
10
11[crates-badge]: https://img.shields.io/crates/v/sharded-slab.svg
12[crates-url]: https://crates.io/crates/sharded-slab
13[docs-badge]: https://docs.rs/sharded-slab/badge.svg
14[docs-url]: https://docs.rs/sharded-slab/latest
15[ci-badge]: https://github.com/hawkw/sharded-slab/workflows/CI/badge.svg
16[ci-url]: https://github.com/hawkw/sharded-slab/actions?workflow=CI
17[license-badge]: https://img.shields.io/crates/l/sharded-slab
18[license]: LICENSE
19[maint-badge]: https://img.shields.io/badge/maintenance-experimental-blue.svg
20
21Slabs provide pre-allocated storage for many instances of a single data
22type. When a large number of values of a single type are required,
23this can be more efficient than allocating each item individually. Since the
24allocated items are the same size, memory fragmentation is reduced, and
25creating and removing new items can be very cheap.
26
27This crate implements a lock-free concurrent slab, indexed by `usize`s.
28
29**Note**: This crate is currently experimental. Please feel free to use it in
30your projects, but bear in mind that there's still plenty of room for
31optimization, and there may still be some lurking bugs.
32
33## Usage
34
35First, add this to your `Cargo.toml`:
36
37```toml
38sharded-slab = "0.1.7"
39```
40
41This crate provides two types, [`Slab`] and [`Pool`], which provide slightly
42different APIs for using a sharded slab.
43
44[`Slab`] implements a slab for _storing_ small types, sharing them between
45threads, and accessing them by index. New entries are allocated by [inserting]
46data, moving it in by value. Similarly, entries may be deallocated by [taking]
47from the slab, moving the value out. This API is similar to a `Vec<Option<T>>`,
48but allowing lock-free concurrent insertion and removal.
49
50In contrast, the [`Pool`] type provides an [object pool] style API for
51_reusing storage_. Rather than constructing values and moving them into
52the pool, as with [`Slab`], [allocating an entry][create] from the pool
53takes a closure that's provided with a mutable reference to initialize
54the entry in place. When entries are deallocated, they are [cleared] in
55place. Types which own a heap allocation can be cleared by dropping any
56_data_ they store, but retaining any previously-allocated capacity. This
57means that a [`Pool`] may be used to reuse a set of existing heap
58allocations, reducing allocator load.
59
60[`Slab`]: https://docs.rs/sharded-slab/0.1.4/sharded_slab/struct.Slab.html
61[inserting]: https://docs.rs/sharded-slab/0.1.4/sharded_slab/struct.Slab.html#method.insert
62[taking]: https://docs.rs/sharded-slab/0.1.4/sharded_slab/struct.Slab.html#method.take
63[`Pool`]: https://docs.rs/sharded-slab/0.1.4/sharded_slab/struct.Pool.html
64[create]: https://docs.rs/sharded-slab/0.1.4/sharded_slab/struct.Pool.html#method.create
65[cleared]: https://docs.rs/sharded-slab/0.1.4/sharded_slab/trait.Clear.html
66[object pool]: https://en.wikipedia.org/wiki/Object_pool_pattern
67
68### Examples
69
70Inserting an item into the slab, returning an index:
71
72```rust
73use sharded_slab::Slab;
74let slab = Slab::new();
75
76let key = slab.insert("hello world").unwrap();
77assert_eq!(slab.get(key).unwrap(), "hello world");
78```
79
80To share a slab across threads, it may be wrapped in an `Arc`:
81
82```rust
83use sharded_slab::Slab;
84use std::sync::Arc;
85let slab = Arc::new(Slab::new());
86
87let slab2 = slab.clone();
88let thread2 = std::thread::spawn(move || {
89    let key = slab2.insert("hello from thread two").unwrap();
90    assert_eq!(slab2.get(key).unwrap(), "hello from thread two");
91    key
92});
93
94let key1 = slab.insert("hello from thread one").unwrap();
95assert_eq!(slab.get(key1).unwrap(), "hello from thread one");
96
97// Wait for thread 2 to complete.
98let key2 = thread2.join().unwrap();
99
100// The item inserted by thread 2 remains in the slab.
101assert_eq!(slab.get(key2).unwrap(), "hello from thread two");
102```
103
104If items in the slab must be mutated, a `Mutex` or `RwLock` may be used for
105each item, providing granular locking of items rather than of the slab:
106
107```rust
108use sharded_slab::Slab;
109use std::sync::{Arc, Mutex};
110let slab = Arc::new(Slab::new());
111
112let key = slab.insert(Mutex::new(String::from("hello world"))).unwrap();
113
114let slab2 = slab.clone();
115let thread2 = std::thread::spawn(move || {
116    let hello = slab2.get(key).expect("item missing");
117    let mut hello = hello.lock().expect("mutex poisoned");
118    *hello = String::from("hello everyone!");
119});
120
121thread2.join().unwrap();
122
123let hello = slab.get(key).expect("item missing");
124let mut hello = hello.lock().expect("mutex poisoned");
125assert_eq!(hello.as_str(), "hello everyone!");
126```
127
128## Comparison with Similar Crates
129
130- [`slab`][slab crate]: Carl Lerche's `slab` crate provides a slab implementation with a
131  similar API, implemented by storing all data in a single vector.
132
133  Unlike `sharded-slab`, inserting and removing elements from the slab requires
134  mutable access. This means that if the slab is accessed concurrently by
135  multiple threads, it is necessary for it to be protected by a `Mutex` or
136  `RwLock`. Items may not be inserted or removed (or accessed, if a `Mutex` is
137  used) concurrently, even when they are unrelated. In many cases, the lock can
138  become a significant bottleneck. On the other hand, `sharded-slab` allows
139  separate indices in the slab to be accessed, inserted, and removed
140  concurrently without requiring a global lock. Therefore, when the slab is
141  shared across multiple threads, this crate offers significantly better
142  performance than `slab`.
143
144  However, the lock free slab introduces some additional constant-factor
145  overhead. This means that in use-cases where a slab is _not_ shared by
146  multiple threads and locking is not required, `sharded-slab` will likely
147  offer slightly worse performance.
148
149  In summary: `sharded-slab` offers significantly improved performance in
150  concurrent use-cases, while `slab` should be preferred in single-threaded
151  use-cases.
152
153[slab crate]: https://crates.io/crates/slab
154
155## Safety and Correctness
156
157Most implementations of lock-free data structures in Rust require some
158amount of unsafe code, and this crate is not an exception. In order to catch
159potential bugs in this unsafe code, we make use of [`loom`], a
160permutation-testing tool for concurrent Rust programs. All `unsafe` blocks
161this crate occur in accesses to `loom` `UnsafeCell`s. This means that when
162those accesses occur in this crate's tests, `loom` will assert that they are
163valid under the C11 memory model across multiple permutations of concurrent
164executions of those tests.
165
166In order to guard against the [ABA problem][aba], this crate makes use of
167_generational indices_. Each slot in the slab tracks a generation counter
168which is incremented every time a value is inserted into that slot, and the
169indices returned by `Slab::insert` include the generation of the slot when
170the value was inserted, packed into the high-order bits of the index. This
171ensures that if a value is inserted, removed,  and a new value is inserted
172into the same slot in the slab, the key returned by the first call to
173`insert` will not map to the new value.
174
175Since a fixed number of bits are set aside to use for storing the generation
176counter, the counter will wrap  around after being incremented a number of
177times. To avoid situations where a returned index lives long enough to see the
178generation counter wrap around to the same value, it is good to be fairly
179generous when configuring the allocation of index bits.
180
181[`loom`]: https://crates.io/crates/loom
182[aba]: https://en.wikipedia.org/wiki/ABA_problem
183
184## Performance
185
186These graphs were produced by [benchmarks] of the sharded slab implementation,
187using the [`criterion`] crate.
188
189The first shows the results of a benchmark where an increasing number of
190items are inserted and then removed into a slab concurrently by five
191threads. It compares the performance of the sharded slab implementation
192with a `RwLock<slab::Slab>`:
193
194<img width="1124" alt="Screen Shot 2019-10-01 at 5 09 49 PM" src="https://user-images.githubusercontent.com/2796466/66078398-cd6c9f80-e516-11e9-9923-0ed6292e8498.png">
195
196The second graph shows the results of a benchmark where an increasing
197number of items are inserted and then removed by a _single_ thread. It
198compares the performance of the sharded slab implementation with an
199`RwLock<slab::Slab>` and a `mut slab::Slab`.
200
201<img width="925" alt="Screen Shot 2019-10-01 at 5 13 45 PM" src="https://user-images.githubusercontent.com/2796466/66078469-f0974f00-e516-11e9-95b5-f65f0aa7e494.png">
202
203These benchmarks demonstrate that, while the sharded approach introduces
204a small constant-factor overhead, it offers significantly better
205performance across concurrent accesses.
206
207[benchmarks]: https://github.com/hawkw/sharded-slab/blob/master/benches/bench.rs
208[`criterion`]: https://crates.io/crates/criterion
209
210## License
211
212This project is licensed under the [MIT license](LICENSE).
213
214### Contribution
215
216Unless you explicitly state otherwise, any contribution intentionally submitted
217for inclusion in this project by you, shall be licensed as MIT, without any
218additional terms or conditions.
219