#lock-free #data-structure #iterator #vector #thread-safe

voluntary-servitude

Thread-safe appendable list with lock-free iterator

5 stable releases

✓ Uses Rust 2018 edition

4.0.8 Apr 25, 2019
4.0.7 Jan 12, 2019
4.0.2 Dec 26, 2018
3.0.11 Dec 16, 2018
1.0.4 Aug 27, 2018

#92 in Data structures

Download history 28/week @ 2019-07-28 59/week @ 2019-08-04 29/week @ 2019-08-11 36/week @ 2019-08-25 61/week @ 2019-09-01 85/week @ 2019-09-08 106/week @ 2019-09-15 205/week @ 2019-09-22 60/week @ 2019-09-29 7/week @ 2019-10-06 85/week @ 2019-10-13 35/week @ 2019-10-20 57/week @ 2019-10-27

253 downloads per month

MIT/Apache

84KB
1.5K SLoC

Voluntary Servitude

Features

  • Atomic abstractions (Atomic, AtomicOption, FillOnceAtomicOption, FillOnceAtomicArc)

  • Thread-safe appendable list with a lock-free iterator (VoluntaryServitude - also called VS)

  • Serde serialization (serde-traits feature)

  • par_extend, from_par_iter rayon implementation (rayon-traits feature)

  • Logging (logs feature)

    You probably only need this if you are debugging this crate

Atomic abstractions

  • Atomic -> atomic Box<T>
  • AtomicOption -> atomic Option<Box<T>>
  • FillOnceAtomicOption -> atomic Option<Box<T>> that can give references (ideal for iterators)
  • FillOnceAtomicArc -> atomic Option<Arc<T>> with a limited API (like FillOnceAtomicOption)

With Atomic and AtomicOption it's not safe to get a reference, you must replace the value to access it.

To safely get a reference of T you must use FillOnceAtomicOption and accept the API limitations (initially None but can be filled once).

For a safe AtomicArc you must use some data-structure from arc-swap, RwLock/Mutex from parking_lot (or std, which is slower but the standard) or FillOnceAtomicArc and accept the limited API (2018).

Licenses

MIT and Apache-2.0

VoluntaryServitude Examples

Single thread

use voluntary_servitude::vs;

fn main() {
    let (a, b, c) = (0usize, 1usize, 2usize);
    // VS alias to VoluntaryServitude
    // vs! alias to voluntary_servitude! (and operates like vec!)
    let list = vs![a, b, c];
    assert_eq!(list.iter().collect::<Vec<_>>(), vec![&a, &b, &c]);

    // Current VS's length
    // Be careful with race conditions since the value, when used, may not be true anymore
    assert_eq!(list.len(), 3);

    // The 'iter' method makes a lock-free iterator (Iter)
    for (index, element) in list.iter().enumerate() {
        assert_eq!(index, *element);
    }

    // You can get the current iteration index
    // iter.index() == iter.len() means iteration ended (iter.next() == None)
    let mut iter = &mut list.iter();
    assert_eq!(iter.index(), 0);
    assert_eq!(iter.next(), Some(&0));
    assert_eq!(iter.index(), 1);

    // List can also be cleared (but current iterators are not affected)
    list.clear();

    assert_eq!(iter.len(), 3);
    assert_eq!(list.len(), 0);
    assert_eq!(list.iter().len(), 0);
    assert_eq!((&mut list.iter()).next(), None);

    println!("Single thread example ended without errors");
}

Multi-producer, multi-consumer

use voluntary_servitude::vs;
use std::{sync::Arc, thread::spawn};

const CONSUMERS: usize = 8;
const PRODUCERS: usize = 4;
const ELEMENTS: usize = 10_000_000;

fn main() {
    let list = Arc::new(vs![]);
    let mut handlers = vec![];

    // Creates producer threads to insert 10k elements
    for _ in 0..PRODUCERS {
        let l = Arc::clone(&list);
        handlers.push(spawn(move || {
            let _ = (0..ELEMENTS).map(|i| l.append(i)).count();
        }));
    }

    // Creates consumer threads to print number of elements
    // Until all of them are inserted
    for _ in 0..CONSUMERS {
        const TOTAL: usize = PRODUCERS * ELEMENTS;
        let consumer = Arc::clone(&list);
        handlers.push(spawn(move || loop {
            let count = consumer.iter().count();
            println!("{} elements", count);
            if count >= TOTAL { break };
        }));
    }

    // Join threads
    for handler in handlers.into_iter() {
        handler.join().expect("Failed to join thread");
    }

    println!("Multi-thread example ended without errors");
}

Dependencies

~0.9–1.4MB
~26K SLoC