Worst-case behaviour of hash collision with float NaN

[congma]

BPO	43475
Nosy	@tim-one, @rhettinger, @mdickinson, @serhiy-storchaka, @miss-islington, @congma
PRs	bpo-43475: Fix worst case collision behavior for NaN instances #25493 bpo-43475: Fix the Python implementation of hash of Decimal NaN #26679 [3.10] bpo-43475: Fix the Python implementation of hash of Decimal NaN (GH-26679) #26706 bpo-43475: Add what's new entry for NaN hash changes #26725 [3.10] bpo-43475: Add what's new entry for NaN hash changes (GH-26725) #26743
Files	nan_key.py: PoC for NaN-collisions and possible fix for worst-case

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2021-06-16.11:36:54.791>
created_at = <Date 2021-03-11.14:55:33.263>
labels = ['interpreter-core', '3.11', 'library', '3.10', 'performance']
title = 'Worst-case behaviour of hash collision with float NaN'
updated_at = <Date 2021-11-24.13:46:50.396>
user = 'https://github.com/congma'

bugs.python.org fields:

activity = <Date 2021-11-24.13:46:50.396>
actor = 'cwg'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2021-06-16.11:36:54.791>
closer = 'mark.dickinson'
components = ['Interpreter Core', 'Library (Lib)']
creation = <Date 2021-03-11.14:55:33.263>
creator = 'congma'
dependencies = []
files = ['49869']
hgrepos = []
issue_num = 43475
keywords = ['patch']
message_count = 40.0
messages = ['388508', '388511', '388512', '388513', '388514', '388519', '388522', '388579', '388603', '388604', '388605', '388608', '388702', '388717', '388748', '390698', '390701', '390767', '390770', '391605', '391606', '391607', '395643', '395653', '395685', '395745', '395746', '395748', '395749', '395750', '395761', '395773', '395783', '395892', '395894', '395918', '406917', '406925', '406927', '406928']
nosy_count = 8.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'serhiy.storchaka', 'miss-islington', 'cwg', 'realead', 'congma']
pr_nums = ['25493', '26679', '26706', '26725', '26743']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue43475'
versions = ['Python 3.10', 'Python 3.11']

[congma]

Summary: CPython hash all NaN values to 0. This guarantees worst-case behaviour for dict if numerous existing keys are NaN. I think by hashing NaN using the generic object (or "pointer") hash instead, the worst-case situation can be alleviated without changing the semantics of either dict or float. However, this also requires changes to how complex and Decimal objects hash, and moreover incompatible change to sys.hash_info. I would like to hear how Python developers think about this matter.

--------

Currently CPython uses the hard-coded macro constant 0 (_PyHASH_NAN, defined in Include/pyhash.h) for the hash value of all floating point NaNs. The value is part of the sys.hashinfo API and is re-used by complex and Decimal in computing its hash in accordance with Python builtin-type documentation. [0]

(The doc [0] specifically says that "[a]ll hashable nans have the same hash value.")

This is normally not a great concern, except for the worst case performance. The problem is that, since they hash to the same value and they're guaranteed to compare unequal to any compatible numeric value -- not even to themselves, this means they're guaranteed to collide.

For this reason I'd like to question whether it is a good idea to have all hashable NaNs with the same hash value.

There has been some discussions about this over the Web for some time (see [1]). In [1] the demo Python script times the insertion of k distinct NaN keys (as different objects) into a freshly created dict. Since the keys are distinct and are guaranteed to collide with each other (if any), the run time of a single lookup/insertion is roughly linear to the existing number of NaN keys. I've recreated the same script using with a more modern Python (attached).

I'd suggest a fix for this worst-case behaviour: instead of returning the hash value 0 for all NaNs, use the generic object (pointer) hash for these objects. As a PoC (also in the attached script), it roughly means

class myfloat(float):
 def __hash__(self):
 if self != self: # i.e., math.isnan(self)
 return object.__hash__(self)
 return super().__hash__(self)

This will

• keep the current behaviour of dict intact;
• keep the invariant a == b implies hash(a) == hash(b) intact, where applicable;
• uphold all the other rules for Python numeric objects listed in [0];
• make hash collisions no more likely than with object() instances (dict lookup time is amortized constant w.r.t. existing number of NaN keys).

However, it will

• not keep the current rule "All hashable nans have the same hash value";
• not be compatible with the current sys.hash_info API (requires the removal of the "nan" attribute from there and documenting the change);
• require congruent modifications in complex and Decimal too.

Additionally, I don't think this will affect module-level NaN "constants" such as math.nan and how they behave. The "NaN constant" has never been a problem to begin with. It's only the *distinct* NaN objects that may cause the worst-case behaviour.

--------

Just for the record I'd also like to clear some outdated info or misconception about NaN keys in Python dicts. It's not true that NaN keys, once inserted, cannot be retrieved (e.g., as claimed in [1][2]). In Python, they can be, if you keep the original key object around by keeping a reference to it (or obtaining a new one from the dict by iterating over it). This, I think, is because Python dict compares for object identity before rich-comparing for equality in lookdict() in Objects/dictobject.c, so this works for d = dict():

f = float("nan")
d[f] = "value"
v = d[f]

but this fails with KeyError, as it should:

d[float("nan")] = "value"
v = d[float("nan")]

In this regard the NaN float object behaves exactly like the object() instance as keys -- except for the collisions. That's why I think at least for floats the "object" hash is likely to work. The solution using PRNG [1] (implemented with the Go language) is not necessary for CPython because the live objects are already distinct.

--------

Links:

[0] https://docs.python.org/3/library/stdtypes.html#hashing-of-numeric-types
[1] https://research.swtch.com/randhash
[2] https://readafterwrite.wordpress.com/2017/03/23/how-to-hash-floating-point-numbers/

[mdickinson]

Sigh. When I'm undisputed ruler of the multiverse, I'm going to make "NaN == NaN" return True, IEEE 754 be damned. NaN != NaN is fine(ish) at the level of numerics; the problems start when the consequences of that choice leak into the other parts of the language that care about equality. NaNs just shouldn't be considered "special enough to break the rules" (where the rules here are that the equivalence relation being used as the basis of equality for a general container should actually *be* an equivalence relation - reflexive, symmetric, and transitive).

Anyway, more constructively ...

I agree with the analysis, and the proposed solution seems sound: if we're going to change this, then using the object hash seems like a workable solution. The question is whether we actually do need to change this.

I'm not too worried about backwards compatibility here: if we change this, we're bound to break *someone's* code somewhere, but it's hard to imagine that there's *that* much code out there that makes useful use of the property that hash(nan) == 0. The most likely source of breakage I can think of is in test code that checks that 3rd-party float-like things (NumPy's float64, or gmpy2 floats, or ...) behave like Python's floats.

@cong Ma: do you have any examples of cases where this has proved, or is likely to prove, a problem in real-world code, or is this purely theoretical at this point?

I'm finding it hard to imagine cases where a developer *intentionally* has a dictionary with several NaN values as keys. (Even a single NaN as a key seems a stretch; general floats as dictionary keys are rare in real-world code that I've encountered.) But it's somewhat easier to imagine situations where one could run into this accidentally. Here's one such:

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

