6 ms·
Inside boost::unordered_flat_map
- htfy96 4y agoTo anybody unfamiliar with recent progress, boost::unordered_flat_map is the fastest open-addressing hash map implementation in this field for C++. Coming out just several months ago, it outperforms absl::flat_hash_map and various other implementations benchmarked in https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ https://martin.ankerl.com/2022/08/27/hashmap-bench-01/.
- jeffbee 4y agoIt's a little hard to take seriously some of the top performers in that table, like emhash8, when the implementations are only a couple of weeks old and the commits are things like "fix crash", "fix clear", and "fix overflow".
- waynesonfire 4y agoUhh.. super irrelevant--being web scale is the most important attribute.
- no_wizard 4y agoI think I need more context for whet you’re trying to say here. I understand “web scale” in the marketing term Mongo sense but I don’t know how that applies to this
- layer8 4y agoI’m pretty sure they’re being sarcastic.
- MauranKilom 4y ago> I understand “web scale” in the marketing term Mongo sense That's the joke. (And for anyone who hasn't seen it: https://www.youtube.com/watch?v=b2F-DItXtZs https://www.youtube.com/watch?v=b2F-DItXtZs)
- tubs 4y agoThat link does not have boost unordered_flat_map?
- anonymoushn 4y agoI have tried swiss tables but I have been unable to make these match the performance of robin hood tables with a single-stage lookup. Fundamentally the issue seems to be that swiss tables require one to read 2 or 3 cache lines while the alternative requires one to read only 1 cache line per lookup (most of the time). The included benchmarks are not that useful for inserting many items or looking up many items because one can achieve much higher throughput using prefetching (like <<10ns/op), but this sort of consideration never makes it into any graphs.
- roboben 4y agoReading boost:: gives me shivers and flashbacks of my Diploma thesis
- hesdeadjim 4y agoIf you want to see utter hell on earth, check out CGAL. Even at my peak C++ TMP days it was bad, being 10 years out of C++ completely, it’s vomit inducing.
- 77pt77 4y agoThis one: https://www.cgal.org/ https://www.cgal.org/ ?
- hesdeadjim 4y agoYea, computational geometry library. What’s unfortunate is that it’s basically the only quality implementation for some pretty niche algorithms.
- ActorNightly 4y agoI still point to wide adoption of boost:: as reason why C++ should never be used. If 4 pages of a single error message isn't enough to convince someone, nothing will.
- jcelerier 4y ago
- mkoubaa 4y agoSometimes I wonder why these nifty data structures that someone already implemented in c++ don't immediately (or even 5+ years later) have ports to other languages. Especially languages that are closer to the metal than average (e.g. Rust, Go, ...)
- deleted 4y ago[deleted]
- tialaramex 4y agoWhat sort of languages are you thinking of which are "closer to the metal" than C++ but support the features you'd want for these structures ? The closest I can think of is Rust, but it does have ports of such things. Rust's HashMap is a Swiss Table - Abseil's flash_hash_map but ported to Rust (via HashBrown), Haphazard is a Rust port of the Folly library's hazard pointers (which might some day be C++ 26 or C++ 29 Hazard Pointers)
- sgerenser 4y agoperhaps mkoubba meant “closer to the metal” than the average programming language, like, say Swift or even C#, not “closer to the metal” than C++. Otherwise it the comment makes little sense, as I would not even consider Rust “closer to the metal” than C++. Maybe C or x86 Assembly?
- mkoubaa 4y agoYes precisely. Closer than the average
- uluyol 4y agoThere are different semantics for these data structures in different languages. These tend to exist for corner cases, but those corner cases constrain your design. So you might not be able to replace the default Java hashmap with absl::flat_hash_map, but you can steal ideas and maybe do better in other ways where the C++ map would be constrained. However, doing that is work that someone has to pick up. And releasing a (e.g.) Go library that breaks from the built in map semantics might not see much adoption in that community. C++ actually seems a bit unique in terms of how many widely used implementations there are of key data structures (e.g. strings, maps, trees, inline vectors). Not criticizing just making an observation.
- jonstewart 4y agoI wish that such benchmarks included bad old std::map, too, so that I could beat my stubborn coworker with them until he finally started using hash maps by default.
- plq 4y agoThere isn't one std::map though, each C++ stdlib has its own.
- jonstewart 4y agoTrue enough!
- gpderetta 4y agostd::map has very different characteristics though. Do you mean std::unordered_map?
- KerrickStaley 4y agoRelated: this talk https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4 about the making of absl::flat_hash_map (a "competitor" to boost::unordered_flat_map) is one of my favorites.
- garaetjjte 4y agoThis talk is also interesting, covering multiple approaches: https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ
- samsquire 4y agoImagine you could interact with an object that had the API of all data structures. And it looked like a HashMap if you ran hash operations on it or like a linked list if you interacted with it that approach. Behind the scenes the compiler shall analyse all your calls to that data structure and see what APIs you use to interact with it. It can then decide which algorithms to use to optimise your interaction with that data structure. If only computers could do hot/cold analysis. It could detect that you call a hash lookup in a hot for loop but only call the ordered map iterator from the admin screen and outside a loop. I would then JIT compile the right data structure algorithm used from a bucket of implemented algorithms. So the data is kept optimised for its usage patterns. Decisions such as use tombstones, compaction, vacuum, LSM trees, btrees, ordered, unordered, LSM trees with separate value storage, a growable array, a std::list or vector. All depend on what your intended access patterns to the data is. Could also do clever materialized views. If you only use one view of the data rarely, it isn't efficient to maintain that view.
- anonymoushn 4y agoThis sounds cool but currently compilers are very very bad at way way easier transformations
- duckerude 4y agoPHP's arrays are a bit like this. You can treat them either like an (ordered) hashmap or like a growable array. The underlying representation will adapt depending on whether the current state can be represented as an array. And I hate it! I'm always unsure about an array's contents. I write functions that expect to operate on linear arrays and might misbehave if given a map, or vice versa. It's rare for the conflation to be helpful. Arrays and maps have different meanings and are used in different ways. Maybe a very mild version of this would be helpful, like automatically converting an array to an array-backed deque—though even that case seems better handled by a linter making the suggestion, so the programmer can make an informed decision. Going all the way would be terrible. Types are helpful. Even in a dynamically typed language they give you a vocabulary.
- IshKebab 4y agoThis is exactly how JavaScript arrays work. I'm not convinced it's a good idea in general because usually the author will have a good idea about how the data will be accessed and what kind of data there is so if you can choose up front you may as well. Plus having runtime analysis like that can lead to weird and unpredictable performance characteristics.
- dzdt 4y agoI have a question about time complexity for hash maps. What is considered the complexity of inserting an initially unknown number n of items into the map? My longstanding belief was that this complexity should be O(n log n) because a particular hash size will be chosen and then have to be repeatedly grown as the density of the map's population overwhelms the current size of the structure. An exponentially increasing size gives growth steps every log n items, and the growth step will require O(n) time. Now everyone seems to believe that hash maps insertion is O(1) time with the only exception being degenerate coincidence between hash function and hashed data that puts large number of items into the same bucket. Do current hash maps avoid O(n) complexity when growth is required? How?
- throw827474737 4y agoSizing the hash map appropriately is one of the tuning knobs to usually achieve the O(1) desired complexity, in theory you are right, but tuning away from that in practice this does not or rare enough happens is the goal why you actually chose a hash map for hopefully close to O(1)?
- joaquintides 4y agoComplexity is still O(n) because sizes grow exponentially, so the cost of amortizing rehashes over the number of inserted elements is a constant. Here's a theoretical analysis of this: https://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/lec20-amortized/amortized.htm https://www.cs.cornell.edu/courses/cs3110/2011sp/Lectures/le...