FlexQueue¶

What is FlexQueue?¶

FlexQueue is a flexibly-sized queue similar to std::queue. Internally, it is implemented as a circular buffer deque, guaranteed to be stored in contiguous memory, thereby helping to avoid or minimize cache misses.

While we aim to create a high-performance data structure, our top priority is in giving the user easy control over the tradeoffs between CPU performance, memory, and cache misses.

Performance¶

Because std::queue is based on std::deque, and thereby is not stored in contiguous memory, we instead must benchmark FlexQueue against std::vector.

FlexQueue is usually as fast as, or faster than, std::vector. Here’s how FlexQueue ranks against the GCC implementation of std::vector…

Pushing (to back) is faster.
Popping (from front) is faster.
Accessing is at least as fast.

If general performance is more important to you than contiguous memory, see SpeedQueue.

Comparison to `std::queue`¶

FlexQueue offers largely the same functionality as std::queue. However, it is not intended to feature-identical. Some functionality hasn’t been implemented yet, and we may not include some other features to leave room for future optimization and experimentation.

FlexQueue does not offer iterators. This may be added in the future.
You cannot change the underlying data structure. Our base class is where most of the heavy lifting occurs.
Some advanced modifiers haven’t been implemented yet.

Technical Limitations¶

FlexQueue can store a maximum of 4,294,967,294 objects. This is because it uses 32-bit unsigned integers for internal indexing, with the largest value reserved as INVALID_INDEX. The limit is calculated as follows.

2^{32} - 2 = 4,294,967,294

Using FlexQueue¶

Queues are “First-In-First-Out”; you insert to the end (or “back”), and remove from the front.

Including FlexQueue¶

To include FlexQueue, use the following:

#include "nimbly/flexqueue.hpp"

Creating a FlexQueue¶

A FlexQueue object is created by whatever means is convenient. It handles its own dynamic allocation for storing its elements.

When the FlexQueue is first created, you must specify the type of its elements.

// Both of these methods are valid...

FlexQueue<int> dmvLine;

anotherQueue = new FlexQueue<int>;

Raw Copy¶

By default, FlexQueue uses standard assignment for moving items when the internal data structure resizes. However, if you’re storing atomic data types, such as integers, additional performance gains may be achieved by having FlexQueue use raw memory copying (memcpy) instead.

To switch to Raw Copy Mode, include true as the second template parameter (raw_copy).

FlexQueue<int, true> i_use_rawcopy;

Resize Factor¶

When we run out of space in the data structure, we need to reallocate memory. To reduce the CPU cycles used on reallocation, we allocate more space than we immediately need. This resize factor is controllable.

By default, when the FlexQueue resizes, it doubles its capacity (n * 2). This provides the best general performance. However, if you want to preserve memory at a small performance cost, you can switch to a resize factor of n * 1.5 (internally implemented as n + n / 2).

To switch to the 1.5 factor, include false as the third template parameter (factor_double).

FlexQueue<int, true, false> i_resize_slower;

Reserve Size¶

We can specify the initial size (in elements) of the FlexQueue in the constructor.

FlexQueue<int>* dmvLine = new FlexQueue<int>(250);

Note

The FlexQueue will always have minimum capacity of 2.

Adding Elements¶

`enqueue()`¶

enqueue() adds a value to the end of the queue. Aliases push() and push_back() are also provided. This function has the performance of O(1).

FlexQueue<int> apples;

// We'll add some values
// using the three aliases
apples.enqueue(23);
apples.push(12);
apples.push_back(31);

// The queue is now [23, 12, 31]

If there is ever a problem adding a value, the function will return false. Otherwise, it will return true.

Accessing Elements¶

`at()`¶

at() allows you to access the value at a given index.

FlexQueue<int> apples;

// We'll push some values for our example
apples.push(23);
apples.push(12);
apples.push(31);

apples.at(1);

// The queue is [23, 12, 31]
// This output yields 12

Alternatively, you can use the [] operator to access a value.

// Using the queue from above...

apples[2];

// The queue is [23, 12, 31]
// This output yields 31

Warning

If the queue is empty, or if the specified index is too large, this function/operator will throw the exception std::out_of_range.

`peek()`¶

peek() allows you to access the next element in the queue without modifying the data structure.

FlexQueue<int> apples;

// We'll push some values for our example
apples.push(23);
apples.push(12);
apples.push(31);

std::cout << apples.peek();

// This output yields 23
// The queue remains [23, 12, 31]

Warning

If the queue is empty, this function will throw the exception std::out_of_range.

Removing Elements¶

In a queue, we typically remove and return elements from the beginning, or “front” of the queue. Imagine a line at a grocery store - you enter in the back and exit in the front.

`clear()`¶

