From c629d4c9a2b6ff92378ee1f2c8ed27f709d2b08e Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Mon, 5 Aug 2013 22:24:50 -0700 Subject: Replace outdated optimization with clearer code that compiles better. Letting the compiler decide how to optimize the multiply by five gives it the freedom to make better choices for the best technique for a given target machine. For example, GCC on x86_64 produces a little bit better code: Old-way (3 steps with a data dependency between each step): shrq $5, %r13 leaq 1(%rbx,%r13), %rax leaq (%rax,%rbx,4), %rbx New-way (3 steps with no dependency between the first two steps which can be run in parallel): leaq (%rbx,%rbx,4), %rax # i*5 shrq $5, %r13 # perturb >>= PERTURB_SHIFT leaq 1(%r13,%rax), %rbx # 1 + perturb + i*5 --- Objects/setobject.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/Objects/setobject.c b/Objects/setobject.c index ea5a24c516..0cea2a81c8 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -118,7 +118,7 @@ set_lookkey(PySetObject *so, PyObject *key, register Py_hash_t hash) /* In the loop, key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */ for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; + i = i * 5 + perturb + 1; entry = &table[i & mask]; if (entry->key == NULL) { if (freeslot != NULL) @@ -189,7 +189,7 @@ set_lookkey_unicode(PySetObject *so, PyObject *key, register Py_hash_t hash) /* In the loop, key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */ for (perturb = hash; ; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; + i = i * 5 + perturb + 1; entry = &table[i & mask]; if (entry->key == NULL) return freeslot == NULL ? entry : freeslot; @@ -258,7 +258,7 @@ set_insert_clean(register PySetObject *so, PyObject *key, Py_hash_t hash) i = (size_t)hash & mask; entry = &table[i]; for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) { - i = (i << 2) + i + perturb + 1; + i = i * 5 + perturb + 1; entry = &table[i & mask]; } so->fill++; -- cgit v1.2.1