Repository navigation
Make hash values the same width as a pointer (or Py_ssize_t) #53987
Description
Activity
Currently, Python produces hash values with fit in a C "long". This is fine at first sight, but in the context of dict and set implementations, it means that
- holding hashes and indices in the same field of a structure requires some care (see bpo-1646068)
- on platforms where a long is smaller than a Py_ssize_t (e.g. Win64), very big hash tables could suffer from lots of artificial collisions (the hash table being bigger than the range of possible hash values)
- when a long is smaller than Py_ssize_t, we don't save any size anyway, since having some pointers follow a C "long" in a structure implies some padding to keep all fields naturally aligned
A future-proof option would be to change all hash values to be of Py_ssize_t values rather than C longs. Either directly, or by defining a new dedicated alias Py_hash_t. This would also impact the ABI, I suppose.
As an example of padding behaviour (under Win64 with 32-bit longs and 64-bit pointers):
Python 3.2a1+ (py3k, Sep 4 2010, 22:50:10) [MSC v.1500 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information. >>> import struct >>> struct.calcsize("l") 4 >>> struct.calcsize("lP") 16 >>> struct.calcsize("lPP") 24
+1 for PyObject_Hash returning a Py_ssize_t.
Nothing good can come from having a hash table larger than the range of a hash value. Tests may pass but performance would degrade catastrophically.
loewis commented
on Sep 5, 2010 loewismannequinMannequinThis would also impact the ABI, I suppose.
Correct. So it either needs to happen before 3.2, or wait until 4.0,
or the introduction of "wide" hashes needs to be done in a compatible
manner, likely requiring two parallel hashing infrastructures.- changed the title
[-]Make hash values the same width as a pointer (or Py_ssize_t)[/-][+]Make hash values the same width as a pointer (or Py_ssize_t)[/+]on Sep 5, 2010 Correct. So it either needs to happen before 3.2, or wait until 4.0,
Shouldn't there be a provision for ABI versioning?
Or do you suggest bumping to the next major number (4.0, 5.0...) be done on the basis of ABI changes?loewis commented
on Sep 5, 2010 loewismannequinMannequinAm 05.09.2010 13:12, schrieb Antoine Pitrou:
Antoine Pitrou <pitrou@free.fr> added the comment:
> Correct. So it either needs to happen before 3.2, or wait until 4.0,
Shouldn't there be a provision for ABI versioning?
There is certainly support for ABI versioning; the ABI version defined
in the PEP is called "python3.dll".Or do you suggest bumping to the next major
number (4.0, 5.0...) be done on the basis of ABI changes?No, vice versa. The PEP promises that the ABI won't change until Python
4. For any change that might break the ABI, either a
backwards-compatible solution needs to be found, or the change be
deferred to Python 4.- changed the title
[-]Make hash values the same width as a pointer (or Py_ssize_t)[/-][+]Make hash values the same width as a pointer (or Py_ssize_t)[/+]on Sep 5, 2010 I would suggest making this change before the ABI freeze starts, then.
... change all hash values to be of Py_ssize_t values rather than C longs ...
Yes, please! (Provided this change can go in before 3.2.) For the numeric types at least, this should be a straightforward adjustment.
And while we're at it, we could clean up some of the undefined behaviour from integer overflow that's in the current hash functions (tuple.__hash__, for example).
Ping?
Not that anybody needs my input on this, but...
Given the range of people advocating for this change, this looks to me
like it should be a release blocker for 3.2. Raymond's comment about
performance seems especially important, and since the world seems to
be moving toward 64-bit operating systems (certainly should happen in
a big way during the lifetime of Python 3) it seems worthwhile to hold
up further 3.2 releases until this is solved.Given the range of people advocating for this change, this looks to me
like it should be a release blocker for 3.2. Raymond's comment about
performance seems especially important, and since the world seems to
be moving toward 64-bit operating systems (certainly should happen in
a big way during the lifetime of Python 3) it seems worthwhile to hold
up further 3.2 releases until this is solved.I think this is a bit exagerated. The performance issues will only
appear if you have huge dicts and sets.
The issue Raymond raised is the potential impossibility of making the
change /after/ we settle on a stable ABI. The question is whether the
ABI will be enforced starting from 3.2, or from a later date.31 remaining items
The calculation of long_hash assumes an unsigned temporary type to get
correct results for the bit shifting and masking.Yes, exactly.
The calculation is
done on the absolute value of the long and then the sign is applied. We
either needed to (1) add an unsigned Py_hash_t type or (2) just use
size_t and Py_ssize_t.I like (2); the use of Py_hash_t suggests to me that the type used for the hash is configurable independently of Py_ssize_t, which isn't true.
Also, with Py_hash_t it's no longer clear that printing a hash value (e.g., using PyErr_Format and friends) should use the '%zd' modifier.
casevh commented
on Oct 21, 2010 casevhmannequinMannequinI've attached a patch that fixes hashing for numerical types, sys.hash_info is now correct, fixes typeobject.c/wrap_hashfunc and tupleobject.c/tuplehash to use Py_ssize_t instead of long, and uses Py_ssize_t instead of Py_hash_t.
I think it is clearer to use Py_ssize_t instead of Py_hash_t. I found two occurances where PyLong_FromLong needed to be replaced by PyLong_FromSsize_t and I think bugs like that would be easier to catch if Py_ssize_t is used.
casevh commented
on Oct 23, 2010 casevhmannequinMannequinI maintain gmpy and it needs to calculate hash values for integers, floats, and rationals. I converted my hash calculations to use Py_ssize_t in a 64-bit Windows enviroment. All my tests pass when I build Python with my previous patch.
In hindsight, I think I made a mistake in my previous patch by eliminating Py_hash_t and using Py_ssize_t/size_t. I ended up defining Py_hash_t and Py_uhash_t in gmpy to simplify the code and to easily support older versions of Python.
I will work on a patch that defines Py_hash_t and Py_uhash_t and upload it later this evening.
casevh commented
on Oct 23, 2010 casevhmannequinMannequinI've uploaded a patch against the current svn trunk that:
- Defines a Py_uhash_t as equivalent to size_t.
- Correctly defines _PyHASH_MODULUS on Win64.
- Replaces several PyLong_FromLong with PyLong_FromSsize_t.
- Change typeobject/wrap_hashfunc to use Py_hash_t instead of long.
- Change tupleobject/tuplehash to use Py_hast_t instead of long.
- Change long/double/complex hash functions to use Py_uhash_t instead of unsigned long.
Thank you. Applied in r85803.
Case's patch fixes test_builtin and test_complex failures on Windows 7 64-bit. But there's still a failure in test_dictviews:
======================================================================
FAIL: test_items_set_operations (test.test_dictviews.DictSetTest)
----------------------------------------------------------------------Traceback (most recent call last): File "Z:\__svn__\lib\test\test_dictviews.py", line 153, in test_items_set_operations {('a', 1), ('b', 2)}) AssertionError: Items in the first set but not the second: ('a', 1) ('b', 2)
Which boils down to the following issue:
>>> d1 = {'a': 1, 'b': 2} >>> d1.items() dict_items([('a', 1), ('b', 2)]) >>> set(d1.items()) {('a', 1), ('b', 2)} >>> d1.items() | set(d1.items()) {('a', 1), ('a', 1), ('b', 2), ('b', 2)}
There are also a bunch of possibly related failures in test_weakset:
======================================================================
FAIL: test_inplace_on_self (test.test_weakset.TestWeakSet)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_weakset.py", line 293, in test_inplace_on_ self self.assertEqual(t, self.s) AssertionError: <_weakrefset.WeakSet object at 0x000000000283CDC0> != <_weakrefs et.WeakSet object at 0x000000000283B2C8>
======================================================================
FAIL: test_or (test.test_weakset.TestWeakSet)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_weakset.py", line 72, in test_or self.assertEqual(self.s | set(self.items2), i) AssertionError: <_weakrefset.WeakSet object at 0x000000000285B400> != <_weakrefs et.WeakSet object at 0x000000000285B260>
======================================================================
FAIL: test_symmetric_difference (test.test_weakset.TestWeakSet)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_weakset.py", line 110, in test_symmetric_d ifference self.assertEqual(c in i, (c in self.d) ^ (c in self.items2)) AssertionError: False != True
======================================================================
FAIL: test_union (test.test_weakset.TestWeakSet)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_weakset.py", line 61, in test_union self.assertEqual(c in u, c in self.d or c in self.items2) AssertionError: False != True
======================================================================
FAIL: test_xor (test.test_weakset.TestWeakSet)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_weakset.py", line 117, in test_xor self.assertEqual(self.s ^ set(self.items2), i) AssertionError: <_weakrefset.WeakSet object at 0x000000000292CA18> != <_weakrefs et.WeakSet object at 0x000000000292C878>
Another bunch of test_pyclbr failures:
======================================================================
FAIL: test_decorators (test.test_pyclbr.PyclbrTest)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 152, in test_decorators self.checkModule('test.pyclbr_input', ignore=['om']) File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 101, in checkModule self.assertListEq(real_bases, pyclbr_bases, ignore) File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 28, in assertListEq self.fail("%r missing" % missing.pop()) AssertionError: 'object' missing
======================================================================
FAIL: test_easy (test.test_pyclbr.PyclbrTest)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 142, in test_easy self.checkModule('pyclbr') File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 101, in checkModule self.assertListEq(real_bases, pyclbr_bases, ignore) File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 28, in assertListEq self.fail("%r missing" % missing.pop()) AssertionError: 'object' missing
======================================================================
FAIL: test_others (test.test_pyclbr.PyclbrTest)
----------------------------------------------------------------------Traceback (most recent call last): File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 158, in test_others cm('random', ignore=('Random',)) # from _random import Random as CoreGenera tor File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 101, in checkModule self.assertListEq(real_bases, pyclbr_bases, ignore) File "Y:\py3k\__svn__\lib\test\test_pyclbr.py", line 28, in assertListEq self.fail("%r missing" % missing.pop()) AssertionError: 'Random' missing
And a test_sys failure which is probably easy to fix:
File "Z:\svn\lib\test\test_sys.py", line 831, in test_objecttypes
check(s, basicsize)
File "Z:\svn\lib\test\test_sys.py", line 601, in check_sizeof
self.assertEqual(result, size, msg)
AssertionError: wrong size for <class 'str'>: got 74, expected 66All these tests pass in 32-bit mode.
Case, you can run the regression test suite with:
python.exe -m test.regrtest
and invidual tests with e.g.:
python.exe -m test.regrtest -v test_dictviewsThis patch seems to fix all aforementioned failures.
loewis commented
on Oct 23, 2010 loewismannequinMannequinThese changes also look all reasonable to me.
Ok, I've committed them in r85808.
casevh commented
on Oct 23, 2010 casevhmannequinMannequinOn Win64, I get two unexpected failures:
I terminated test_capi after a Windows exception box popped up.
[ 37/349] test_capi test test_capi failed -- Traceback (most recent call last): File "C:\svn\py3k\lib\test\test_capi.py", line 50, in test_no_FatalError_infinite_loop b'Fatal Python error:' AssertionError: b"Fatal Python error: PyThreadState_Get: no current thread\r\n\r\nThis application has requested the Runtime to term inate it in an unusual way.\nPlease contact the application's support team for more information." != b'Fatal Python error: PyThreadS tate_Get: no current thread' [ 67/349] test_concurrent_futures test test_concurrent_futures failed -- Traceback (most recent call last): File "C:\svn\py3k\lib\test\test_concurrent_futures.py", line 442, in test_timeout future1]), finished) AssertionError: Items in the second set but not the first: <Future at 0x5510fd0 state=finished raised AssertionError>
The dictviews test passes successfully.
loewis commented
on Oct 23, 2010 loewismannequinMannequinI recommend to declare this issue closed, and keep it closed unless somebody wants to propose to revert the change (widening the hash type) completely. Any remaining issues that people want to attribute to this change (correctly or incorrectly) should be reported as separate issues.
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:
bugs.python.org fields: