Hash table iteration order and compiler optimizations

[François Dumont]

On 3/21/19 10:43 AM, Jonathan Wakely wrote:
> On 21/03/19 09:50 +0100, Florian Weimer wrote:
>> Is it acceptable if the hash table iteration order depends on compiler
>> optimizations (and other compiler implementation details)?
>
> Yes, I think so.


What do you mean by iteration order ? Just how you iterate over the 
hashtable content ?

If so the std name is std::unordered_*, this is not for nothing :-)


>
>> I'm concerned that the use of floating point in the hash policy has
>> such an effect.
>>
>> For example, in bits/hashtable_policy.h, _Prime_rehash_policy contains
>> this:
>>
>> Â Â  // Return a bucket count appropriate for n elements
>> Â Â  std::size_t
>> Â Â  _M_bkt_for_elements(std::size_t __n) const
>> Â Â  { return __builtin_ceil(__n / (long double)_M_max_load_factor); }
>
>
>> It should probably use __builtin_ceill to avoid an excess precision
>> issue on i386.
>
> Ah yes.
>
>> There's also the matter of using long double, which differs from
>> architecture to architecture.  Arithmetic on float and double should
>> be much more uniform across architectures.
>
> I don't know why the calculations were changed to use long double.
> That happened in r178615. Maybe François or Paolo remembers.
>
> It looks like they used to use ceil and floor with floats, now they
> use ceil and floor with long doubles.

 Â Â Â  AFAIR float computation was simply too limited and we were not able 
to respect the load factor constraint. I even think (or hope) that if 
you change it back to float operations some tests will start to fail.

 Â Â Â  Note that I have several patches regarding hashtable awaiting stage 
1. One is related to hash policy but doesn't change this point.


>
>> Unfortunately, getting matching behavior between i386 and x86-64 on
>> the one hand, and getting consistent behavior across more
>> architectures are conflicting goals in this case, I think.
>
> Yes, but I don't think behaviour needs to be consistent. The iteration
> order is not required to be reproducable from run to run, or when
> rehashing happens in different translation units that inline the code
> and get different results.
>
>