hash policy patch

[Paolo Carlini]

On 09/06/2011 09:03 PM, François Dumont wrote:
> On 09/01/2011 08:36 PM, Paolo Carlini wrote:
>> Hi,
>> Today, I had time to look a bit more into these issues. I think we
>> should handle one change at a time. About the first one above, I don't
>> like the new __strict parameter, looks like we are going through this
>> complication only because we are refactoring to use _M_next_bkt, because
>> otherwise, if I understand correctly, we are not really incorrect, since
>> we are talking about something like *strict* equality of *floating*
>> point quantities, by itself something badly defined (indeed, carefully,
>> the standard talks about "keeping the load factor below this number", 
>> using plain English, not a formula).
> Hi
>
>     What do you mean by the fact that there is no formula ? Is it that 
> checking at any moments that for a given unordered container uc:
>
> assert( uc.load_factor() < uc.max_load_factor() )
I meant that the Standard, not accidentally, does *not* use a formula, 
because it is well known that strict equality of floating point numbers 
is badly defined. At some point you said you wanted to fix things to 
avoid equality, and I maintain that "keeping the load factor below this 
number", as the Standard says, is actually indistinguishable from 
"keeping the load factor below or equal to this number", when floating 
point numbers are involved.
>     I ask because I kept on studying this issue and found that we also 
> have an other issue. When we compute the policy _M_next_resize we use:
>
>     _M_next_resize = static_cast<std::size_t>(__builtin_floor(__p * 
> _M_max_load_factor));
>
>     But doing so we transform an unsigned long __p into a float value 
> losing information if __p is larger than float mantissa. The resulting 
> _M_next_resize might be in fact too large and the policy will request 
> a rehash after the load_factor has started to be greater than 
> max_load_factor. Raising the operation in double delay this effect to 
> a very large number of buckets but is it enough to consider that it is 
> not an issue anymore ?
Sure, we can use a double (I can do that as part of the patch I posted 
today), seems a good idea. Note that the unordered containers code, at 
first had already some issues with 32-bit vs 64-bit: for sure the issue 
you are pointing out is much less noticeable with 32-bit longs.

Paolo.