Possible excessive hash collisions from hash of nan

[mdickinson]

A potential performance issue relating to hash collisions from distinct NaNs was recently reported and fixed in core Python. In brief, the fact that all NaNs hash to 0 makes it easy to accidentally invoke quadratic-time behaviour from NaNs going into a set or dictionary. The fix involved changing the hash of a float NaN to match the usual object hash.

The core issue affects NumPy, too (and in fact one of the examples given in the Python bug report to demonstrate the issue used np.float64 rather than float); NumPy may want to consider changing the hash of floating-point NaNs, both to address the potential performance issue, and to remain compatible with Python.

Reproducing code example:

The following code takes several hours to execute on my machine:

>>> import collections, numpy as np
>>> x = np.full(1000000, np.nan)
>>> c = collections.Counter(x)

The cause is that (a) the float64 NaN objects realised from the array all have distinct id, and so are considered unequal for the purposes of dict and set membership, together with (b) all of those NaNs have the same hash value of 0. Then we get a perfect storm of hash collisions while building the dictionary underlying the Counter object.

NumPy/Python version information:

>>> import sys, numpy; print(numpy.__version__, sys.version)
1.20.2 3.9.4 (default, Apr  6 2021, 11:23:37) 
[Clang 11.0.3 (clang-1103.0.32.62)]

[seberg]

While I am never sure that returning a hash for NaN is good, that would be a silly discussion now (EDIT: well, I guess the singleton solution to the problem is likely better but it all comes with its own set of issues). Changing the hash to return id() sounds like it will not modify any behaviour but avoid excessive collisions, so we should do it.

[seberg]

Removing the milestone, we just use _PyDouble_Hash in NumPy, since Python changed the signature on the main branch, this is bound to be fixed as soon as the alpha releases with the change sail in.