9 releases

Uses old Rust 2015

0.3.4 Dec 19, 2017
0.3.3 Nov 15, 2017
0.3.1 Oct 25, 2017
0.2.1 Aug 24, 2017
0.1.0 Apr 9, 2017
Download history 264/week @ 2021-06-06 280/week @ 2021-06-13 132/week @ 2021-06-20 191/week @ 2021-06-27 311/week @ 2021-07-04 367/week @ 2021-07-11 416/week @ 2021-07-18 299/week @ 2021-07-25 313/week @ 2021-08-01 453/week @ 2021-08-08 231/week @ 2021-08-15 271/week @ 2021-08-22 111/week @ 2021-08-29 142/week @ 2021-09-05 548/week @ 2021-09-12 371/week @ 2021-09-19

1,009 downloads per month
Used in 3 crates

Apache-2.0/MIT

110KB
2K SLoC

Concurrent collections (deprecated)

Build Status License Cargo Documentation

NOTE: This crate is now deprecated in favor of Crossbeam. See crossbeam-epoch and crossbeam-deque.

This crate offers several collections that are designed for performance in multithreaded contexts. They can be freely shared among multiple threads running in parallel, and concurrently modified without the overhead of locking.

The following collections are available:

  • Stack: A lock-free stack.
  • deque: A lock-free work-stealing deque.

lib.rs:

Concurrent collections.

This crate offers several collections that are designed for performance in multithreaded contexts. They can be freely shared among multiple threads running in parallel, and concurrently modified without the overhead of locking.

Collections

The following collections are available:

  • Stack: A lock-free stack.
  • deque: A lock-free work-stealing deque.

Which collection should you use?

Use a Stack when:

  • You want a simple shared collection where objects can be insert and removed.
  • You want to avoid performance degradation due to locking.
  • You want the last-in first-out order of elements.

Use a deque when:

  • You want one thread inserting and removing objects, and multiple threads just removing them.
  • You don't care about the order of elements.

Garbage collection

An interesting problem concurrent collections deal with comes from the remove operation. Suppose that a thread removes an element from a lock-free map, while another thread is reading that same element at the same time. The first thread must wait until the second thread stops reading the element. Only then it is safe to destruct it.

Programming languages that come with garbage collectors solve this problem trivially. The garbage collector will destruct the removed element when no thread can hold a reference to it anymore.

This crate implements a basic garbage collection mechanism, which is based on epochs (see the epoch module). When an element gets removed from a concurrent collection, it is inserted into a pile of garbage and marked with the current epoch. Every time a thread accesses a collection, it checks the current epoch, attempts to increment it, and destructs some garbage that became so old that no thread can be referencing it anymore.

That is the general mechanism behind garbage collection, but the details are a bit more complicated. Anyhow, garbage collection is designed to be fully automatic and something users of concurrent collections don't have to worry about.

Dependencies

~50KB