Skip to content

2018-03-14-circbuf.md

Latest commit

 

History

History
129 lines (88 loc) · 4.56 KB

2018-03-14-circbuf.md

File metadata and controls

129 lines (88 loc) · 4.56 KB

Summary

Introduce crate crossbeam-circbuf which provides SPSC and SPMC channels based on concurrent circular buffer. Here is a prototype implementation.

Motivation

Crossbeam already has a work-stealing deque for being used in task schedulers, which is successfully deployed in Rayon and Tokio. However, Tokio actually doesn't use the full functionality of deque, leaving Deque::pop() unused. This is because Tokio targets on IO and should be fair in executing tasks, while Deque::pop() will pop the most recent task repeatedly.

Basically, crossbeam-circbuf is the result of removing Deque::pop() from crossbeam-deque. Since the synchronization between Deque::pop() and Stealer::steal() is the most intricate and complex part of a work-stealing deque, removing Deque::pop() from the work-stealing deque will greatly simplify the code base and make it faster.

It is worth noting that Go's scheduler also uses circular buffer, basically.

Detailed design

Changes from deque

Besides removing pop(), we renamed existing structs and methods and added a few methods to circular buffer:

Name changes

  • Deque renamed into CircBuf
  • Stealer renamed into Receiver
  • Deque::push() renamed into CircBuf::send()
  • Deque::steal(), Stealer::steal() renamed into CircBuf::try_recv(), Receiver::try_recv(). Now they return Result<Some<T>, RecvError>, where Ok(Some(v)) means the value v is returned, Ok(None) means the circular buffer is empty, and Err(RecvError::Retry) means you lost a race and may want to retry.

New methods

  • CircBuf::recv(), Receiver::recv(): retries to receive a value until get a value or check that the circular buffer is empty.
  • Receiver::recv_exclusive(): receives a value, assuming that there are no concurrent receiving methods invocations. It's necessary for providing efficient SPSC receivers.

SPSC and SPMC channels

We provide SPSC and SPMC channels as a thin wrapper around circular buffer. Their API looks like:

use concurrent_circbuf::spsc;
use std::thread;

// Since there's only one receiver, `spsc::new()` just creates it.
let (tx, rx) = spsc::new::<char>();

tx.send('a');
tx.send('b');
tx.send('c');

assert_eq!(rx.recv(), Some('a'));
drop(tx);

thread::spawn(move || {
    assert_eq!(rx.recv(), Some('b'));
    assert_ne!(rx.try_recv(), Ok(None)); // it's not empty
}).join().unwrap();
use concurrent_circbuf::spmc::{Channel, Receiver};
use std::thread;

// Since there can be multiple receivers, `Channel::new()` creates an SPMC channel, and the channel
// can create multiple receivers.
let c = Channel::<char>::new();
let r = c.receiver();

c.send('a');
c.send('b');
c.send('c');

assert_eq!(c.recv(), Some('a'));
drop(c);

thread::spawn(move || {
    assert_eq!(r.recv(), Some('b'));
    assert_ne!(r.try_recv(), Ok(None)); // Ok(Some('c')) or Err(RecvError::Retry)
}).join().unwrap();

Performance

We benchmarked the performance of SPSC and SPMC using crossbeam-channel's benchmark.

Results on an Intel(R) Xeon(R) CPU E5-2620 v3 @ 2.40GHz (12 cores, 24 hw-threads) running Linux 4.11.12-1-MANJARO:

Graphs

It says crossbeam-circbuf outperforms not only crossbeam-deque but also crossbeam-channel, crossbeam::sync::SegQueue, and std::sync::mpsc for unbounded SPSC and SPMC scenarios.

Drawbacks and Alternatives

We are creating even another crate. Is it worth? Maybe you can use crossbeam-deque in spite of crossbeam-circbuf's performance advantages.

API distinguishes recv() and try_recv(), the only difference being that recv() always succeeds in returning value or checking the emptiness, while try_recv() may lose a race and bail out. While they have different performance characteristics (recv() being ~20% faster than spinning try_recv() in benchmark), is it actually worth distinguishing?

Unresolved questions

Not that I'm aware of now.