Unordered container insertion hints

[François Dumont]

Hi

     Any news regarding this patch ?

Thanks

François


On 06/06/2013 10:33 PM, François Dumont wrote:
> 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
>