This project delivers LP3, a replacement for std::unordered_map that has better performance
across the board except lookups where the key and value types are equal to or smaller than 32 bit integers.
It is a map based on linear probing.
This project started as a design project for college, where I chose to create an STL compatible hashmap that performs better than std::unordered_map at lookups. It also had to be as close to a drop in replacement for unordered_map as possible, emulating its behaviour (outside of performance, of course) as best as it could.
Just copy LPmap3.h, fastmod3.h, and plf_colony.h to a folder,
and include "./path/to/location/LPmap3.h" where you normally would include <unordered_map>
Where you would use
#include <unordered_map>
// ........
std::unordered_map<int, int> my_map;
you now use
#include "path/to/LPmap3.h"
// ........
LP3<int, int> my_map;
Like the design goals mention, it has to be as close as possible to std::unordered_map. Unfortunately, I was not able to archive full compatibility with it. The following things differ from std::unordered_map:
- There are no iterators to buckets
begin(size_t bucket_n), cbegin, end and cend member functions. The default map allows you to iterate over the buckets where each element has the same hash. Since this map doesn't use seperate chaining, buckets have 1 element. Instead of implementing it with slightly differing behaviour, which might result in bugs, I chose not to implement it. - There are no merge and extract member functions. unordered_map, being node based, can easily transfer ownership without invalidating references. This map, not being one, can't do it as easily without heavy redesign.
To Be Added Later
It compiles on clang 11 and 12, and GCC 10 and 11. It passes all tests when compiling for C++11, C++14, C++17 and C++20, although most of the dev work has been done with C++17 as the target.
This map is mostly a proof of concept, and is provided as is. I don't foresee myself working on this in the future. I probably will respond to issues and bug reports, but it will never be a priority. The test suite is not close to exhaustive, so take that however you will.
This project is licensed under GPLv3. Also, I am not sure where to put this, but plf_colony, one of the dependencies is licenced under zlib, which require me to state changes made to it. I added my bucket interface as a friend class to plf::colony::iterator
with perf:
sudo perf record -e cache-misses,branch-misses ./LP-profiling
sudo report
with gproftools:
don't forget to link profiling to the target
env CPUPROFILE=LP-profiling.prof ./LP-profiling
pprof ./LP-profiling ./LP-profiling.prof
- Decrease bucket size by removing as much redundant info from colony's iterator
- Write more comperhensive test suite
- look for more performance improvements
- find better after hashing function