Bannalia
bannalia.blogspot.com · Personal blog · on HN since 2013
Joaquín M López Muñoz writes about C++ data structures and Boost libraries, including hash tables, binary search layouts, and performance.
What HN saysCommenters cite it for Boost's unordered_flat_map, which they say beats Abseil in some benchmarks, and for the cache-friendly binary search post.
22HN people shared it
10linked it in comments
57stories submitted
713story points
6 months agolast shared
2013people per year2026
Most-shared posts
- 1Inside boost::unordered_flat_map5 people · 121 points · first shared 2022 · 44 comments on HN
- 2Cache-friendly binary search4 people · 83 points · first shared 2015 · 13 comments on HN
- 3Advancing the state of the art for std:unordered_map implementations2 people · 95 points · first shared 2022 · 51 comments on HN
- 4C++: Maps on Chains2 people · 50 points · first shared 2025 · 20 comments on HN
- 5Bulk Operations in Boost.Bloom2 people · 17 points · first shared 2025 · discussion on HN
- 6Trip June 2025 ISO C++ standards meeting2 people · 10 points · first shared 2024 · 1 comments on HN
- 7C++ encapsulation for Data-Oriented Design: performance2 people · 9 points · first shared 2015 · discussion on HN
- 8Bulk Visitation in Boost:Concurrent_flat_map2 people · 6 points · first shared 2023 · discussion on HN
- 9Fast polymorphic collections2 people · 2 points · first shared 2014 · discussion on HN
- 10A better hash table: GCC2 people · 1 points · first shared 2014 · discussion on HN
- 11The perfect shape1 people · 99 points · first shared 2014 · 21 comments on HN
- 12C++ encapsulation for Data-Oriented Design1 people · 44 points · first shared 2015 · 18 comments on HN
- 13Monadic lifting in C++1 people · 33 points · first shared 2014 · 17 comments on HN
- 14A better hash table1 people · 28 points · first shared 2014 · 1 comments on HN
- 15Deferred Argument Evaluation1 people · 24 points · first shared 2022 · 6 comments on HN
What HN people wrote when they linked it
spacechild1 · 2025-07-28
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.htm…
dtf · 2016-08-18
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/)
garaetjjte · 2026-04-30
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.htm… 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.
vitus · 2024-11-26
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.htm…
jcelerier · 2021-09-07
Isn't that the same principle that e.g. https://www.boost.org/doc/libs/master/doc/html/poly_collection.html which has existed since 2016 and described since 2014 (at least: https://bannalia.blogspot.com/2014/05/fast-polymorphic-collections.htm… ) ?
RcouF1uZ4gsC · 2019-01-11
Here is a writeup of the idea and some numbers.
http://bannalia.blogspot.com/2015/06/cache-friendly-binary-search.html
Kristine1975 · 2016-05-24
C++ supports it if you're willing to use more or less complicated templates:
http://bannalia.blogspot.de/2015/09/c-encapsulation-for-data-oriented.…
https://blog.molecular-matters.com/2013/10/22/implementing-a-semi-auto…
joaquintides · 2015-06-08
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
nly · 2015-06-07
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.h…
plorkyeran · 2014-03-17
And for C++, http://bannalia.blogspot.com/2014/01/a-better-hash-table-gcc.html shows significant differences between 3 different implementations of the same API (and which one is fastest varies between operations, as they're optimized for different things).