Taskflow: A General - Taskflow

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

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

Public Member Functions

Static Public Member Functions

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.

Embedded content

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>

| 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:105

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

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

| inlinestaticconstexpr |

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.

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

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

taskflow/core/wsq.hpp
tf
UnboundedWSQ
Maintained by Dr. Tsung-Wei Huang — Generated by 1.13.1