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

[Marc Mutz]

On Friday 17 July 2015 11:02:08 André Somers wrote:
> 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...

You can have that with C++11 std::*set, and a custom transparent comparator, 
but of course, they are not cache-friendly. But it's testament to the value of 
having the ability to _have_ a custom comparator. QFashHash consequently has 
that ability, but its a map, not a set, so it won't fit your use-case.

-- 
Marc Mutz <marc.mutz at kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
Tel: +49-30-521325470
KDAB - The Qt Experts