From c1f5c903a7e4ed27190488f4e33b00d3c3d952e5 Mon Sep 17 00:00:00 2001 From: Yury Selivanov Date: Mon, 23 May 2022 12:09:59 -0700 Subject: gh-93065: Fix HAMT to iterate correctly over 7-level deep trees (GH-93066) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Also while there, clarify a few things about why we reduce the hash to 32 bits. Co-authored-by: Eli Libman Co-authored-by: Yury Selivanov Co-authored-by: Łukasz Langa --- Python/hamt.c | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'Python/hamt.c') diff --git a/Python/hamt.c b/Python/hamt.c index c3cb4e6fda4..908c2531870 100644 --- a/Python/hamt.c +++ b/Python/hamt.c @@ -409,14 +409,22 @@ hamt_hash(PyObject *o) return -1; } - /* While it's suboptimal to reduce Python's 64 bit hash to + /* While it's somewhat suboptimal to reduce Python's 64 bit hash to 32 bits via XOR, it seems that the resulting hash function is good enough (this is also how Long type is hashed in Java.) Storing 10, 100, 1000 Python strings results in a relatively shallow and uniform tree structure. - Please don't change this hashing algorithm, as there are many - tests that test some exact tree shape to cover all code paths. + Also it's worth noting that it would be possible to adapt the tree + structure to 64 bit hashes, but that would increase memory pressure + and provide little to no performance benefits for collections with + fewer than billions of key/value pairs. + + Important: do not change this hash reducing function. There are many + tests that need an exact tree shape to cover all code paths and + we do that by specifying concrete values for test data's `__hash__`. + If this function is changed most of the regression tests would + become useless. */ int32_t xored = (int32_t)(hash & 0xffffffffl) ^ (int32_t)(hash >> 32); return xored == -1 ? -2 : xored; -- cgit v1.2.3