Hopscotch map
unordered
Hopscotch map | unordered | |
---|---|---|
3 | 10 | |
701 | 53 | |
- | - | |
3.7 | 9.2 | |
7 months ago | 5 days ago | |
C++ | C++ | |
MIT License | Boost Software License 1.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Hopscotch map
-
boost::unordered map is a new king of data structures
Unordered hash map shootout CMAP = https://github.com/tylov/STC KMAP = https://github.com/attractivechaos/klib PMAP = https://github.com/greg7mdp/parallel-hashmap FMAP = https://github.com/skarupke/flat_hash_map RMAP = https://github.com/martinus/robin-hood-hashing HMAP = https://github.com/Tessil/hopscotch-map TMAP = https://github.com/Tessil/robin-map UMAP = std::unordered_map Usage: shootout [n-million=40 key-bits=25] Random keys are in range [0, 2^25). Seed = 1656617916: T1: Insert/update random keys: KMAP: time: 1.949, size: 15064129, buckets: 33554432, sum: 165525449561381 CMAP: time: 1.649, size: 15064129, buckets: 22145833, sum: 165525449561381 PMAP: time: 2.434, size: 15064129, buckets: 33554431, sum: 165525449561381 FMAP: time: 2.112, size: 15064129, buckets: 33554432, sum: 165525449561381 RMAP: time: 1.708, size: 15064129, buckets: 33554431, sum: 165525449561381 HMAP: time: 2.054, size: 15064129, buckets: 33554432, sum: 165525449561381 TMAP: time: 1.645, size: 15064129, buckets: 33554432, sum: 165525449561381 UMAP: time: 6.313, size: 15064129, buckets: 31160981, sum: 165525449561381 T2: Insert sequential keys, then remove them in same order: KMAP: time: 1.173, size: 0, buckets: 33554432, erased 20000000 CMAP: time: 1.651, size: 0, buckets: 33218751, erased 20000000 PMAP: time: 3.840, size: 0, buckets: 33554431, erased 20000000 FMAP: time: 1.722, size: 0, buckets: 33554432, erased 20000000 RMAP: time: 2.359, size: 0, buckets: 33554431, erased 20000000 HMAP: time: 0.849, size: 0, buckets: 33554432, erased 20000000 TMAP: time: 0.660, size: 0, buckets: 33554432, erased 20000000 UMAP: time: 2.138, size: 0, buckets: 31160981, erased 20000000 T3: Remove random keys: KMAP: time: 1.973, size: 0, buckets: 33554432, erased 23367671 CMAP: time: 2.020, size: 0, buckets: 33218751, erased 23367671 PMAP: time: 2.940, size: 0, buckets: 33554431, erased 23367671 FMAP: time: 1.147, size: 0, buckets: 33554432, erased 23367671 RMAP: time: 1.941, size: 0, buckets: 33554431, erased 23367671 HMAP: time: 1.135, size: 0, buckets: 33554432, erased 23367671 TMAP: time: 1.064, size: 0, buckets: 33554432, erased 23367671 UMAP: time: 5.632, size: 0, buckets: 31160981, erased 23367671 T4: Iterate random keys: KMAP: time: 0.748, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 CMAP: time: 0.627, size: 23367671, buckets: 33218751, repeats: 8, sum: 4465059465719680 PMAP: time: 0.680, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 FMAP: time: 0.735, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 RMAP: time: 0.464, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 HMAP: time: 0.719, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 TMAP: time: 0.662, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 UMAP: time: 6.168, size: 23367671, buckets: 31160981, repeats: 8, sum: 4465059465719680 T5: Lookup random keys: KMAP: time: 0.943, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 CMAP: time: 0.863, size: 23367671, buckets: 33218751, lookups: 34235332, found: 29040438 PMAP: time: 1.635, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 FMAP: time: 0.969, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 RMAP: time: 1.705, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 HMAP: time: 0.712, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 TMAP: time: 0.584, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 UMAP: time: 1.974, size: 23367671, buckets: 31160981, lookups: 34235332, found: 29040438
-
Yes, this is embarrassingly slow .so I solved your problem
the map member used for the lookups is a tsl::hopscotch_map (https://github.com/Tessil/hopscotch-map), which is a proper hash map. so it seems to be the latter, that the API is wrong, but from what I can tell it is only a wrongly named class. i don't see where the API makes guarantees about iteration order, which is where the implementation difference would be noticeable (beyond performance for lookup).
-
Any suggestions for resources to optimize for memory allocation/reallocation?
using an open-addressing hash table, such as abseil flat_hash_map or tessil/hopscotch-map
unordered
-
Effortless Performance Improvements in C++: std::unordered_map
We added two new benchmarks to Boost.Unordered, word_count and word_size, and the second one ends up testing a small hash table (114 elements in 64 bit, even fewer in 32 bit because we use a smaller input file there.)
-
Inside boost::unordered_flat_map
Hi, we have seen similar gains with __forceinline in MSVC, looks like this compiler is not particularly aggressive at inlining. Could you please file an issue at Boost.Unordered repo so what we don't forget? Thank you
-
Boost 1.81 will have boost::unordered_flat_map...
You can request a feature be added by opening an issue in https://github.com/boostorg/unordered.
-
boost::unordered map is a new king of data structures
Here are the results of our uint32.cpp synthetic benchmark under VS2022 Release x64:
-
Advancing the state of the art for <code>std::unordered_map</code> implementations
You can run these benchmarks yourself from the Boost develop branch, they are in the Unordered repo. Since Unordered is header-only, there should be need to build Boost but you do need to bootstrap and then run b2 headers to create the symlinks in boost/.
-
New Boost.Unordered containers have BIG improvements!
Make sure you checkout the preview.md for instructions on how to build nightly Boost in a way that's non-intrusive to your system and works with CMake.
What are some alternatives?
C++ B-tree - Git mirror of the official (mercurial) repository of cpp-btree
flat_hash_map - A very fast hashtable
PEGTL - Parsing Expression Grammar Template Library
FetchBoostContent - CMake FetchContent for Boost libraries
sparsehash-c11 - Experimental C++11 version of sparsehash
unordered_dense - A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
sparsehash - C++ associative containers
boostdep - A tool to create Boost module dependency reports
Optional Argument in C++ - Named Optional Arguments in C++17
emhash - Fast and memory efficient c++ flat hash map/set
Hashmaps - Various open addressing hashmap algorithms in C++
robin-map - C++ implementation of a fast hash map and hash set using robin hood hashing