docs/classtf_1_1UnboundedWSQ.html
class to create a lock-free unbounded work-stealing queue
| Template parameters |
|---|
| T |
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.
UnboundedWSQOwner Owner Thread(single) Push push()bulk_push() Owner->PushPop pop() Owner->PopThieves Thief Threads(multiple) Steal steal() Thieves->StealQueueHead (Top)steal indexDynamic Buffer(resizes as needed)Tail (Bottom)push / pop indexPush->Queue:tail insert at bottom(grow if needed) Pop->Queue:tail remove from bottom Steal->Queue:head remove from top
Unlike bounded queues, this queue automatically grows its internal storage as needed, allowing it to accommodate an arbitrary number of tasks without a fixed capacity limit.
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
UnboundedWSQ(int64_t LogSize = TF_DEFAULT_UNBOUNDED_TASK_QUEUE_LOG_SIZE) explicit constructs the queue with the given size in the base-2 logarithm~UnboundedWSQ()destructs 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 noexceptqueries the capacity of the queuevoid push(T item)inserts an item to the queue template<typename I> void bulk_push(I& first, size_t N)tries 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 the given size in the base-2 logarithm
| Parameters |
|---|
| LogSize |
tf::UnboundedWSQ\<int\> wsq(10);assert(wsq.capacity() == 1024);
queries if the queue is empty at the time of this call
tf::UnboundedWSQ\<int\> wsq(10);assert(wsq.empty() == true);wsq.push(1);assert(wsq.empty() == false);
queries the number of items at the time of this call
tf::UnboundedWSQ\<int\> wsq(10);assert(wsq.size() == 0);wsq.push(1);assert(wsq.size() == 1);
queries the capacity of the queue
tf::UnboundedWSQ\<int\> wsq(10);assert(wsq.capacity() == 1024);for(int i=0; i\<1025; i++){// insert more than 1024 ints to trigger resizingwsq.push(i);}assert(wsq.capacity() == 2048);assert(wsq.size() == 1025);
inserts an item to the queue
| Parameters |
|---|
| item |
This method pushes one item into the queue. The operation can trigger the queue to resize its capacity if more space is required.
tf::UnboundedWSQ\<int\> wsq(10);assert(wsq.capacity() == 1024);for(int i=0; i\<1025; i++) {// insert more than 1024 items to trigger resizingwsq.push(i);}assert(wsq.capacity() == 2048);assert(wsq.size() == 1025);
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 |
This method pushes up to N items from the range [first, first + N) into the queue. The operation can trigger the queue to resize its capacity if more space is required. 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::UnboundedWSQ\<int\> wsq(10);assert(wsq.capacity() == 1024);std::vector\<int\> vec(1025, 1);auto first = vec.data();wsq.bulk\_push(first, vec.size()); assert(wsq.capacity() == 2048);assert(wsq.size() == vec.size());assert(std::distance(vec.begin(), first) == 1025);
Only the owner thread can insert an item to the queue.
pops out an item from the queue
This method pops an item from the queue. If the queue is empty, empty_value() is returned. The elements popped out from the queue follow a last-in-first-out (LIFO) order.
tf::UnboundedWSQ\<int\> wsq(10);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::UnboundedWSQ\<int\> wsq(10);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::UnboundedWSQ\<int\> wsq(10);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.