[Development] QHash for Qt 6
Ville Voutilainen
ville.voutilainen at gmail.com
Fri Dec 20 10:32:18 CET 2019
On Fri, 20 Dec 2019 at 10:25, Lars Knoll <lars.knoll at qt.io> wrote:
>
> Hi,
>
> I’ve 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 that’s 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 isn’t the fastest implementation. But std::unordered_map is just as bad, so there’s 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 that’s 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 it’s 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.
>
> I’m 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 :)
Looks good, go right ahead with the rest of the implementation.
More information about the Development
mailing list