[Development] QHash for Qt 6

[Lars Knoll]

On 20 Dec 2019, at 11:47, Giuseppe D'Angelo via Development <development at qt-project.org<mailto:development at qt-project.org>> wrote:

Il 20/12/19 09:23, Lars Knoll ha scritto:
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.

Just to be devil's advocate, there is... As much as it's fun and everything implementing a container, just using std::unordered_map would have minimal effort on our side ("someone else's problem", and it's not even a random 3rd party, but a mandatory prerequisite for building Qt), and we can put in our API move-conversion between QHash / std::unordered_map.

I’m in principle not against using std containers for our implementation (I brought up the idea before), but have a look at https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html and tell me why we’d want the std implementation? It has some serious drawbacks in terms of memory usage and performance, and they can’t be fixed because some of the API forces a certain type of implementation.

And I honestly can see very little to no use cases where you’d need to move from a QHash to a std::unordered_map or back.


I stopped thinking that Qt should provide "special" data structures (and for sure we should kill any QHash/QMap usage in our APIs); QHash can be as bad (or as good) as std::unordered_map, and if people need something more tailored for their use cases, there's plenty of 3rd parties to choose from. Or is there a political agenda here trying to promove QHash usage? :-)

We use QHash all over the place in Qt. A better implementation will also speed up our own code and reduce our own memory use.

Is the plan to also have QMap be backed by an hybrid solution (array-backed, etc.), or std::map, or something else?

My first assumption would be std::map, but I think we should do some similar benchmarks as the one from tessil above for hash tables before making a decision.

Cheers,
Lars

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20191220/1628921c/attachment.html>