Joaquín M López Muñoz writes about C++ data structures and Boost libraries, including hash tables, binary search layouts, and performance.
Commenters cite it for Boost's unordered_flat_map, which they say beats Abseil in some benchmarks, and for the cache-friendly binary search post.
I was very glad to find this page earlier this week, after scratching my head while implementing an isometric renderer for a client. I had assumed it would be a simple back-to-front order, but this page and a few others pointed out that the partial ordering required to 1) use an intersection test to build disjoint sets of confused objects, 2) use a pairwise order test to determine inter-object dependencies, 3 ) use a topological sort to resolve the ultimate drawing order.
This method was implemented in some fantastic 1980s computer games, and the developer had named their technique "Filmation". Here's a discussion of that system, plus a demo of the rendering bug caused by not bothering to break dependency cycles as discussed in the main article:
http://bannalia.blogspot.co.uk/2008/02/filmation-math.html
(also I just found another with a load more details on the Filmation games: http://retrospec.sgn.net/users/nwalker/filmation/)
The reddit thread mentions that the author was probably going to write a blog post about it at some point; I went and found it so you don't have to.
I was curious what exactly differentiates boost::unordered_flat_map from absl::flat_hash_map, and was not disappointed. It seems that the lion's share of the performance improvement comes from using more of the metadata for the reduced hash value, although there are a few other contributing factors.
The blog post further describes where absl::flat_hash_map performs better: iteration (and consequently erasure), which is ironic given those are a couple of areas where I always felt that absl::flat_hash_map was especially weak. But, it makes sense to double down on Abseil's strengths as well as its shortcomings.
https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html
Indeed. std::unordered_* implementations are hogtied by the interface and complexity requirements in the C++ standard (it basically mandates chained buckets), and more generally the need to work with almost any hash function (linear probing would suck with crappy hash functions for example).
Jo Muñoz wrote a cool blog series on the current implementations in circulation, the flaws with the interface, and how his implementation (Boost multi_index) made further optimisations despite the constraints.
Don't miss the other two parts of the series - look under October on the right. He did extensive bookmarks in November as well.
http://bannalia.blogspot.co.uk/2013/10/implementation-of-c-unordered.html
I once did have a need for binary search in memory mapped files and I experimented with Eytzinger layout (which I learned from https://bannalia.blogspot.com/2015/06/cache-friendly-binary-search.html). It turned out that it was slower than plain binary search, I think because keys I was looking up were often clumped together thus it played quite well with cache anyway.
You might also consult the entries given below, which take into account some late improvements in Boost.MultiIndex not present at the beginning of the series:
http://bannalia.blogspot.com/2014/01/a-better-hash-table.html
http://bannalia.blogspot.com/2014/01/a-better-hash-table-gcc.html
http://bannalia.blogspot.com/2014/01/a-better-hash-table-clang.html
It's worth mentioning that boost.unordered now also has a state-of-the-art open adressing hashtable (boost::unordered_flat_map) that beats abseil in some benchmarks, particularly for unsuccessful look-up: https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html?m=1