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