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 <[email protected]> | Senior Software Engineer KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company Tel: +49-30-521325470 KDAB - The Qt Experts _______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
