| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Member Functions | List of all members
tf::UnboundedWSQ< T > Class Template Reference

class to create a lock-free unbounded work-stealing queue More...

`#include <taskflow/core/wsq.hpp>`

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

## Public Member Functions
| UnboundedWSQ (int64_t LogSize=TF_DEFAULT_UNBOUNDED_TASK_QUEUE_LOG_SIZE)
| constructs the queue with the given size in the base-2 logarithm
| ~UnboundedWSQ ()
| destructs the queue
bool | empty () const noexcept
| queries if the queue is empty at the time of this call
size_t | size () const noexcept
| queries the number of items at the time of this call
size_t | capacity () const noexcept
| queries the capacity of the queue
void | 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 queue
value_type | pop ()
| pops out an item from the queue
value_type | steal ()
| steals an item from the queue
value_type | steal_with_feedback (size_t &num_empty_steals)
| attempts to steal a task with feedback on the emptiness of the queue

## Static Public Member Functions
static constexpr auto | empty_value ()
| returns the empty sentinel value for the queue element type

## Detailed Description

template<typename T>
class tf::UnboundedWSQ< T >

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

Template Parameters

  T | data type (must be a pointer type)

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.

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.

## Member Typedef Documentation

## ◆ value_type

template<typename T>

using tf::UnboundedWSQ< T >::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.

## Constructor & Destructor Documentation

## ◆ UnboundedWSQ()

template<typename T>

tf::UnboundedWSQ< T >::UnboundedWSQ | ( | int64_t | LogSize = TF_DEFAULT_UNBOUNDED_TASK_QUEUE_LOG_SIZE | ) |
| explicit

constructs the queue with the given size in the base-2 logarithm

Parameters

  LogSize | the base-2 logarithm of the queue size

tf::UnboundedWSQ<int> wsq(10);
assert(wsq.capacity() == 1024);
tf::UnboundedWSQ
class to create a lock-free unbounded work-stealing queue
Definition wsq.hpp:67

## Member Function Documentation

## ◆ bulk_push()

template<typename T>
template<typename I>

void tf::UnboundedWSQ< T >::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`

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.

## ◆ capacity()

template<typename T>

size_t tf::UnboundedWSQ< T >::capacity | ( |  | ) | const
| noexcept

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 resizing
wsq.push(i);
}
assert(wsq.capacity() == 2048);
assert(wsq.size() == 1025);

## ◆ empty()

template<typename T>

bool tf::UnboundedWSQ< T >::empty | ( |  | ) | const
| noexcept

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);

## ◆ empty_value()

template<typename T>

static constexpr auto tf::UnboundedWSQ< T >::empty_value | ( |  | ) |
| inline static constexpr

returns the empty sentinel value for the queue element type

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.

Returns
  an empty `value_type` representing the absence of an element.

## ◆ pop()

template<typename T>

UnboundedWSQ< T >::value_type tf::UnboundedWSQ< T >::pop | ( |  | ) |

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.

## ◆ push()

template<typename T>

void tf::UnboundedWSQ< T >::push | ( | T | item | ) |

inserts an item to the queue

Parameters

  item | the item to push to the queue

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 resizing
wsq.push(i);
}
assert(wsq.capacity() == 2048);
assert(wsq.size() == 1025);

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

## ◆ size()

template<typename T>

size_t tf::UnboundedWSQ< T >::size | ( |  | ) | const
| noexcept

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);

## ◆ steal()

template<typename T>

UnboundedWSQ< T >::value_type tf::UnboundedWSQ< T >::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::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.

## ◆ steal_with_feedback()

template<typename T>

UnboundedWSQ< T >::value_type tf::UnboundedWSQ< T >::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::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.

The documentation for this class was generated from the following file:

- taskflow/core/wsq.hpp