PLF Library - queue (original) (raw)

Home

Intro

plf::queue is a container that gives the programmer the functionality of a FIFO (first-in, first-out) queue. It is a more efficient drop-in replacement for std::queue, and faster than all std:: containers in the context of a queue. Like plf::colony it never invalidates references/pointers to non-popped elements, making it at least potentially useful for programming with containers of inter-related data structures. It supports C++11 move and emplace semantics and operations.

In real-world scenario benchmarking it is on average:

* Averaged across total numbers of stored elements ranging between 10 and 1000000, with the number of samples = 126 and the number of elements increasing by 10% per sample. The test in question is a pump test, where elements are pushed and popped consecutively with the overall number of elements fluctuating over time. Benchmarked on a 3rd gen i5, GCC 9.2, x64. Queue priority is set to plf::speed.

It obtains this performance difference by having a more limited/efficient structure compared to deque (the default underlying container of std::queue) implementations, and by using an adaptive capacity for memory blocks, which no deques to date do. This decreases the number of allocations/deallocations necessary, the number of block traversals when pushing/popping, and increases cache locality by enabling larger blocks. In addition, unlike most deque implementations, the block capacities are based on element sizeof(), not a fixed byte size. For most deque implementations, this means that larger element types effectively turn the deque into a linked list. Currently, libstdc++ uses fixed 512-byte block sizes, libc++ uses 4096 block sizes, and MSVC, perplexingly, 16-byte block sizes. For all three, if the element type is larger than the block size, the block size becomes the same as the element type, except for clang where the block size becomes 16 * element size.

In addition there are a few block optimisations implemented which only make sense in the context of a queue, which are detailed in the below.

Implementation

plf::queue uses the same chained-group memory allocation pattern as plf::colony and plf::stack ie. it is made up of a linked chain of 'groups', structs containing a memory block and metadata. New block capacities are based on the current number of elements in the container, not the capacity of previous blocks. This makes more sense in the context of a queue, because the first block in the queue may have a low number of elements left. In effect this makes the block capacities adaptive to the current number of stored elements.

If the plf::queue template parameter 'priority' is set to plf::memory, plf::queue aims for block capacities which are roughly == 1/4 of size(). This results in less unused memory during use as elements are pushed and popped. If set to plf::speed (default), it aims for block capacities == size(). This results in more cache locality during use. In addition, when priority is plf::memory, the default minimum block capacity is lower.

When creating a new block, if size() (or in the case of priority == plf::memory, 1/4 size()) is less than 2x the back block's capacity and greater than 0.5x the back block's capacity, the next block allocated will be the same capacity as the back block, rather than equal to the number of elements in the container. The latter feeds into the following optimisation: In the case where only two memory blocks are present, if the first and second memory block capacities are equal, and the first block is emptied via pop(), instead of being deallocated, the first block will be retained and will become the 'next' memory block in the sequence after the second block. This helps prevent unnecessary allocations/deallocations when a queue is receiving an equal number of push's and pop's. In terms of a consecutive sequence equal numbers of of pushes and pops, this means there will be no new block allocations, only recycling of front blocks.

So for example, a plf::queue with an initial single block of 8 elements, which is full, will create another block of 8 element capacity for the next push(), effectively doubling the potential size(). But another plf::queue with 3 blocks, with capacities == 8, 8, and 16 respectively, where the back block is full but the first block has had all but one element popped, making the size() == 25, the next block created by push() will be 16 elements (if Priority == plf::speed) - not a block of 32 elements.

The metadata within groups - 'elements' (pointer to the memory block), previous_group (pointer or NULL), next_group (pointer or NULL), and 'end' (pointer to last element in memory block) - aid respectively in the identification of when when a pop reaches the end of the memory block, iterating backwards to the previous block (upon an element construction exception), iterating forward to the next block, and identifying when a push reaches the capacity of a given memory block.

When capacity of the current memory block is reached, a new group is created and linked to via the next_group pointer. Reserve() can be called to create larger memory blocks ahead of time, and any unused memory blocks can be released via the trim() command. Lastly, minimum and maximum memory block sizes can be specified by the user. By default both the maximum and minimum capacities are algorithmically-determined based on sizeof(element_type), sizeof(queue) + sizeof(group metadata). The means a larger type will have a smaller default minimum size. In terms of the minimum default size, this avoids a scenario where plf::queue internal metadata data takes up more space initially than the stored type's memory blocks.

License

plf::queue is under a permissive zlib license. This means: Software is used on 'as-is' basis. It can be modified and used in commercial software. Authors are not liable for any damages arising from its use. The distribution of a modified version of the software is subject to the following restrictions:

Download

Download here or view the repository.
plf::queue is a simple .h header-only library, to be used with an #include command.

If you are interested in benchmarking you can also download the plf benchmark suite.

Function Descriptions and syntax

For the most part the syntax and semantics of plf::queue functions are the same as std::queue. However there are a few key differences, such as the ability to specify min/max block capacities in the constructor. Formal description is as follows:

template <class T, class Allocator = std::allocator <T> > class queue

**T** - the element type. In general T must meet the requirements of Erasable, CopyAssignableand CopyConstructible.
However, if emplace is utilized to insert elements into the queue, and no functions which involve copying or moving are utilized, T is only required to meet the requirements of Erasable.
If move-insert is utilized instead of emplace, T must also meet the requirements of MoveConstructible.
**Priority** - an enum whose value is either plf::memory or plf::speed. plf::speed is the default.
**Allocator** - an allocator that is used to acquire memory to store the elements. The type must meet the requirements of Allocator. The behavior is undefined if Allocator::value_type is not the same as T.

Basic example of usage

#include <iostream>
#include "plf_queue.h"

int main(int argc, char **argv)
{
  plf::queue<int> i_queue;

  // Insert 100 ints:
  for (int i = 0; i != 100; ++i)
  {
    i_queue.push(i);
  }

  // Total the ints:
  int total = 0;

  while (!i_queue.empty())
  {
    total += i_queue.front();
    i_queue.pop();
  }

  std::cout << "Total: " << total << std::endl;
  std::cin.get();
  return 0;
}

Member types

Member type Definition
value_type T
allocator_type Allocator
size_type Allocator::size_type (pre-c++11) std::allocator_traits::size_type (post-c++11)
reference Allocator::reference (pre-c++11) value_type & (post-c++11)
const_reference Allocator::const_reference (pre-c++11) const value_type & (post-c++11)
pointer Allocator::pointer (pre-c++11) value_type & (post-c++11)
const_pointer Allocator::const_pointer (pre-c++11) std::allocator_traits::const_pointer (post-c++11)

Constructors

default explicit queue(const allocator_type &alloc = allocator_type()) explicit queue(const size_type min_group_size, const size_type max_group_size = std::numeric_limits<size_type>::max() / 2, const allocator_type &alloc = allocator_type())
copy queue(const queue &source)
move queue(const queue &&source) noexcept (C++11 and upwards)Source queue has same status as an empty queue post-move.

Constructor usage examples

Member functions

Benchmarks

Benchmark results for queue under GCC 9.2 x64 on an Intel 3rd gen i5 are here.

Version history

Contact: footer
plf:: library and this page Copyright (c) 2024, Matthew Bentley