libstdc++/41975

[François Dumont]

On 11/14/2011 10:08 PM, Christopher Jefferson wrote:
> On 14 Nov 2011, at 20:48, François Dumont wrote:
>
>>     Here is as promise my latest proposal. This time there is no memory overhead except that hash code are now cached per default
> Not that I'm saying your idea is bad, am I right in thinking that approximately doubles the size of the table (for small types like int)?
>
> Chris
     If you had follow the whole story you would have seen that I even 
proposed temporarily to add almost 2 pointers in addition to the hash 
code. You should be happy with only the hash code :-).

     But we do not really have the choice, the Standard allow the hash 
functor to throw, with the new data structure allowing good performance 
we need to compute the hash code in erase method which is not supposed 
to throw so we need to cache the hash code. Moreover the new data 
structure also have all nodes linked to each other in a singly linked 
list. It means that there is no more sentinel to detect the bucket last 
node and so we need to access hash code very often to know if we are 
still in the correct bucket. You see this problem in the performance 
test, when using unordered_set<string> performances are better when hash 
code is cached, for unordered_set<int> there is almost no difference.

     The good news is that we can avoid this overhead for small types 
like int because caching or not the hash code is just a matter of 
setting a flag to true or false. I will make this flag default value 
depending on the key type.

Thanks for the feedback