clear() removes all the elements in the FlexQueue.

FlexQueue<int> pie_sizes;

pie_sizes.push(18);
pie_sizes.push(18);
pie_sizes.push(15);

// I ate everything...
pie_sizes.clear();

// The FlexQueue is now empty.

This function always returns true, and will never throw an exception (no-throw guarantee).

`dequeue()`¶

dequeue() will remove and return the first element in the queue. Aliases pop() and pop_front() are also provided. This function has the performance of O(1).

FlexQueue<int> apples;

// We'll push some values
apples.push(23);
apples.push(12);
apples.push(31);
apples.push(40);

// The queue is now [23, 12, 31, 40]

// We'll now remove three elements
// with the three provided aliases
apples.dequeue();
apples.pop();
apples.pop_front();

// The queue is now simply [40]

Warning

If the queue is empty, this function will throw the exception std::out_of_range.

`erase()`¶

erase() allows you to delete elements in a queue in a given range. Remaining values are shifted to fill in the empty slot. This function has a worst-case performance of O(n/2).

FlexQueue<std::string> coffeeshop_line;

// We'll push some values for our example
coffeeshop_line.enqueue("Bob");
coffeeshop_line.enqueue("Jane");
coffeeshop_line.enqueue("Alice");

// The queue is currently ["Bob", "Jane", "Alice"]

apples.erase(0,1);
// The first number in the function call is the lower bound
// The second number is the upper bound.
// The queue is now simply ["Alice"]

If any of the indices are too large, this function will return false. Otherwise, it will return true. It never throws exceptions (no-throw guarantee).

Size and Capacity Functions¶

`getCapacity()`¶

getCapacity() returns the total number of elements that can be stored in the FlexQueue without resizing.

FlexQueue<int> short_term_memory;

short_term_memory.getCapacity();
// Returns 8, the default size.

`length()`¶

length() allows you to check how many elements are currently in the FlexQueue.

FlexQueue<int> apples;

// We'll enqueue some values for our example
apples.enqueue(23);
apples.enqueue(42);
apples.enqueue(36);

apples.length();
// The function will return 3

`isEmpty()`¶

isEmpty() returns true if the FlexQueue is empty, and false if it contains values.

FlexQueue<int> answers;

answers.isEmpty();
// The function will return true

// We'll enqueue some values for our example
answers.enqueue(42);

answers.isEmpty();
// The function will return false

`isFull()`¶

isFull() returns true if the FlexQueue is full to the current capacity (before resizing), and false otherwise.

FlexQueue<int> answers;

answers.isFull();
// The function will return false

// Push values until we are full, using the isFull() function to check.
while(!answers.isFull())
{
    answers.enqueue(42);
}

`reserve()`¶

You can use reserve() to resize the FlexQueue to be able to store the given number of elements. If the data structure is already equal to or larger than the requested capacity, nothing will happen, and the function will return false.

FlexQueue<std::string> labors_of_hercules;

// Reserve space for all the elements we plan on storing.
labors_of_hercules.reserve(12);

labors_of_hercules.getCapacity();
// Returns 12, the requested capacity.

After reserving space in an existing FlexQueue, it can continue to resize.

This function is effectively identical to specifying a size at instantiation.

`shrink()`¶

You can use shrink() function to resize the FlexQueue to only be large enough to store the current number of elements in it. If the shrink is successful, it wil return true, otherwise it will return false.

FlexQueue<int> marble_collection;

for(int i = 0; i < 100; ++i)
{
    marble_collection.enqueue(i);
}

marble_collection.getCapacity();
// Returns 128, because FlexQueue is leaving room for more elements.

// Shrink to only hold the current number of elements.
marble_collection.shrink();

marble_collection.getCapacity();
// Returns 100, the same as the number of elements.

After shrinking, we can continue to resize as new elements are added.

Note

It is not possible to shrink below a capacity of 2.

FlexQueue¶

What is FlexQueue?¶

Performance¶

Comparison to std::queue¶

Technical Limitations¶

Using FlexQueue¶

Including FlexQueue¶

Creating a FlexQueue¶

Raw Copy¶

Resize Factor¶

Reserve Size¶

Adding Elements¶

enqueue()¶

Accessing Elements¶

at()¶

peek()¶

Removing Elements¶

clear()¶

dequeue()¶

erase()¶

Size and Capacity Functions¶

getCapacity()¶

length()¶

isEmpty()¶

isFull()¶

reserve()¶

shrink()¶

Comparison to `std::queue`¶

`enqueue()`¶

`at()`¶

`peek()`¶

`clear()`¶

`dequeue()`¶

`erase()`¶

`getCapacity()`¶

`length()`¶

`isEmpty()`¶

`isFull()`¶

`reserve()`¶

`shrink()`¶