Hash table iteration order and compiler optimizations

[Jonathan Wakely]

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.

>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.

>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.