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

[pitrou]

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']

[pitrou]

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

1. holding hashes and indices in the same field of a structure requires some care (see bpo-1646068)
2. 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)
3. 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.

[pitrou]

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

[rhettinger]

+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]

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.

[pitrou]

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]

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.

[birkenfeld]

I would suggest making this change before the ABI freeze starts, then.

[mdickinson]

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

[birkenfeld]

Ping?

[smontanaro]

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.

[pitrou]

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.