PLF C++ Library

PLF is a collection of header-only library modules for C++. Please click on the links below to learn more about the different modules and to download. All modules are under a permissive Zlib license and support C++98/03/11/14/17/20. Tested compilers include Clang 3.71-10, GCC 4.6-10 (32-bit and 64-bit) and MS Visual C++ 2010-2019.


blog - A random collection of thoughts, assembled and poorly filtered through cognitive biases and subjective aesthetics, resulting in a distortion of perspective.


plf::colony - An unordered bucket-like data container providing fast iteration/insertion/erasure while maintaining pointer/iterator validity to non-erased elements.

plf::list - A data container replicating std::list functionality but with (on average) 333% faster insertion, 81% faster erasure and 16% faster iteration.

plf::stack - A data container replicating std::stack functionality but with better performance than standard library containers in a stack context.

plf::indiesort - A sort wrapper enabling both use of random-access sorting on non-random access containers, and increased performance for the sorting of large types.

plf::nanotimer - A cross-platform lowest-overhead microsecond-precision timer for simple benchmarking on Linux/BSD/Windows/Mac.

plf::rand - A replacement for rand()/srand() that's ~700% faster with (typically) better statistical distribution. An adaption of PCG with fallback to xorshift for C++98/03.

Papers

The high complexity jump-counting pattern - A skipfield pattern which avoids branching during iteration. Previously used by colony versions 4.68 and lower. Has additional graphs with performance vs a boolean skipfield, as well as details of a general skipfield compression algorithm. Previously known as the 'advanced jump-counting skipfield pattern' link.

The low complexity jump-counting pattern - A similar skipfield pattern which also avoids branching during iteration and which has reduced time complexity compared to it's counterpart, hence the name. Used by colony v5 and onwards. Previously known by a working title of 'Bentley pattern'.

Modulated jump-counting patterns - A method of conditionally skipping or processing multiple different types of objects.

Random access of elements in data containers using multiple memory blocks of increasing capacity - How to use power-of-2 block sizes and bit-manipulation to enable growth factors in the capacity of memory blocks, in multiple-memory-block random access containers.



Talks

The following talk entitled "Colonies, performance and why you should care" was presented at CPPcon 2016. Please note the talk is out-of-date in terms of the technology used in Colony and benchmarks:

The slides for the talk are available here.

The following talk entitled "Can we make a faster linked list?" was presented at PacifiC++ 2017:

The slides for the talk are available here. Minor bug: I didn't realise std::list's splice allowed for intra-list splicing (splicing from *this into *this) at the time.

Contact: footer
I am no longer on twitter (with the odd exception of making announcements) as I find the US-centric nature of the discourse slightly baffling.
plf:: library and this page Copyright (c) 2020, Matthew Bentley