plf::list is a drop-in higher-performance replacement for std::list,
featuring 333% faster insertion, 81% faster erasure, 16% faster
iteration and 72% faster sorting on average. This results in 25%
faster performance overall in ordered use-case benchmarking.
Like std::list, plf::list maintains stable pointer/iterator links to list elements regardless of erasure, insertion, merging, splicing, reversing and sorting. It's functionality replicates std::list with two minor exceptions: the removal of incomplete list splices (splicing whole lists is still available) and inclusion of several useful functions: reserve(), shrink_to_fit(), free_unused_memory(), and approximate_memory_use().
It achieves it's speed via the following:
The first increases insertion and erasure speed since individual
per-element allocations and deallocations are no longer necessary, and
also increases the speed of iteration due to increased element
contiguousness in memory.
The second re-uses erased element memory locations, but in a way which promotes element contiguousness (positioning the inserted element as close to the insertion position as possible in memory). Several other methods were trialed, but this had the best balance of reinsertion speed and subsequent iteration speed.
The third is a simple method which allows any linked list to use quicksort-style internal sorting rather than the slower mergesort-based internal sorting typically utilized, but without invalidating pointers/iterators to elements and without the disadvantage of slower sort speed for larger-than-scalar types typically evidenced with a quicksort method.
Linked lists have many useful characteristics: they splice together without losing pointer validity to contained elements, they sort fast for large types, and their erasure speed is very good. Unfortunately the base implementation of most linked lists disallows decent performance for insertion - specifically, most linked lists allocate per-node, which in the modern age is particularly slow. The current (2017) C++ spec disallows clustered allocations by allowing partial list splicing - ie. if a block of nodes is allocated instead of one, the block cannot be split without invalidating pointers to nodes within the block. This in turn has a negative effect on iteration and erasure due to cache effects.
plf::list is a re-think from the ground-up of how to structure a linked list around modern hardware. This means grouped allocations, re-use of memory and sort modification. The result is not something which can compete with vector for iteration performance, but which easily beats it for insertion and erasure speeds, and increases it's competitiveness with aspects like sorting. It is designed as a drop-in replacement for std::list, as well as a demonstration of how lists can perform outside of the C++ specification's requirement of partial splicing.
plf::list is designed for better push_back() performance than push_front() performance, in keeping with the most typical container usage patterns.
As detailed earlier, extensive testing showed block sizes of 2048 elements to be optimal across types for balancing the reinsertion mechanism - what this means is that, for any given block, the free list may contain element locations in any area of that block, and, the location popped off the top of the list to be used for reinsertion, may not be the location closest to the insertion position (out of all locations in the free list). But if we decrease the block size, we increase the probability of any free list location being closer to the insertion position. However making the block size too low results in lowered iteration speeds, as fewer elements are contiguous.
Other methods were tested for the reinsertion mechanism, with the dual aim of quick reinsertion and finding a reinsertion location as close to the insertion position as possible. In no particular order they are:
As mentioned, the latter is the chosen method - however there were several sub-methods of this which did not get selected. The first was to process the selected free list to find the location within that free list closest to the insertion position. This did not result in a net gain when benchmarked with subsequent iterations balanced against the additional reinsertion cost. The second sub-method was searching from the last memory block in the list to the first sequentially instead of radiating outwards from the insertion position's block - again this was slower, due to the likelyhood of finding a location further away in memory than with the radiant pattern.
The reason why the radiant pattern works best is because in terms of iteration, if you find a location in as close a memory block as possible, you increase the overall statistical likelihood that the linked list sequence will also follow the sequence of the memory blocks in memory (provided the blocks are allocated close to each other, this will affect cache locality).
Normally it is impossible for a container with a bidirectional iterator (such as a list) to utilize std::sort, as it requires a random-access iterator. This method allows any container to use std::sort (or any sort technique that requires random-access iterators). It has a memory cost of N pointers over a normal list sort - one pointer for each element in the container. Each element has it's node's memory address inserted into an array - the order of the insertion is not important. Hence, while with a traditional linked list the list must be iterated over to add the addresses to the array, with plf::list the nodes of all memory blocks can be processed sequentially in order, speeding up the process of filling the array.
Once this array of N pointers is filled with the addresses of all active nodes in the list, we then use a templated redirection in order to sort these pointers based on the value of the elements within the nodes that they point to:
template <class comparison_function>
sort_dereferencer(const comparison_function &function_instance):
bool operator() (const node_pointer_type first, const node_pointer_type second) const
return stored_instance(first->element, second->element);
This function object takes whatever sort function is supplied to the sort operation, and uses it to sort the pointers instead of the elements. Since an array is a linear structure and can hence utilize a random-access iterator, we can now sort the array of pointers using std::sort (or any quicksort-type technique), the function object above and whichever sort function is supplied.
Once the pointers are sorted according to the sort function and the elements themselves, the final process is simple;
The resultant sort process is roughly 72% faster than std::list's sort, when averaged across all datatypes and numbers of elements. It is not, unlike mergesort, stable (in this context, stable means two contiguous objects with the same sort value will be in the same order once sorted), because std::sort is not guaranteed to be stable, but std::stable_sort can be used instead if this is important.
The internal structure of plf::list is as follows: a custom vector holds the individual memory blocks that the elements are stored within, plus each memory block's metadata (this combined with the memory block is termed a 'group'). Part of the metadata is each block's 'free list' of erased memory locations. When a memory block becomes empty of elements it is either freed to the OS or moved to the back of the vector for subsequent re-use in future. The implementation defines the protocol for deciding whether or not to free the block, but in my implementation the decision is based on whether or not the memory block is of maximum size, and also whether it is close to the back of the vector.
When an insertion occurs, if there are no erased locations the new element is pushed to the next available element location in the last memory block and then linked into insertion position. Otherwise the free list of the memory block which the insertion position is within is checked - if empty, we check each memory block to the left and right in sequence until a non-empty free list is found. The selected non-empty free list has it's top element popped off and re-used.
To avoid double-destruction of elements when clearing or destroying a plf::list, element nodes which are added to their memory block's free list have their 'next' pointer set to the same value as their 'previous' pointer - since free lists only utilize the previous pointer, this has no effect on operation. When a plf::list is cleared or destroyed, instead of iterating over the list normally, we can more quickly iterate directly over the memory blocks themselves, destroying any element of any node where the previous pointer is not the same as the next pointer. The reason this is faster is because in this method, each subsequent node is contiguous in memory while iterating, compared to a regular list traversal which can jump all over the place.
plf::list 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 here (21kb zip file) or
view the repository
The list library is a simple .h header file, to be included with a #include command.
In addition if you are interested in benchmarking you can also download the plf benchmark suite (44kb zip file), which includes plf::nanotimer.
plf::list meets the technical specifications and has the same functions and iterator functions as std::list, with the exception of the removal of partial splices. Only full list splices are allowed. In addition, plf::list does not guarantee that contiguous and equal elements will be in the same order after sorting as std::list does (ie. the sort style is not a 'stable'-type). Additional functions specific to plf::list follow:
Removes any trailing groups within the container substructure, which may
be present in the scenario of many erasures. Unlike a
regular shrink_to_fit, does not shrink capacity to the size needed to
contain the currently-stored elements, simply frees up unused groups.
Runtime cost is significantly lower than shrink_to_fit, but may not free as
Reduces container capacity to the amount necessary to store all
currently stored elements, consolidates elements and removes any erased locations. Invalidates all pointers, iterators and
references to elements within the container.
void reserve(size_type reserve_amount)
Preallocates memory space sufficient to store the number of elements
reserve_amount. If possible the algorithm will re-use existing empty memory blocks, so long as they are large enough.
Returns total number of elements currently able to be stored in
container without expansion.
std::cout << i_list.capacity()
Benchmark results under GCC 7.1 x64 on an Intel Xeon E3-1241 (Haswell) are available here.
plf:: library and this page Copyright (c) 2017, Matthew Bentley