Multi-producer multi-consumer queue with optional blocking
authorNathan Bronson <ngbronson@fb.com>
Fri, 28 Jun 2013 20:42:14 +0000 (13:42 -0700)
committerSara Golemon <sgolemon@fb.com>
Mon, 1 Jul 2013 19:57:43 +0000 (12:57 -0700)
commit8b26063954ea3aec10781efab5a78f0df6670d76
tree1e9cecb8ca9c2d22a99c98416fb206648ad06e15
parent78f3142f51b4fd555664936701f49da7dea86b7e
Multi-producer multi-consumer queue with optional blocking

Summary:
MPMCQueue<T> is a high-performance bounded concurrent queue that
supports multiple producers, multiple consumers, and optional blocking.
The queue has a fixed capacity, for which all memory will be allocated
up front.  The bulk of the work of enqueuing and dequeuing can be
performed in parallel.

To make an MPMCQueue<T>, T must satisfy either of two conditions:
- it has been tagged FOLLY_ASSUME_FBVECTOR_COMPATIBLE; or
- both the constructor used during enqueue and the move operator are
marked noexcept.

This diff extracts the generic component from tao/queues/ConcurrentQueue
and renames identifiers to match those of existing folly queues.
It also includes an extraction of Futex, which wraps the futex syscall,
and DeterministicScheduler, which allows for deterministic exploration
of thread interleavings for components built from std::atomic and Futex.

Test Plan: new unit tests

Reviewed By: tudorb@fb.com

FB internal diff: D866566
folly/MPMCQueue.h [new file with mode: 0644]
folly/detail/Futex.h [new file with mode: 0644]
folly/test/DeterministicSchedule.cpp [new file with mode: 0644]
folly/test/DeterministicSchedule.h [new file with mode: 0644]
folly/test/DeterministicScheduleTest.cpp [new file with mode: 0644]
folly/test/FutexTest.cpp [new file with mode: 0644]
folly/test/MPMCQueueTest.cpp [new file with mode: 0644]