Repository navigation
Unified hash for numeric types. #52435
Description
| BPO | 8188 |
|---|---|
| Nosy | @rhettinger, @mdickinson, @ericvsmith, @skrah |
| Files |
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/mdickinson'
closed_at = <Date 2010-05-23.13:35:21.075>
created_at = <Date 2010-03-20.20:34:28.514>
labels = ['type-feature']
title = 'Unified hash for numeric types.'
updated_at = <Date 2010-06-11.10:51:51.694>
user = 'https://github.com/mdickinson'bugs.python.org fields:
activity = <Date 2010-06-11.10:51:51.694>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2010-05-23.13:35:21.075>
closer = 'mark.dickinson'
components = []
creation = <Date 2010-03-20.20:34:28.514>
creator = 'mark.dickinson'
dependencies = []
files = ['16604', '16608', '16610', '16629', '16675', '16756', '16782', '16907', '17437']
hgrepos = []
issue_num = 8188
keywords = ['patch']
message_count = 25.0
messages = ['101395', '101397', '101401', '101402', '101403', '101404', '101405', '101406', '101407', '101417', '101581', '101824', '102339', '102341', '102347', '102350', '102352', '102467', '103031', '103032', '103800', '103843', '106291', '106333', '107539']
nosy_count = 6.0
nosy_names = ['rhettinger', 'mark.dickinson', 'Rhamphoryncus', 'casevh', 'eric.smith', 'skrah']
pr_nums = []
priority = 'normal'
resolution = 'accepted'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue8188'
versions = ['Python 3.2']
Activity
mdickinson commentedon Mar 20, 2010
Here's a patch that makes hash(x) == hash(y) for any numeric types (int, float, complex, Decimal, Fraction, bool) when x and y are numerically equal.
This is a prerequisite for making all numeric types accurately comparable with each other.
mdickinson commentedon Mar 20, 2010
Uploaded to Rietveld:
http://codereview.appspot.com/660042
mdickinson commentedon Mar 20, 2010
Updated patch, with a bit of cleanup and some comments describing the hashing strategy; I'll update the Rietveld issue as well.
mdickinson commentedon Mar 20, 2010
Whoops; that patch included some accidental Lib/test/test_decimal changes. Here's the correct patch.
Rhamphoryncus commentedon Mar 20, 2010
Why aren't you using 64-bit hashes on 64-bit architectures?
mdickinson commentedon Mar 20, 2010
Mostly because I haven't got around to putting that in yet. :)
Ideal would be to use _PyHASH_BITS=61 for 64-bit machines, throughout.
Rhamphoryncus commentedon Mar 20, 2010
I assume you mean 63. ;)
mdickinson commentedon Mar 20, 2010
No, I mean 61. 2**61 - 1 is prime; 2**63-1 is not. (So 2 bits of the hash get wasted, but that's not a big deal, especially since they're the high-end bits and Python mostly cares about the lower-order bits.)
mdickinson commentedon Mar 20, 2010
Restore tests accidentally omitted from second patch.
mdickinson commentedon Mar 21, 2010
Updated patch:
put hash parameters into pyport.h, to avoid repetition; make them
available to Python code via a private attribute sys._hash_info.
use a modulus of 2**61-1 on systems where SIZEOF_LONG >= 8, and
a modulus of 2**31 - 1 otherwise.
remove _invmod from fractions module. It's faster (and easier) to
use 3-argument pow to compute inverses modulo a prime.
add a few more tests.
mdickinson commentedon Mar 23, 2010
Another update, partly to address comments raised by Guido on Rietveld. I'll upload these changes to Rietveld later today.
rename sys._hash_info to sys.hash_info and make it public rather than private (it still needs docs somewhere)
add some explanatory comments to long_hash; remove an outdated comment
fix missing error check (in previous patch) in slot_tp_hash. slot_tp_hash also now always raises a TypeError if __hash__ returns a non-integer; this is a change from current behaviour, which allows small floats to be returned by __hash__, but not large floats (where large means > 2**31 or > 2**63 in absolute value, depending on the system). I'm assuming this was unintentional (the docs specify that __hash__ should return an integer).
simplify specification of hash function slightly: for nonnegative x it simply computes the reduction of x; previously it computed 1 + reduction of (x-1) for positive values. This extra +-1 doesn't really add anything of value, and makes it slightly more complicated and error-prone to write your own hash function.
mdickinson commentedon Mar 27, 2010
Here's a version of the patch that adds exact comparisons between the various numeric types. The only slightly tricky comparison is the Fraction <-> Decimal one: an obvious strategy is to convert the Decimal exactly to a Fraction and then use the fraction comparison, but this is inefficient for Decimal instances with large exponent. So instead, we compare a Decimal
xwith a Fractionn/dby comparingx*dwithnin the Decimal domain.mdickinson commentedon Apr 4, 2010
New patch:
not sure whether this is the best place for it)
with instances of float, fraction.Fraction)
I think this is close to final form: I intend to apply this patch (or something very much like it) soon; any review would be appreciated.
mdickinson commentedon Apr 4, 2010
I've refreshed the Rietveld patch as well:
http://codereview.appspot.com/660042
skrah commentedon Apr 4, 2010
Mark, very nice concept! - I'm just starting to review the patch, but I
think the unsigned longs in_Py_HashDouble() and long_hash() should be
uint64_t on a 64-bit OS.
For instance, now on Windows 64-bit:
skrah commentedon Apr 4, 2010
Actually the current long_hash() is affected as well. On Windows 64-bit:
mdickinson commentedon Apr 4, 2010
Yes, hash values are C longs, regardless of platform. I think that's probably too ingrained to consider changing it (we'd have to change hashes of all the non-numeric types, too).
skrah commentedon Apr 6, 2010
I've finished reviewing the patch and I think it's quite ready to be
applied.
The documentation in stdtypes.rst says that P = 2**61-1 on 64-bit
machines. This should be changed to reflect the fact that actually
sizeof long is the deciding factor. I attach a patch that also fixes
the typo pointed out by Christophe Simonis.
mdickinson commentedon Apr 13, 2010
Many thanks for reviewing, Stefan, and for the patch.
Here's an updated patch:
was bugging me).
for the values of float('inf') and float('nan')
One unresolved issue: it would probably make sense to specify (publicly) a hash algorithm for complex types, too, so that someone implementing e.g. Gaussian integers can make their hash function agree with that for the complex type where appropriate.
That hash algorithm would probably be as simple as:
where the algorithm for the combination needs to be specified explicitly, and any relevant parameters put into sys.hash_info.
(Unfortunately, -1 doesn't have square roots modulo the prime P used, else we could do the cute thing and make use of a square root of -1 modulo P.)
Another tiny detail: I'm wondering whether hash(m/P) should care about the sign of m: currently it doesn't, which means that the symmetry hash(-x) = -hash(x) *almost* always holds for a rational x, but not always. An almost-always-true symmetry seems like a recipe for hard-to-find bugs.
mdickinson commentedon Apr 13, 2010
... and here's the actual patch... Forget my own head next. :)
casevh commentedon Apr 21, 2010
I've spent some time working through the new hash function by re-implementing it for gmpy. Very elegant design.
I like _PyHASH_MODULUS better, too.
Regarding a hash function for complex types, I think documenting the existing behavior for PyComplex is sufficient. The magic number 1000003 could be documented in hash_info as 'multiplier' and _PyHASH_MULTIPLIER. The same constant, but a different algorithm, is also used when hashing a tuple.
I think hash(m/P) should preserve sign. It just seems more symmetrical. :)
mdickinson commentedon Apr 21, 2010
Seems reasonable; I'm tempted to call the constant it hash_info.imaginary and _PyHASH_IMAGINARY, though. :)
There's also an implicit parameter in this algorithm, namely the size of a C long; I think this should go into sys.hash_info, too.
complex_hash does need fixing in one respect: it currently depends on signed overflow wrapping modulo 2**BIT_IN_LONG, but that's undefined behaviour; it should use unsigned arithmetic instead.
Agreed. Along similar lines, I think I'm also going to get rid of _PyHASH_NINF and just use -PyHASH_INF instead.
mdickinson commentedon May 22, 2010
Updated patch:
drop sys.hash_info.bits (the exponent of the Mersenne prime);
it's not needed in the Python code, and it can be deduced from
the prime itself if necessary. This also means that there's no
public requirement that the prime be a Mersenne prime.
drop sys.hash_info.ninf; just use -sys.hash_info.inf instead
add sys.hash_info.width: the underlying width in bits for hashes
of all descriptions; in other words, it's just the number of bits
in a C long in the current implementation
add sys.hash_info.imag, the multiplier used for the imaginary
part of a complex number
mdickinson commentedon May 23, 2010
Committed the hash changes in r81486. This commit just changes the method for computing hash values; it doesn't include the changes to the decimal module that make Decimal instances comparable with Fraction instances.
mdickinson commentedon Jun 11, 2010
Committed the Decimal-to-Fraction comparisons in r81893. All numeric types should now compare nicely with each other.