[Development] Container benchmark was HEADS UP: Don't use QList, use Q_DECLARE_TYPEINFO

André Somers andre at familiesomers.nl
Fri Jul 17 11:02:08 CEST 2015


Marc Mutz schreef op 17-7-2015 om 11:09:
> On Thursday 16 July 2015 23:09:55 Gunnar Roth wrote:
>>> About QFastHash: that is WIP. It's the very rudimentary beginnings of an
>>> open- addressing hash container (a hash container using consecutive
>>> memory, not nodes).
>>>
>>>
>> What was the idea behind it? Is so much slower than any other that I can
>> just see why anyone should want to have this? What is the advantage?
> The idea is to implement https://en.wikipedia.org/wiki/Open_addressing with
> linear probing, which theoretically should be more cache friendly than a node-
> based container (less memory overhead, cache-friendly probing).
>
> But I separated key and values into different containers, so even at optimum,
> you get two cache hits instead of one with QHash. As Ossi pointed out in the
> review, that's probably a pessimisation unless you have a very loaded
> container. Likewise, Optional<T>, required to mark entries as empty or
> occupied, isn't optimized at all. all but doubling the space required for most
> keys because of the pairing with a bool.
>
> As I said, it's WIP.
>
What might also be a consideration when making a container like this, is 
that I find the key is often (not always of course) already part of the 
value data structure. For instance, if I store employee records and key 
them by id, that id is also in the record itself. It would be nice to 
have a fast and friendly key-based container that could handle that 
without duplicating the data...

André




More information about the Development mailing list