docs/classtf_1_1BoundedWSQ.html
class to create a lock-free bounded work-stealing queue
| Template parameters |
|---|
| T |
| LogSize |
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.
BoundedWSQOwner Owner Thread(single) Push try_push()try_bulk_push() Owner->PushPop pop() Owner->PopThieves Thief Threads(multiple) Steal steal() Thieves->StealQueueHead (Top)steal indexTasks Buffer[Fixed Capacity = 2^LogSize]Tail (Bottom)push / pop indexPush->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.
using value_type = std::conditional_t<std::is_pointer_v<T>, T, std::optional<T>> the return type of queue operations
static auto empty_value() -> auto constexprreturns the empty sentinel value for the queue element type
BoundedWSQ() defaultedconstructs the queue with a given capacity~BoundedWSQ() defaulteddestructs the queue
auto empty() const -> bool noexceptqueries if the queue is empty at the time of this callauto size() const -> size_t noexceptqueries the number of items at the time of this callauto capacity() const -> size_t constexprqueries the capacity of the queue template<typename O> auto try_push(O&& item) -> booltries to insert an item to the queue template<typename I> auto try_bulk_push(I& first, size_t N) -> size_ttries to insert a batch of items into the queueauto pop() -> value_typepops out an item from the queueauto steal() -> value_typesteals an item from the queueauto steal_with_feedback(size_t& num_empty_steals) -> value_typeattempts to steal a task with feedback on the emptiness of the queue
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.
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.
constructs the queue with a given capacity
tf::BoundedWSQ\<int, 10\> wsq;static\_assert(wsq.capacity() == 1024);
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);
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);
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);
tries to insert an item to the queue
| Template parameters |
|---|
| O |
| Parameters |
| --- |
| item |
| Returns |
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.
tries to insert a batch of items into the queue
| Template parameters |
|---|
| I |
| Parameters |
| --- |
| first |
| N |
| Returns |
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. The iterator first is updated in place and will point to the next uninserted element after the call.
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);auto first = vec.begin();assert(wsq.try\_bulk\_push(first, vec.size()) == wsq.capacity());assert(std::distance(vec.begin(), first) == wsq.capacity());
Only the owner thread can insert items into the queue.
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.
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.
attempts to steal a task with feedback on the emptiness of the queue
| Parameters |
|---|
| num_empty_steals |
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.