Unordered container insertion hints

[François Dumont]

On 05/24/2013 01:00 AM, Paolo Carlini wrote:
> On 05/23/2013 10:01 PM, François Dumont wrote:
>> Some feedback regarding this patch ?
> Two quick ones: what if the hint is wrong? I suppose the insertion 
> succeeds anyway, it's only a little waste of time, right?

Right.

> Is it possible that for instance something throws in that case and 
> would not now (when the hint is simply ignored)? In case, check and 
> re-check we are still conforming.
I consider the hint only if it is equivalent to the inserted element so 
I invoke the equal_to functor for that. The invocation of the equal_to 
functor is already done if no hint is granted at the same location. So 
usage of the hint has no impact on exception safety.
>
> In any case, I think it's quite easy to notice if an implementation is 
> using the hint in this way or a similar one basing on some simple 
> benchmarks, without looking of course at the actual implementation 
> code. Do we have any idea what other implementations are doing? Like, 
> eg, they invented something for unordered_set and map too? Or a better 
> way to exploit the hint for the multi variants?

     I only bench llvm/clang implementation and notice no different with 
or without hint, I guess it is simply ignored. I haven't plan to check 
or bench other implementations. The usage of hint I am introducing is 
quite natural considering the new unordered containers data model. And 
if anyone has a better idea to deal with it then he is welcome to 
contribute !

> Eventually I suppose we want to add a performance testcase to our 
> testsuite.
Good request and the reason why it took me so long to answer. Writing 
such benchmark have shown me that users should be very careful with it 
cause it can do more bad than good.

unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions w/o 
hint     120r  120u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions with 
any hint     130r  130u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions with 
good hint      54r   54u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions with 
perfect hint      36r   36u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions w/o 
hint      40r   40u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions with 
any hint      38r   38u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions with 
bad hint      49r   50u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions with 
perfect hint      34r   35u    0s 64000016mem    0pf

     The small number represents how many time the same element is 
inserted and the big one the number of different elements. 100 X 20000 
means that we loop 100 times inserting the 20000 elements during each 
loop. 20000 X 100 means that the main loop is on the elements and we 
insert each 100 times. Being able to insert all the equivalent elements 
at the same time or not has a major impact on the performances to get 
the same result. This is because when a new element is inserted it will 
be first in its bucket and the following 99 insertions will benefit from 
it even without any hint.

     The bench also show that a bad hint can be worst than no hint. A 
bad hint is one that once used require to check that next bucket is not 
impacted by the insertion. To do so it requires a hash code computation 
(if it is not cached like in my use case) and check. I have added a word 
about being able to check performance before using hints. Here is the 
result using the default std::hash<std::string>, hash code is being cached.

unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions w/o 
hint      76r   76u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions with 
any hint      83r   83u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions with 
good hint      29r   29u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 100 X 20000 insertions with 
perfect hint      24r   23u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions w/o 
hint      27r   26u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions with 
any hint      24r   24u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions with 
bad hint      27r   27u    0s 64000016mem    0pf
unordered_multiset_hint.cc    unordered_set 20000 X 100 insertions with 
perfect hint      23r   23u    0s 64000016mem    0pf

Almost no impact in this case when using a bad hint. I consider adding 
another condition to the use of the hint which is to have the element 
after the hint also equivalent to the inserted element. This way we are 
sure that next bucket won't be affected and do not need to compute a 
hash code. But the result was a rather counter-intuitive hint. To get a 
good one you had to do:

std::unordered_multiset<std::string> ums;
const std::string foo("foo");
ums.insert(foo);
auto hint = ums.insert(foo);
ums.insert(hint, foo);

     it means keeping the second insertion iterator as the best hint to 
insert foo string. Not very convenient to use in real life and quite 
error prone cause if you keep the first insertion hint then you get 
stuck with the worst hint ever !

Compared to the previous patch I have just added some __builtin_expect 
cause hint are not likely to be used very often.

Tested under Linux x86_64, ok to commit ? With or without doc ?

2013-06-06  François Dumont <fdumont@gcc.gnu.org>

     * include/bits/hashtable_policy.h (_Insert_base): Consider hint in
     insert methods.
     * include/bits/hashtable.h: Likewise.
     * testsuite/23_containers/unordered_multimap/insert/hint.cc: New.
     * 
testsuite/performance/23_containers/insert/unordered_multiset_hint.cc:
     New.
     * doc/xml/manual/containers.xml: Document hinting in unordered
     containers.

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hinting.patch
Type: text/x-patch
Size: 26288 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20130606/7b0d34a2/attachment.bin>