map_benchmark
unordered
Our great sponsors
map_benchmark | unordered | |
---|---|---|
5 | 10 | |
287 | 53 | |
- | - | |
5.5 | 9.2 | |
about 1 year ago | about 15 hours 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.
map_benchmark
-
Optimizing Open Addressing
I tied adding the maps to the [1] benchmark, but I wasn't able to, since they aren't type generic yet. You may want to benchmark against [2], and [3] which are the best performing ones in the above benchmark.
[1] https://github.com/martinus/map_benchmark/
[2] https://github.com/TheNumbat/hashtables/blob/main/code/robin...
[3] https://github.com/ktprime/ktprime
-
Benchmarking my data structure
In any case, I guess you can find some inspiration in this comparison of maps which was posted to /r/cpp a couple of months ago: https://martin.ankerl.com/2022/08/27/hashmap-bench-01/ (source code for the benchmark seems to be on https://github.com/martinus/map_benchmark ). It's made for maps but adjusting most benchmarks for other containers should be fairly straightforward.
-
Is there a committee paper on a "simplified" random interface?
There is no such thing as best random generator. They have so many different properties, e.g. is it cryptographic secure, how large is the state, how fast on x86 architecture, can it jump forward, etc. My go-to generator is sfc64 because it's fast, simple, and seems to produce high quality random numbers. Here is one implementation: https://github.com/martinus/map_benchmark/blob/master/src/app/sfc64.h other popular generators are PCG and xorshift
-
boost::unordered map is a new king of data structures
I've implemented this PoolAllocator which does exactly this: https://github.com/martinus/map_benchmark/blob/master/src/app/pool.h
-
Development Plan for Boost.Unordered
Hi Martin, thanks for the pointer! BTW, I think we may use your impressive benchmark suite to test our advances once we come up with something worth deep testing.
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?
robin-map - C++ implementation of a fast hash map and hash set using robin hood hashing
flat_hash_map - A very fast hashtable
unordered_dense - A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
FetchBoostContent - CMake FetchContent for Boost libraries
Hopscotch map - C++ implementation of a fast hash map and hash set using hopscotch hashing
parallel-hashmap - A family of header-only, very fast and memory-friendly hashmap and btree containers.
robin-hood-hashing - Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
emhash - Fast and memory efficient c++ flat hash map/set
STC - A modern, user friendly, generic, type-safe and fast C99 container library: String, Vector, Sorted and Unordered Map and Set, Deque, Forward List, Smart Pointers, Bitset and Random numbers.
boostdep - A tool to create Boost module dependency reports