chase_lev_deque.h File Reference

#include <atomic>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <new>
#include <type_traits>
#include <utility>
#include <dispenso/platform.h>
#include <dispenso/tsan_annotations.h>

Go to the source code of this file.

Classes
class	dispenso::ChaseLevDeque< T, Capacity >
	A lock-free SPMC bounded work-stealing deque. More...

Detailed Description

A lock-free single-producer / multi-consumer (SPMC) work-stealing deque.

This is the bounded variant of the Chase-Lev deque (Chase & Lev, 2005), the standard data structure backing fork-join work-stealing schedulers (e.g., TBB, Cilk). The owning thread pushes and pops at the "bottom" end with no atomic CAS on the fast path; other threads steal from the "top" end via CAS. Owner pop is LIFO (newest-first) for cache locality; steal is FIFO (oldest-first) to take broad chunks of work.

Note

Only the owning thread may push or pop. Any thread may steal.

See also

"Dynamic Circular Work-Stealing Deque", Chase & Lev, SPAA 2005.

"Correct and Efficient Work-Stealing for Weak Memory Models", Lê et al., PPoPP 2013.

Definition in file chase_lev_deque.h.