3

std::unordered_map is too slow for me. I want something faster! What libraries/stand-alone sources implement alternative, faster, hash maps with a similar (or superior) interface?

Requirements:

  • Libre
  • Gratis
  • Some kind of testing to back claims of efficiency
  • Non-negligable user base

4 Answers 4

2

hopscotch

  • Form: Header only
  • License: MIT (Gratis and Libre)
  • Performance benchmark results: here
  • Git repository: tessil/hopscotch-map

Hopscotch is also quite performant. I found it when I was looking for something similiar I used once so far a smaller project where it had far more better performance than std::unordered_map. I didn't do performance tests compared to the other competitors.

The header only library is available on GitHub, at the link above. The library also provides implementations of other hash map algorithms. The creator claims that it uses less memory than Google's dense_hash_map but has similiar performance. But as you can see from other posts here new hash map implementations pop up quite continously. According to a post I read hopscotch is supposed to be faster than the ska::flat_hash_map. Either way it is a lot faster than the maps in std.

2
  • 1
    Can you describe what's special about it? Who developed it? What's the motivation/context for its development? Why it's called that?
    – einpoklum
    Jul 28, 2018 at 9:59
  • added some more details which I could find on a fast glimps and could recall from using it.
    – elchzucht
    Jul 28, 2018 at 12:54
2

If you can sacrifice guarantees like reference stability, you can use

ska::flat_hash_map by Malte Skarupke

The main features are:


There is also a talk about it on YouTube given by Malte Skarupke at C++ Now 2018:

You Can Do Better than std::unordered_map: New Improvements to Hash Table Performance

and blog posts on his personal blog where you can also find the benchmark picture below:

enter image description here

2
  • 1. Please write a couple of sentences about what's special with this hash map implementation, or what are its main design features; links are nice, but general policy on StackExchange is to have the basic information contained in the answer. 2. There are three different map headers at the link - how do they relate?
    – einpoklum
    Jul 28, 2018 at 11:14
  • @einpoklum I added the main features listed in the blog to this post. I don't think it is feasible to summarize a 1h 30min talk in a few sentences. Only the flat_hash_map.hpp header is important, I changed the link. Jul 30, 2018 at 5:19
1

There's a hash table shootout page at incise.org.

According to that, the best performance - in terms of speed, not memory - is with Google's Dense Hash Map: C++11 repository, original repository.

Note: The linked-to repositories are named "sparsehash", but actually contain both the sparse and dense hash maps, as well as sparse and dense hash sets.

8
  • 1
    The test is 8 years old - it might be worthwhile to revisit the numbers using current GCC.
    – TCSGrad
    May 18, 2018 at 22:30
  • In my more recent tests it is just as fast or faster than ska::flat_hash_map and F14 and both F14 and google dense are more memory efficient than ska::flat_hash_map: 1ykos.github.io/patchmap/#Performance%20comparison May 12, 2020 at 17:13
  • 1
    @WolfgangBrehm: What do you mean by "it"? I didn't mention "patchmap" in my answer... perhaps you could write a separate answer about your work?
    – einpoklum
    May 12, 2020 at 18:31
  • @einpoklum I'm thinking about it, that's why I'm here, but it's not really the fastest haha. But I made benchmarks that compare the patchmap, google dense, F14, ska::flat_hash_map and many more, which you can find when you follow the link. The fastest hash tables have the lower most points, the most memory efficient ones are to the right. May 12, 2020 at 18:36
  • @WolfgangBrehm: It doesn't have to be the fastest. The question is about hash maps faster than std::unordered_map. If it's interesting, and it seems to be - it merits an answer and probably an upvote.
    – einpoklum
    May 12, 2020 at 18:45
1

patchmap

  • open source
  • gratis support from me
  • extensive performance tests and sparse unit tests
  • almost perfectly mimicking the interface of std::unordered_map
  • open addressing using linear probing with pseudorandom ordering (similar to Robin-Hood hashing)

I had a similar problem, I need a hash table that was not just faster but also more memory efficient, that's why I created the patchmap. The most relevant statistic when judging the performance of a hash table is the space-time trade-off. Both time and memory are costly resources, so you'll want to save them, but the preferred trade-off can differ. lookup performance and memory usage of different hash tables

patchmap: 🔴                khash: × 
bytell: +                   google::sparse_hash_map: ○ 
google::dense_hash_map: ⬟   ska::flat_hash_map: △ 
std::unordered_map: ◇       sparsepp: ◻     
Judy array: ◆               F14ValueMap: ▲ 
chaining+sorting: •         robin_hood::unordered_map: ▽  
absl::flat_hash_map: ⬠      tsl::sparse_hash_map: ★ 
emilib2::HashMap: ▩ 

Successful lookups are probably the most prevalent operation a hash table needs to perform, but insertion, deletion and failing lookup benchmarks do not change the picture dramatically. The patchmap is not the fastest. The fastest would be a hash table using lots of memory, a fast and good hash, and a simple open addressing and probing scheme like linear probing. It is also not the most memory efficient, although pseudorandom ordering can be pushed to that regime, sacrificing speed. It does however offer a small product of space and time, on par with bytell, both only insignificantly better than absl::flat_hash_map.

1
  • That is quite the informative chart :-)
    – einpoklum
    May 12, 2020 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.