Template Class concurrent_dequeue

Class Documentation

template<typename T>
class concore::v1::concurrent_dequeue

Concurrent double-ended queue implementation, for a small number of elements.

This will try to preallocate a vector with enough elements to cover the most common cases. Operations on the concurrent queue when we have few elements are fast: we only make atomic operations, no memory allocation. We only use spin mutexes in this case.

Template Parameters

  • T: The type of elements to store

If we have too many elements in the queue, we switch to a slower implementation that can grow to a very large number of elements. For this we use regular mutexes.

Note 1: when switching between fast and slow, the FIFO ordering of the queue is lost.

Note 2: for efficiency reasons, the element size should be at least as a cache line (otherwise we can have false sharing when accessing adjacent elements)

Note 3: we expect very-low contention on the front of the queue, and some contention at the end of the queue. And of course, there will be more contention when the queue is empty or close to empty.

Note 4: we expect contention over the atomic that stores the begin/end position in the fast queue

The intent of this queue is to hold tasks in the task system. There, we typically add any enqueued tasks to the end of the queue. The tasks that are spawned while working on some task are pushed to the front of the queue. The popping of the tasks is typically done on the front of the queue, but when stealing tasks, popping is done from the back of the queue trying to maximize locality for nearby tasks.

Public Types

using value_type = T

The value type stored in the concurrent dequeue.

Public Functions

concurrent_dequeue(size_t expected_size)

Constructs a new instance of the queue, with the given preallocated size.

If we ever add more elements in our queue than the given limit, our queue starts to become slower.

Parameters

  • expected_size: How many elements to preallocate in our fast queue.

The number of reserved elements should be bigger than the expected concurrency.

void push_back(T &&elem)

Pushes one element in the back of the queue. This is considered the default pushing operation.

void push_front(T &&elem)

Push one element to the front of the queue.

bool try_pop_front(T &elem)

Try to pop one element from the front of the queue. Returns false if the queue is empty. This is considered the default popping operation.

bool try_pop_back(T &elem)

Try to pop one element from the back of the queue. Returns false if the queue is empty.

void unsafe_clear()

Clears the queue.