Make hash values the same width as a pointer (or Py_ssize_t)

@malemburg

BPO	9778
Nosy	@malemburg, @tim-one, @loewis, @smontanaro, @birkenfeld, @rhettinger, @mdickinson, @abalkin, @pitrou, @benjaminp, @skrah
Files	hash_t.diff hash_t.diff deunsignify.diff py_ssize_t_hash_patch.diff Py_uhash_t_patch.diff hashw64.patch

^{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 = None
closed_at = <Date 2010-10-23.19:09:16.110>
created_at = <Date 2010-09-04.22:11:29.637>
labels = ['interpreter-core', 'type-feature']
title = 'Make hash values the same width as a pointer (or Py_ssize_t)'
updated_at = <Date 2010-10-23.19:09:16.109>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2010-10-23.19:09:16.109>
actor = 'loewis'
assignee = 'none'
closed = True
closed_date = <Date 2010-10-23.19:09:16.110>
closer = 'loewis'
components = ['Interpreter Core']
creation = <Date 2010-09-04.22:11:29.637>
creator = 'pitrou'
dependencies = []
files = ['19257', '19258', '19260', '19317', '19338', '19343']
hgrepos = []
issue_num = 9778
keywords = ['patch']
message_count = 52.0
messages = ['115617', '115618', '115619', '115626', '115639', '115656', '115657', '115695', '118789', '118820', '118823', '118953', '118954', '118955', '118959', '118968', '118972', '118980', '118982', '118983', '118987', '118994', '118995', '119000', '119001', '119011', '119015', '119017', '119019', '119020', '119025', '119029', '119030', '119034', '119043', '119044', '119058', '119077', '119079', '119080', '119124', '119265', '119411', '119415', '119442', '119443', '119446', '119453', '119456', '119464', '119465', '119468']
nosy_count = 14.0
nosy_names = ['lemburg', 'tim.peters', 'loewis', 'skip.montanaro', 'georg.brandl', 'rhettinger', 'jimjjewett', 'mark.dickinson', 'belopolsky', 'pitrou', 'casevh', 'ked-tao', 'benjamin.peterson', 'skrah']
pr_nums = []
priority = 'normal'
resolution = 'accepted'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue9778'
versions = ['Python 3.2', 'Python 3.3']

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.

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

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?

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

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.

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.

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

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

I'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 66

All 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_dictviews

This patch seems to fix all aforementioned failures.

These changes also look all reasonable to me.

Ok, I've committed them in r85808.

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

The test_capi problem is not 64-bit-specific (see bpo-9116).

As for test_concurrent_futures, I also have a failure (not the same one) in both 32-bit and 64-bit builds here. I'm gonna open a separate issue.

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

Navigation Menu

Repository navigation

Make hash values the same width as a pointer (or Py_ssize_t) #53987

31 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Make hash values the same width as a pointer (or Py_ssize_t) #53987

Description

Activity

pitrou commented on Sep 4, 2010

pitrou commented on Sep 4, 2010

rhettinger commented on Sep 4, 2010

loewis commented on Sep 5, 2010

pitrou commented on Sep 5, 2010

loewis commented on Sep 5, 2010

birkenfeld commented on Sep 5, 2010

mdickinson commented on Sep 6, 2010

birkenfeld commented on Oct 15, 2010

smontanaro commented on Oct 15, 2010

pitrou commented on Oct 15, 2010

31 remaining items

mdickinson commented on Oct 19, 2010

casevh commented on Oct 21, 2010

casevh commented on Oct 23, 2010

casevh commented on Oct 23, 2010

benjaminp commented on Oct 23, 2010

pitrou commented on Oct 23, 2010

pitrou commented on Oct 23, 2010

loewis commented on Oct 23, 2010

pitrou commented on Oct 23, 2010

casevh commented on Oct 23, 2010

pitrou commented on Oct 23, 2010

loewis commented on Oct 23, 2010

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions