template<typename T, size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>
tf::BoundedWSQ class

class to create a lock-free bounded work-stealing queue

Template parameters
T data type
LogSize the base-2 logarithm of the queue size

This class implements the work-stealing queue described in the paper, Correct and Efficient Work-Stealing for Weak Memory Models.

A work-stealing queue supports a single owner thread that performs push and pop operations, while multiple concurrent thief threads may steal tasks from the opposite end of the queue. The implementation is designed to operate correctly under weak memory models and uses atomic operations with carefully chosen memory orderings to ensure correctness and scalability.

BoundedWSQ Owner Owner Thread (single) Push try_push() try_bulk_push() Owner->Push Pop pop() Owner->Pop Thieves Thief Threads (multiple) Steal steal() Thieves->Steal Queue Head (Top) steal index Tasks Buffer [Fixed Capacity = 2^LogSize] Tail (Bottom) push / pop index Push->Queue:tail append at bottom Pop->Queue:tail remove from bottom Steal->Queue:head remove from top

The queue has a fixed capacity determined at construction time and does not grow dynamically. When the queue is full, push operations may fail or require external handling.

Public types

using value_type = std::conditional_t<std::is_pointer_v<T>, T, std::optional<T>>
the return type of queue operations

Public static functions

static auto empty_value() -> auto constexpr
returns the empty sentinel value for the queue element type

Constructors, destructors, conversion operators

BoundedWSQ() defaulted
constructs the queue with a given capacity
~BoundedWSQ() defaulted
destructs the queue

Public functions

auto empty() const -> bool noexcept
queries if the queue is empty at the time of this call
auto size() const -> size_t noexcept
queries the number of items at the time of this call
auto capacity() const -> size_t constexpr
queries the capacity of the queue
template<typename O>
auto try_push(O&& item) -> bool
tries to insert an item to the queue
template<typename I>
auto try_bulk_push(I first, size_t N) -> size_t
tries to insert a batch of items into the queue
auto pop() -> value_type
pops out an item from the queue
auto steal() -> value_type
steals an item from the queue
auto steal_with_feedback(size_t& num_empty_steals) -> value_type
attempts to steal a task with feedback on the emptiness of the queue

Typedef documentation

template<typename T, size_t LogSize>
using tf::BoundedWSQ<T, LogSize>::value_type = std::conditional_t<std::is_pointer_v<T>, T, std::optional<T>>

the return type of queue operations

value_type represents the type returned by pop and steal operations. For pointer element types T, it is T itself and uses nullptr to indicate an empty result. For non-pointer types, it is std::optional<T>, where std::nullopt denotes the absence of a value.

static_assert(std::is_same_v<tf::UnboundedWSQ<int>::value_type, std::optional<int>>);
static_assert(std::is_same_v<tf::UnboundedWSQ<int*>::value_type, nullptr);

This design avoids the overhead of std::optional for pointer types while providing a uniform empty-result semantics.

Function documentation

template<typename T, size_t LogSize>
static auto tf::BoundedWSQ<T, LogSize>::empty_value() constexpr

returns the empty sentinel value for the queue element type

Returns an empty value_type representing the absence of an element.

This function provides a type-appropriate empty value used to indicate that a pop or steal operation failed. For pointer types, the empty value is nullptr of type T; for non-pointer types, it is std::nullopt of type std::optional<T>.

The function is implemented as a constexpr helper to avoid additional storage, runtime overhead, or code duplication across queue operations.

template<typename T, size_t LogSize>
tf::BoundedWSQ<T, LogSize>::BoundedWSQ() defaulted

constructs the queue with a given capacity

tf::BoundedWSQ<int, 10> wsq;  
static_assert(wsq.capacity() == 1024);

template<typename T, size_t LogSize>
bool tf::BoundedWSQ<T, LogSize>::empty() const noexcept

queries if the queue is empty at the time of this call

tf::BoundedWSQ<int, 10> wsq;  
assert(wsq.empty() == true);
wsq.push(1);
assert(wsq.empty() == false);

template<typename T, size_t LogSize>
size_t tf::BoundedWSQ<T, LogSize>::size() const noexcept

queries the number of items at the time of this call

tf::BoundedWSQ<int, 10> wsq;  
assert(wsq.size() == 0);
wsq.push(1);
assert(wsq.size() == 1);

template<typename T, size_t LogSize>
size_t tf::BoundedWSQ<T, LogSize>::capacity() const constexpr

queries the capacity of the queue

The capacity of a bounded work-stealing queue is decided at compile time.

tf::BoundedWSQ<int, 10> wsq;
static_assert(wsq.capacity() == 1024);

template<typename T, size_t LogSize> template<typename O>
bool tf::BoundedWSQ<T, LogSize>::try_push(O&& item)

tries to insert an item to the queue

Template parameters
O data type
Parameters
item the item to perfect-forward to the queue
Returns true if the insertion succeed or false (queue is full)

This method attempts to push one item into the queue. If the operation succeed, it returns true or false otherwise.

tf::BoundedWSQ<int, 10> wsq;  
static_assert(wsq.capacity() == 1024);
for(int i=0; i<1024; i++) {
  assert(wsq.try_push(i) == true);
}
assert(wsq.size() == 1024);
assert(wsq.try_push(0) == false);

Only the owner thread can insert an item to the queue.

template<typename T, size_t LogSize> template<typename I>
size_t tf::BoundedWSQ<T, LogSize>::try_bulk_push(I first, size_t N)

tries to insert a batch of items into the queue

Template parameters
I input iterator type
Parameters
first iterator to the first item in the batch
N number of items to insert beginning at first
Returns the number of items successfully inserted

This method attempts to push up to N items from the range [first, first + N) into the queue. Insertion stops early if the queue becomes full. Bulk insertion is often faster than inserting elements one by one because it requires fewer atomic operations.

tf::BoundedWSQ<int, 10> wsq;  
static_assert(wsq.capacity() == 1024);
std::vector<int> vec(1030, 1);
assert(wsq.try_bulk_push(vec.data(), vec.size()) == wsq.capacity());
assert(wsq.try_bulk_push(vec.data(), vec.size()) == 0);

Only the owner thread can insert items into the queue.

template<typename T, size_t LogSize>
value_type tf::BoundedWSQ<T, LogSize>::pop()

pops out an item from the queue

The method pops an item out of the queue based on a last-in-first-out (LIFO) order. The return can be an empty_value() if this operation failed (empty queue).

tf::BoundedWSQ<int, 10> wsq;  
wsq.push(1);
wsq.push(2);
wsq.push(3);
assert(wsq.pop().value() = 3);
assert(wsq.pop().value() = 2);
assert(wsq.pop().value() = 1);
assert(wsq.pop() == std::nullopt);

Only the owner thread can pop out an item from the queue.

template<typename T, size_t LogSize>
value_type tf::BoundedWSQ<T, LogSize>::steal()

steals an item from the queue

Any threads can try to steal an item from the queue. The return can be an empty_value() if this operation failed. The elements stolen from the queue follow a first-in-first-out (FIFO) order.

tf::BoundedWSQ<int, 10> wsq;  
wsq.push(1);
wsq.push(2);
wsq.push(3);
assert(wsq.steal().value() = 1);
assert(wsq.steal().value() = 2);
assert(wsq.steal().value() = 3);
assert(wsq.steal() == std::nullopt);

Multiple threads can simultaneously steal items from the queue.

template<typename T, size_t LogSize>
value_type tf::BoundedWSQ<T, LogSize>::steal_with_feedback(size_t& num_empty_steals)

attempts to steal a task with feedback on the emptiness of the queue

Parameters
num_empty_steals a reference to a counter tracking consecutive empty steal attempts

This function tries to steal a task from the queue. If the steal attempt is successful, the stolen task is returned. Additionally, if the queue is empty, the provided counter num_empty_steals is incremented; otherwise, num_empty_steals is reset to zero. The return can be an empty_value() if this operation failed. The elements stolen from the queue follow a first-in-first-out (FIFO) order.

tf::BoundedWSQ<int, 10> wsq;  
size_t num_empty_steals(0);
assert(wsq.steal_with_feedback(num_empty_steals) == std::nullopt);
assert(wsq.steal_with_feedback(num_empty_steals) == std::nullopt);
assert(wsq.steal_with_feedback(num_empty_steals) == std::nullopt);
assert(num_empty_steals == 3);
wsq.push(1);
wsq.push(2);
wsq.push(3);
assert(wsq.steal_with_feedback(num_empty_steals).value() = 1);
assert(num_empty_steals == 0);  // successful steal will reset the feedback to 0

Multiple threads can simultaneously steal items from the queue.