That took around 4 minutes of non-ctrl-C-interruptible time on my laptop. (I was actually expecting it not to "work" as a bad example: I was expecting that NaNs realised from a NumPy array would all be the same NaN object, but that's not what happens.) For comparison, this appears instant:

>> x = np.random.rand(100000)
>> c = collections.Counter(x)

And it's not a stretch to imagine having a NumPy array representing a masked binary 1024x1024-pixel image (float values of NaN, 0.0 and 1.0) and using Counter to find out how many 0s and 1s there were.

On the other hand, we've lived with the current behaviour for some decades now without it apparently ever being a real issue.

On balance, I'm +1 for fixing this. It seems like a failure mode that would be rarely encountered, but it's quite unpleasant when it *is* encountered.

[mdickinson]

Hmm. On second thoughts, the proposed solution wouldn't actually *help* with the situation I gave: the elements (lazily) realised from the NumPy array are highly likely to all end up with the same address in RAM. :-(

>>> x = np.full(10, np.nan)
>>> for v in x:
... print(id(v))
... del v
... 
4601757008
4601757008
4601757008
4601757008
4601757008
4601757008
4601757008
4601757008
4601757008
4601757008

[mdickinson]

On third thoughts, of course it *would* help, because the Counter is keeping references to the realised NaN values. I think I'll go away now and come back when my brain is working.

[congma]

Thank you @mark.dickinson for the detailed analysis.

In addition to your hypothetical usage examples, I am also trying to understand the implications for user code.

If judging by the issues people open on GitHub like this: pandas-dev/pandas#28363 yes apparently people do run into the "NaN as key" problem every now and then, I guess. (I'm not familiar enough with the poster's real problem in the Pandas setting to comment about that one, but it seems to suggest people do run into "real world" problems that shares some common features with this one). There's also StackOverflow threads like this (https://stackoverflow.com/a/17062985) where people discuss hashing a data table that explicitly use NaN for missing values. The reason seems to be that "[e]mpirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation." (https://arxiv.org/pdf/0902.2206.pdf).

I cannot imagine whether the proposed change would make life easier for people who really want NaN keys to begin with. However I think it might reduce the exposure to worst-case performances in dict (and maybe set/frozenset), while not hurting Python's own self-consistency.

Maybe there's one thing to consider about future compatibility though... because the proposed fix depends on the current behaviour that floats (and by extension, built-in float-like objects such as Decimal and complex) are not cached, unlike small ints and interned Unicode objects. So when you explicitly construct a NaN by calling float(), you always get a new Python object. Is this guaranteed now on different platforms with different compilers? I'm trying to parse the magic in Include/pymath.h about the definition of macro Py_NAN, where it seems to me that for certain configs it could be a static const union translation-unit-level constant. Does this affect the code that actually builds a Python object from an underlying NaN? (I apologize if this is a bad question). But if it doesn't and we're guaranteed to really have Python NaN-objects that don't alias if explicitly constructed, is this something unlikely to change in the future?

I also wonder if there's security implication for servers that process user-submitted input, maybe running a float() constructor on some string list, checking exceptions but silently succeeding with "nan": arguably this is not going to be as common an concern as the string-key collision DoS now foiled by hash randomization, but I'm not entirely sure.

On "theoretical interest".. yes theoretical interests can also be "real world" if one teaches CS theory in real world using Python, see https://bugs.python.org/issue43198#msg386849

So yes, I admit we're in an obscure corner of Python here. It's a tricky, maybe-theoretical, but seemingly annoying but easy-to-fix issue..

[congma]

Sorry, please ignore my rambling about "float() returning aliased object" -- in that case the problem with hashing doesn't arise.

[mdickinson]

I also wonder if there's security implication for servers that process user-submitted input

Yes, the "malicious actor" scenario is another one to consider. But unlike the string hashing attack, I'm not seeing a realistic way for the nan hash collisions to be used in attacks, and I'm content not to worry about that until someone gives an actual proof of concept. Many of Python's hash functions are fairly predictable (by design!) and there are already lots of other ways to deliberately construct lots of hash collisions with non-string non-float values.

[rhettinger]

Idea: We could make this problem go away by making NaN a singleton.

[mdickinson]

We could make this problem go away by making NaN a singleton.

That could work, though we'd annoy anyone who cared about preserving NaN payloads and signs in Python. I don't know if such people exist. Currently the sign is accessible through things like math.copysign, and the payload through struct manipulations (though on most platforms we still don't see the full range of NaNs: signalling NaNs are quietly silenced on my machine).

We'd also want to do some performance checks: the obvious way to do this would be to have an "is_nan" check in PyFloat_FromDouble. I'd *guess* that a typical CPU would do a reasonable job of branch prediction on that check so that it had minimal impact in normal use, but only timings will tell for sure.