I am largely no longer on twitter.
plf:: library and this page Copyright (c) 2023, Matthew Bentley
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/23. Tested compilers include Clang 3.71-14, GCC 4.6-11 and MS Visual C++ 2010-2023.
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::queue - A data container replicating std::queue functionality but with better performance than standard library containers in a queue context.
plf::reorderase - A faster method for singular erasures, ranged erasures, and erase_if-style erasures for vector/deque/static_vector when element order is not important.
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 adaptation of PCG with fallback to xorshift for C++98/03.
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.
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.
Another talk entitled "Colony: how to" was presented at CPPNow! 2021. It's very much Not an introductory talk, dives right into the mechanics on a deeper level, and may be dry and boring to some. But it is more up to date:
The slides for the talk are available here (with extra, unused slides).
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 in speech: I didn't realise std::list's splice allowed for intra-list splicing (splicing from *this into *this) at the time.
Last talk, "Performance matters: New tricks for old dogs" was presented at MeetingCPP 2023. It covers most of my work outside of colony/hive, including a brief refresher on plf::list:
I failed to mention in the end of the speech that a caveat for time complexity's relevance is when 'O' (the operation) is very, very expensive, then obviously time complexity has a greater effect. This is rarely the case however.
Contact:
I am largely no longer on twitter.
plf:: library and this page Copyright (c) 2023, Matthew Bentley