Still no chance to have a look ?
I think that that patch is a really safe one. Those that do not use
hint won't be impacted. Those that are already using it without any
reason might experiment a small performance issue if they found the way
to always use the worst possible hint.
François
On 06/12/2013 10:12 PM, François Dumont wrote:
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 <fdum...@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
