Work stealing queue¶
A production-quality implementation of the Chase-Lev lock-free SPMC deque.
Concepts¶
-
template<typename T>
concept atomicable¶ - #include <libfork/core/ext/deque.hpp>
Verify a type is suitable for use with
std::atomic
This requires a
TriviallyCopyable
type satisfying bothCopyConstructible
andCopyAssignable
.
-
template<typename T>
concept lock_free¶ - #include <libfork/core/ext/deque.hpp>
A concept that verifies a type is lock-free when used with
std::atomic
.
-
template<typename T>
concept dequeable¶ - #include <libfork/core/ext/deque.hpp>
Test is a type is suitable for use with
lf::deque
.This requires it to be
lf::ext::lock_free
andstd::default_initializable
.
Helpers¶
-
enum class lf::ext::err : int¶
Error codes for
deque
‘ssteal()
operation.Values:
-
enumerator none¶
The
steal()
operation succeeded.
-
enumerator lost¶
Lost the
steal()
race hence, thesteal()
operation failed.
-
enumerator empty¶
The deque is empty and hence, the
steal()
operation failed.
-
enumerator none¶
-
template<typename T>
struct steal_t¶ The return type of a
lf::deque
steal()
operation.This type is suitable for structured bindings. We return a custom type instead of a
std::optional
to allow for more information to be returned as to why a steal may fail.Public Functions
-
inline explicit constexpr operator bool() const noexcept¶
Check if the operation succeeded.
-
inline constexpr auto operator*() const noexcept -> T const&¶
Get the value like
std::optional
.Requires
code == err::none
.
-
inline constexpr auto operator*() noexcept -> T&¶
Get the value like
std::optional
.Requires
code == err::none
.
-
inline explicit constexpr operator bool() const noexcept¶
-
template<typename T>
struct return_nullopt¶ A functor that returns
std::nullopt
.
WSQ¶
-
template<dequeable T>
class deque : private lf::impl::immovable<deque<T>>¶ An unbounded lock-free single-producer multiple-consumer work-stealing deque.
Implements the “Chase-Lev” deque described in the papers, “Dynamic Circular Work-Stealing deque” and “Correct and Efficient Work-Stealing for Weak Memory Models”.
Only the deque owner can perform
pop()
andpush()
operations where the deque behaves like a LIFO stack. Others can (only)steal()
data from the deque, they see a FIFO deque. All threads must have finished using the deque before it is destructed.Example:
#include <atomic> // for atomic #include <optional> // for optional #include <thread> // for thread #include <vector> // for vector #include "libfork/core.hpp" // for deque, err, steal_t, return_nullopt namespace { auto example() -> int { // Work-stealing deque of ints lf::deque<int> deque; constexpr int num_items = 10000; // One thread can push and pop items from one end (like a stack) std::thread owner([&]() { for (int i = 0; i < num_items; ++i) { deque.push(i); } while (std::optional item = deque.pop()) { // Do something with items... } }); // While multiple (any) threads can steal items from the other end std::thread thief([&]() { while (!deque.empty()) { if (auto item = deque.steal()) { // Do something with item... } } }); owner.join(); thief.join(); return 0; } } // namespace
- Template Parameters:
T – The type of the elements in the deque.
Public Functions
-
inline constexpr deque()¶
Construct a new empty deque object.
-
explicit constexpr deque(std::ptrdiff_t cap)¶
Construct a new empty deque object.
- Parameters:
cap – The capacity of the deque (must be a power of 2).
-
constexpr ~deque() noexcept¶
Destroy the deque object.
All threads must have finished using the deque before it is destructed.
-
constexpr auto capacity() const noexcept -> ptrdiff_t¶
Get the capacity of the deque.
-
constexpr auto empty() const noexcept -> bool¶
Check if the deque is empty.
-
template<std::invocable F = return_nullopt<T>>
constexpr auto pop(F &&when_empty = {}) noexcept(std::is_nothrow_invocable_v<F>) -> std::invoke_result_t<F>¶ Pop an item from the deque.
Only the owner thread can pop out an item from the deque. If the buffer is empty calls
when_empty
and returns the result. By default,when_empty
is a no-op that returns a nullstd::optional<T>
.
-
constexpr void push(T const &val)¶
Push an item into the deque.
Only the owner thread can insert an item into the deque. This operation can trigger the deque to resize if more space is required. This may throw if an allocation is required and then fails.
- Parameters:
val – Value to add to the deque.
-
constexpr auto size() const noexcept -> std::size_t¶
Get the number of elements in the deque.
-
constexpr auto ssize() const noexcept -> ptrdiff_t¶
Get the number of elements in the deque as a signed integer.