Skip to content

gh-94155: Reduce hash collisions for code objects #100183

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
sweeneyde merged 7 commits into from
Dec 23, 2022
+60 −20
Merged

gh-94155: Reduce hash collisions for code objects #100183

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
9942ce6
Reduce hash collisions for code objects
sweeneyde Dec 12, 2022
d54249c
📜🤖 Added by blurb_it.
blurb-it[bot] Dec 12, 2022
3c38f5a
don't compare unsigned to signed
sweeneyde Dec 12, 2022
dbb5c77
Disregard byte order
sweeneyde Dec 12, 2022
b2975bc
Merge remote-tracking branch 'upstream/main' into code_hash
sweeneyde Dec 17, 2022
2014fb1
SCRAMBLE_IN_HASH macro
sweeneyde Dec 19, 2022
cffe844
Merge branch 'main' into code_hash
sweeneyde Dec 23, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Reduce hash collisions for code objects
  • Loading branch information
@sweeneyde
sweeneyde committed Dec 12, 2022
commit 9942ce65d7771117d7a542fb511496bfa45f6164
26 changes: 26 additions & 0 deletions Lib/test/test_code.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -465,6 +465,32 @@ def f():
self.assertNotEqual(code_b, code_d)
self.assertNotEqual(code_c, code_d)

def test_code_hash_uses_firstlineno(self):
c1 = (lambda: 1).__code__
c2 = (lambda: 1).__code__
self.assertNotEqual(c1, c2)
self.assertNotEqual(hash(c1), hash(c2))
c3 = c1.replace(co_firstlineno=17)
self.assertNotEqual(c1, c3)
self.assertNotEqual(hash(c1), hash(c3))

def test_code_hash_uses_order(self):
# Swapping posonlyargcount and kwonlyargcount should change the hash.
c = (lambda x, y, *, z=1, w=1: 1).__code__
self.assertEqual(c.co_argcount, 2)
self.assertEqual(c.co_posonlyargcount, 0)
self.assertEqual(c.co_kwonlyargcount, 2)
swapped = c.replace(co_posonlyargcount=2, co_kwonlyargcount=0)
self.assertNotEqual(c, swapped)
self.assertNotEqual(hash(c), hash(swapped))

def test_code_hash_uses_bytecode(self):
c = (lambda x, y: x + y).__code__
d = (lambda x, y: x * y).__code__
c1 = c.replace(co_code=d.co_code)
self.assertNotEqual(c, c1)
self.assertNotEqual(hash(c), hash(c1))


def isinterned(s):
return s is sys.intern(('_' + s + '_')[1:-1])
Expand Down
53 changes: 33 additions & 20 deletions Objects/codeobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1834,28 +1834,41 @@ code_richcompare(PyObject *self, PyObject *other, int op)
static Py_hash_t
code_hash(PyCodeObject *co)
{
Py_hash_t h, h0, h1, h2, h3;
h0 = PyObject_Hash(co->co_name);
if (h0 == -1) return -1;
h1 = PyObject_Hash(co->co_consts);
if (h1 == -1) return -1;
h2 = PyObject_Hash(co->co_names);
if (h2 == -1) return -1;
h3 = PyObject_Hash(co->co_localsplusnames);
if (h3 == -1) return -1;
Py_hash_t h4 = PyObject_Hash(co->co_linetable);
if (h4 == -1) {
return -1;
Py_uhash_t res = 20221211;
#define SCRAMBLE_IN(H) do { \
res ^= (Py_uhash_t)(H); \
res *= _PyHASH_MULTIPLIER; \
} while (0)
#define SCRAMBLE_IN_OR_ERR(EXPR) do { \
Py_hash_t h = (EXPR); \
if (h == -1) { \
return -1; \
} \
SCRAMBLE_IN(h); \
} while (0)

SCRAMBLE_IN_OR_ERR(PyObject_Hash(co->co_name));
SCRAMBLE_IN_OR_ERR(PyObject_Hash(co->co_consts));
SCRAMBLE_IN_OR_ERR(PyObject_Hash(co->co_names));
SCRAMBLE_IN_OR_ERR(PyObject_Hash(co->co_localsplusnames));
SCRAMBLE_IN_OR_ERR(PyObject_Hash(co->co_linetable));
SCRAMBLE_IN_OR_ERR(PyObject_Hash(co->co_exceptiontable));
SCRAMBLE_IN(co->co_argcount);
SCRAMBLE_IN(co->co_posonlyargcount);
SCRAMBLE_IN(co->co_kwonlyargcount);
SCRAMBLE_IN(co->co_flags);
SCRAMBLE_IN(co->co_firstlineno);
SCRAMBLE_IN(Py_SIZE(co));
for (int i = 0; i < Py_SIZE(co); i++) {
_Py_CODEUNIT co_instr = _PyCode_CODE(co)[i];
_Py_SET_OPCODE(co_instr, _PyOpcode_Deopt[_Py_OPCODE(co_instr)]);
SCRAMBLE_IN(co_instr);
i += _PyOpcode_Caches[_Py_OPCODE(co_instr)];
}
Py_hash_t h5 = PyObject_Hash(co->co_exceptiontable);
if (h5 == -1) {
return -1;
if (res == -1) {
return -2;
}
h = h0 ^ h1 ^ h2 ^ h3 ^ h4 ^ h5 ^
co->co_argcount ^ co->co_posonlyargcount ^ co->co_kwonlyargcount ^
co->co_flags;
if (h == -1) h = -2;
return h;
return res;
}


Expand Down