template<typename T, unsigned TF_MAX_PRIORITY = static_cast<unsigned>(TaskPriority:: MAX)>
TaskQueue class
class to create a lock-free unbounded single-producer multiple-consumer queue
Template parameters | |
---|---|
T | data type (must be a pointer type) |
TF_MAX_PRIORITY | maximum level of the priority |
This class implements the work-stealing queue described in the paper, Correct and Efficient Work-Stealing for Weak Memory Models, and extends it to include priority.
Only the queue owner can perform pop and push operations, while others can steal data from the queue simultaneously. Priority starts from zero (highest priority) to the template value TF_MAX_PRIORITY-1
(lowest priority). All operations are associated with priority values to indicate the corresponding queues to which an operation is applied.
The default template value, TF_MAX_PRIORITY
, is TaskPriority::
which applies only three priority levels to the task queue.
auto [A, B, C, D, E] = taskflow.emplace( [] () { }, [&] () { std::cout << "Task B: " << counter++ << '\n'; // 0 }, [&] () { std::cout << "Task C: " << counter++ << '\n'; // 2 }, [&] () { std::cout << "Task D: " << counter++ << '\n'; // 1 }, [] () { } ); A.precede(B, C, D); E.succeed(B, C, D); B.priority(tf::TaskPriority::HIGH); C.priority(tf::TaskPriority::LOW); D.priority(tf::TaskPriority::NORMAL); executor.run(taskflow).wait();
In the above example, we have a task graph of five tasks, A
, B
, C
, D
, and E
, in which B
, C
, and D
can run in simultaneously when A
finishes. Since we only uses one worker thread in the executor, we can deterministically run B
first, then D
, and C
in order of their priority values. The output is as follows:
Task B: 0 Task D: 1 Task C: 2
Constructors, destructors, conversion operators
- TaskQueue(int64_t capacity = 512) explicit
- constructs the queue with a given capacity
- ~TaskQueue()
- destructs the queue
Public functions
- auto empty() const -> bool noexcept
- queries if the queue is empty at the time of this call
- auto empty(unsigned priority) const -> bool noexcept
- queries if the queue is empty at a specific priority value
- auto size() const -> size_t noexcept
- queries the number of items at the time of this call
- auto size(unsigned priority) const -> size_t noexcept
- queries the number of items with the given priority at the time of this call
- auto capacity() const -> int64_t noexcept
- queries the capacity of the queue
- auto capacity(unsigned priority) const -> int64_t noexcept
- queries the capacity of the queue at a specific priority value
- auto push(T item, unsigned priority) -> TF_FORCE_INLINE void
- inserts an item to the queue
- auto pop() -> T
- pops out an item from the queue
- auto pop(unsigned priority) -> TF_FORCE_INLINE T
- pops out an item with a specific priority value from the queue
- auto steal() -> T
- steals an item from the queue
- auto steal(unsigned priority) -> T
- steals an item with a specific priority value from the queue
Function documentation
template<typename T, unsigned TF_MAX_PRIORITY>
tf:: TaskQueue<T, TF_MAX_PRIORITY>:: TaskQueue(int64_t capacity = 512) explicit
constructs the queue with a given capacity
Parameters | |
---|---|
capacity | the capacity of the queue (must be power of 2) |
template<typename T, unsigned TF_MAX_PRIORITY>
TF_FORCE_INLINE void tf:: TaskQueue<T, TF_MAX_PRIORITY>:: push(T item,
unsigned priority)
inserts an item to the queue
Parameters | |
---|---|
item | the item to push to the queue |
priority | priority value of the item to push (default = 0) |
Only the owner thread can insert an item to the queue. The operation can trigger the queue to resize its capacity if more space is required.
template<typename T, unsigned TF_MAX_PRIORITY>
T tf:: TaskQueue<T, TF_MAX_PRIORITY>:: pop()
pops out an item from the queue
Only the owner thread can pop out an item from the queue. The return can be a nullptr
if this operation failed (empty queue).
template<typename T, unsigned TF_MAX_PRIORITY>
TF_FORCE_INLINE T tf:: TaskQueue<T, TF_MAX_PRIORITY>:: pop(unsigned priority)
pops out an item with a specific priority value from the queue
Parameters | |
---|---|
priority | priority of the item to pop |
Only the owner thread can pop out an item from the queue. The return can be a nullptr
if this operation failed (empty queue).
template<typename T, unsigned TF_MAX_PRIORITY>
T tf:: TaskQueue<T, TF_MAX_PRIORITY>:: steal()
steals an item from the queue
Any threads can try to steal an item from the queue. The return can be a nullptr
if this operation failed (not necessary empty).
template<typename T, unsigned TF_MAX_PRIORITY>
T tf:: TaskQueue<T, TF_MAX_PRIORITY>:: steal(unsigned priority)
steals an item with a specific priority value from the queue
Parameters | |
---|---|
priority | priority of the item to steal |
Any threads can try to steal an item from the queue. The return can be a nullptr
if this operation failed (not necessary empty).