Boxcar
A concurrent, append-only vector.
The vector provided by this crate suports concurrent get and push operations. Reads are always lock-free, as are writes except when resizing is required.
Examples
Appending an element to a vector and retrieving it:
let vec = boxcar::Vec::new();
vec.push(42);
assert_eq!(vec[0], 42);
The vector can be shared across threads with an Arc:
use std::sync::Arc;
fn main() {
let vec = Arc::new(boxcar::Vec::new());
// spawn 6 threads that append to the vec
let threads = (0..6)
.map(|i| {
let vec = vec.clone();
std::thread::spawn(move || {
vec.push(i); // push through `&Vec`
})
})
.collect::<Vec<_>>();
// wait for the threads to finish
for thread in threads {
thread.join().unwrap();
}
for i in 0..6 {
assert!(vec.iter().any(|&x| x == i));
}
}
Elements can be mutated through fine-grained locking:
use std::sync::{Mutex, Arc};
fn main() {
let vec = Arc::new(boxcar::Vec::new());
// insert an element
vec.push(Mutex::new(1));
let thread = std::thread::spawn({
let vec = vec.clone();
move || {
// mutate through the mutex
*vec[0].lock().unwrap() += 1;
}
});
thread.join().unwrap();
let x = vec[0].lock().unwrap();
assert_eq!(*x, 2);
}
Details
A concurrent vector is represented as an array of lazily allocated buckets, of sizes 1, 1, 2, 4 .. 2^63:
______________________________________
| | | | | |
| | | | | |
--------------------------------------
A buckets holds a number entries, as well as a lock to guard againt concurrent initialization:
_____________
| | | | |
| | | | |
-------------
| UNLOCKED |
-------------
An entry holds a slot for a value along with a flag indicating whether the slot is active:
_____________________
| ACTIVE | INACTIVE |
| 42 | NULL |
---------------------
Writes acquire a unique index into the vector. The bucket holding the given entry is calculated using the leading zeros instruction. If the bucket is already initialized, the value is written to the slot, and the slot is marked as active. If the bucket has not been initialized, the thread acquires the initialization lock, allocates the bucket, and then writes the value. Note that in the general case, writes are lock-free.
Reads use the same calculation to find the entry mapped to the given index, reading the value from the slot if the flag indicates the slot is active. All reads are guaranteed to be lock-free.
Performance
Below is a benchmark in which an increasing number of elements are pushed and read from the vector by 12 threads, comparing boxcar::Vec to RwLock
:
The results show that boxcar::Vec scales very well under load, performing significantly better than lock-based solutions.
910 Feb 22, 2023
4 Jun 7, 2023
4 Nov 30, 2023
19 Dec 4, 2023
16 Mar 1, 2024
3 Apr 2, 2024
5 Oct 29, 2022
194 Jan 3, 2023
30 Dec 2, 2022
64 Oct 24, 2022
3 Oct 10, 2022
2 Sep 23, 2022
8 Feb 1, 2023
1 Jan 23, 2022
5.7k Dec 30, 2022
6.1k Dec 27, 2022
373 Dec 27, 2022
11 Jun 1, 2021
0 Dec 5, 2021
0 Dec 5, 2021
29 Dec 11, 2022
4 Nov 9, 2022
5 Aug 29, 2023
16 Oct 9, 2022
12 Nov 16, 2022
26 Jul 9, 2021
1.3k Jan 1, 2023
6 Apr 11, 2022
0 Nov 30, 2022