Template Class StaticStealableDequeue

• Defined in File static_stealable_dequeue.hpp

Class Documentation

template<typename Type, uint32_t MaxElements>
class ripple::StaticStealableDequeue

The StaticStealableDequeue is a fixed-size, concurrent, lock-free stealable double-ended queue implementation.

It is designed for a single thread to push and pop onto and from the bottom of the queue, respectively, and any number of threads to steal from the top of the queue.

The API provides by try_push, push, pop, steal, and size.

The push function will push an object onto the queue regardless of whether the queue is full or not, and since the queue is circular, will therefore overwrite the oldest object which was pushed onto the queue. It is faster than try_push, but must only be used when it’s known that the queue is not full. In debug mode, push will notify if an overwrite happens.

The try_push function calls push if the queue is not full.

pop and steal will return a nullopt if the queue is empty, or if another thread stole the last element before they got to it. Otherwise they will return a pointer to the object.

To provide an API that does not easily introduce bugs, all returned objects are copies, thus the queue is not suitable for large objects. This is because providing a reference or pointer to an element introduces a potential race between the use of that element and a push to the queue.

Consider if the queue is full. Calling try_push returns false, as one would expect, and calling steal returns the oldest element (say at index 0) then increments top (to 1). Another call to try_push then succeeds because the queue is not at capacity, but it creates the new element in the same memory location as the element just stolen. Therefore, if a pointer is returned, there is a race between the stealing thread to use the element pointed to, and the pushing thread overwriting the memory. Such a scenario is too tricky to use correctly to include in the API. Therefore, benchmark the queue for the required data type, or run in debug mode to determine a good size for the queue. This queue is not dynamically sized to improve performance.

Also note that due to the multi-threaded nature of the queue, a call to size only returns the size of the queue at that point in time, and it’s possible that other threads may have stolen from the queue between the time at which size was called and then next operation.

This imlementation is based on the original paper by Chase and Lev:

Dynamic circular work-stealing deque

without the dynamic resizing.

Note: This class is aligned to avoid false sharing. Even though the objects in the queue are stored on the stack, it’s possible that the last cache line isn’t full, so we need to avoid other members of the class being put on the cacheline.

struct alignas(avoid_false_sharing_size) SomeClass {
  StaticStealableQueue<SomeType, 1024> queue;
};

Template Parameters

• Type: The type of the data in the queue.

• MaxElements: The maximum number of elements for the queue.

Public Types

using Size = uint32_t

Defines the size type of for the indices.

using Atomic = std::atomic<Size>

Defines the atomic type used for the index pointers.

using Element = Type

Defines the type of the elements in the queue.

using Optional = std::optional<Element>

Defines an optional typeto use when returning value types.

using Container = std::vector<Element>

Defines the type of container used to store the queue’s objects.

Public Functions

StaticStealableDequeue() = default

Default constructor for the queue.

StaticStealableDequeue(StaticStealableDequeue &&other) noexcept

Move constructor to move the other queue into this one.

Parameters

• other: The other queue to move into this one.

StaticStealableDequeue(const StaticStealableDequeue&) = delete

Copy constructor deleted.

template<typename T, pointer_enable_t<T> = 0>
auto push(T ptr) noexcept -> void

Pushes an element onto the front of the queue, when the element is an rvalue reference type.

Note

This does not check if the queue is full, and hence it will overwrite the least recently added element if the queue is full

Parameters

• args: The arguments used to construct the object.

Template Parameters

• Args: The type of the arguments for object construction.

template<typename ...Args, non_pointer_enable_t<Args...> = 0>
auto push(Args&&... args) noexcept -> void

Pushes an element onto the front of the queue, when the element is an rvalue reference type.

Note

This does not check if the queue is full, and hence it will overwrite the least recently added element if the queue is full.

Parameters

• args: The arguments used to construct the object.

Template Parameters

• Args: The type of the arguments for object construction.

template<typename ...Args>
auto try_push(Args&&... args) noexcept -> bool

Tries to push an object onto the front of the queue.

Return

true if a new object was pushed onto the queue.

Parameters

• args: The arguments used to construct the object.

Template Parameters

• Args: The type of the arguments for object construction.

auto pop() noexcept -> Optional

Pops an object from the front of the queue.

This returns an optional type which holds either the object at the bottom of the queue (the most recently added object) or an invalid optional.

// If using the object directly:
if (auto object = queue.pop()) {
  object->invoke_oject_member_function();
}

// If using the object for a call:
if (auto object = queue.pop()) {
  // Passes object by reference:
  function_using_bject(*object);
}

Return

An optional type which is in a valid state if the queue is not empty.

auto steal() noexcept -> Optional

Steals an object from the top of the queue.

This returns an optional type which is the object if the steal was successful, or a default constructed optional if not.

Example usage is:

// If using the object directly:
if (auto object = queue.steal()) {
  object->invoke_object_member_function();
}

// If using the object for a call:
if (auto object = queue.steal()) {
  // Passes object by reference:
  function_using_object(*object);
}

Return

A pointer to the top (oldest) element in the queue, or nullptr.

auto size() const noexcept -> Size

Gets the number of elements in the queue.

This does not always return the actual size, but an approximation of the size since top can be modified by another thread which steals.