+10 It's excellent because it behaves very well in multiple scenarios, which is uncommon for a hash map. And according to your design, it should perform equally well with very small maps. And all that under 1000 lines of code, this is brillant (BTW, you need to #include <array> in qthash.h)
Given the fact that maps are used in so many places, this would be a major addtion to Qt6 Though this is not the same thing, your optimized memory layout design recalls me the recent ordered map implementation of abseil https://abseil.io/blog/20190812-btree Philippe On Fri, 20 Dec 2019 08:23:34 +0000 Lars Knoll <[email protected]> wrote: > Hi, > > Ive been playing around with QHash during our recent Hackathon at The Qt > Company. I started with measuring and comparing our implementation with > various others that are out there using the benchmark thats described here: > https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html. > > The result was that QHash has clear weaknesses compared to other > implementations. It uses too much memory and certainly isnt the fastest > implementation. But std::unordered_map is just as bad, so theres no point in > using that to implement QHash. > > After looking into it and some of the ideas behind googles and tessils spare > map implementations, I got an idea how to possibly improve on those and > implement a hash table thats both very fast and greedy on memory. > > The result can be found at https://git.qt.io/laknoll/qt6hash. For now it only > implements QHash and not QMultiHash and its still lacking some APIs such as > emplace(), but it does implement the data structure. > > Performance is pretty much on par with the best hash tables I could find out > there, memory usage is a few percent higher than the tsl_sparse_map (which is > using least memory of them all). You can find some benchmark results in my > repository in the results folder. > > Im pretty happy with the results, and would like to move ahead and finish > the implementation, so that we get a state of the art hash table > implementation for QHash in Qt 6. > > Let me know what you think :) > > Cheers, > Lars > > _______________________________________________ > Development mailing list > [email protected] > https://lists.qt-project.org/listinfo/development _______________________________________________ Development mailing list [email protected] https://lists.qt-project.org/listinfo/development
