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::BoundedWSQ< T, LogSize > Class Template Reference

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

#include <taskflow/core/wsq.hpp>

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

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

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

Template Parameters

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

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.

Member Typedef Documentation

◆value_type

template<typename T, size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>

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

Constructor & Destructor Documentation

◆BoundedWSQ()

template<typename T, size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>

| tf::BoundedWSQ< T, LogSize >::BoundedWSQ | ( | | ) | |

| default |

constructs the queue with a given capacity

tf::BoundedWSQ<int, 10> wsq;

static_assert(wsq.capacity() == 1024);

tf::BoundedWSQ

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

Definition wsq.hpp:559

tf::BoundedWSQ::capacity

constexpr size_t capacity() const

queries the capacity of the queue

Definition wsq.hpp:879

Member Function Documentation

◆capacity()

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

◆empty()

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

tf::BoundedWSQ::empty

bool empty() const noexcept

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

Definition wsq.hpp:756

◆empty_value()

template<typename T, size_t LogSize = TF_DEFAULT_BOUNDED_TASK_QUEUE_LOG_SIZE>

| static constexpr auto tf::BoundedWSQ< T, LogSize >::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, size_t LogSize>

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

tf::BoundedWSQ::pop

value_type pop()

pops out an item from the queue

Definition wsq.hpp:822

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

◆size()

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

tf::BoundedWSQ::size

size_t size() const noexcept

queries the number of items at the time of this call

Definition wsq.hpp:764

◆steal()

template<typename T, size_t LogSize>

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

tf::BoundedWSQ::steal

value_type steal()

steals an item from the queue

Definition wsq.hpp:855

Multiple threads can simultaneously steal items from the queue.

◆try_bulk_push()

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

Returnsthe 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. 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());

tf::BoundedWSQ::try_bulk_push

size_t try_bulk_push(I &first, size_t N)

tries to insert a batch of items into the queue

Definition wsq.hpp:796

Only the owner thread can insert items into the queue.

◆try_push()

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 |

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

tf::BoundedWSQ::try_push

bool try_push(O &&item)

tries to insert an item to the queue

Definition wsq.hpp:773

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

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

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