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

自愿奴役

线程安全的可追加列表,带有无锁迭代器

5 个稳定版本

4.0.8 2019年4月25日
4.0.7 2019年1月12日
4.0.2 2018年12月26日
3.0.11 2018年12月16日
1.0.4 2018年8月27日

#917 in 并发

每月40次下载

MIT/Apache

85KB
1.5K SLoC

自愿奴役

功能

  • 原子抽象(AtomicAtomicOptionFillOnceAtomicOptionFillOnceAtomicArc

  • 具有无锁迭代器的线程安全可追加列表(VoluntaryServitude - 也称为 VS

  • Serde 序列化(serde-traits 功能)

  • par_extendfrom_par_iter rayon 实现(rayon-traits 功能)

  • 日志记录(logs 功能)

    你可能只需要这个功能来调试这个 crate

原子抽象

  • Atomic -> 原子 Box<T>
  • AtomicOption -> 原子 Option<Box<T>>
  • FillOnceAtomicOption -> 原子 Option<Box<T>> 可以提供引用(适用于迭代器)
  • FillOnceAtomicArc -> 原子 Option<Arc<T>> 具有有限的 API(类似于 FillOnceAtomicOption

使用 AtomicAtomicOption 时,获取引用是不安全的,您必须替换值以访问它。

要安全地获取 T 的引用,您必须使用 FillOnceAtomicOption 并接受 API 限制(最初为 None 但可以填充一次)。

要获得安全的 AtomicArc,您必须使用来自 arc-swap 的某些数据结构,来自 parking_lotRwLock/Mutex(或 std,它较慢但为标准)或 FillOnceAtomicArc 并接受有限的 API(2018)。

许可证

MITApache-2.0

VoluntaryServitude 示例

单线程

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");
}

多生产者,多消费者

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");
}

依赖

~1.2–1.9MB
~32K SLoC