Work stealing queue#

A stand-alone, production-quality implementation of the Chase-Lev lock-free single-producer multiple-consumer 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 both CopyConstructible and CopyAssignable.

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 and std::default_initializable.

Helpers#

enum class lf::ext::err : int#

Error codes for deque ‘s steal() operation.

Values:

enumerator none#: The steal() operation succeeded.

enumerator lost#: Lost the steal() race hence, the steal() operation failed.

enumerator empty#: The deque is empty and hence, the steal() operation failed.

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 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 .

Public Members

err code#: The error code of the steal() operation.

T val#: The value stolen from the deque, Only valid if code == err::stolen.

template<typename T> struct return_nullopt#

A functor that returns std::nullopt.

Public Static Functions

static inline constexpr auto operator()() noexcept -> std::optional<T>#: 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() and push() 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 Types

using value_type = 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 null std::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.

constexpr auto steal() noexcept -> steal_t<T>#

Steal an item from the deque.

Any threads can try to steal an item from the deque. This operation can fail if the deque is empty or if another thread simultaneously stole an item from the deque.