map_benchmark
unordered_dense
Our great sponsors
map_benchmark | unordered_dense | |
---|---|---|
5 | 12 | |
287 | 730 | |
- | - | |
5.5 | 7.1 | |
about 1 year ago | 22 days ago | |
C++ | C++ | |
MIT License | MIT License |
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_dense
- unordered_dense: A Fast & Densely Stored Hashmap And Hashset Based On Robin-Hood Backward Shift Deletion
- unordered_dense: A fast, densely stored hashmap based on backward shift deletion
-
boost::unordered standalone
That's deprecated. Use https://github.com/martinus/unordered_dense instead And yes, tell use if it's any better(it should)
-
Is there an accepted way to order qualifiers?
No, I've deprecated it because the code has become a mess, I rewrote it quite differently and with much higher code quality and more features here: https://github.com/martinus/unordered_dense
-
Effortless Performance Improvements in C++: std::unordered_map
When no ordering is necessary and the number of elements is larger than 20, nothing beats https://github.com/martinus/unordered_dense (for general use).
-
Effortless Performance Improvements in C++: std:unordered_map
https://github.com/martinus/unordered_dense
Check this one out, it's a successor to this idea. Boost also introduced a very performant flat_hash_map in 1.81
-
Fuzzing is Cool, Actually
I have an API fuzz test for a hash map here: https://github.com/martinus/unordered_dense/blob/main/test/fuzz/api.cpp
-
A container with set interface based on std::vector
That sounds a bit like ankerl::unordered_dense::set: https://github.com/martinus/unordered_dense
- Inside boost::unordered_flat_map
- martinus/unordered_dense v1.4.0: A fast & densely stored hashmap, Now with heterogeneous overloads
What are some alternatives?
robin-map - C++ implementation of a fast hash map and hash set using robin hood hashing
Hopscotch map - C++ implementation of a fast hash map and hash set using hopscotch hashing
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.
unordered - Boost.org unordered module
robin-hood-hashing - Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
parallel-hashmap - A family of header-only, very fast and memory-friendly hashmap and btree containers.
flat_hash_map - A very fast hashtable