[Python-checkins] cpython: Replace outdated optimization with clearer code that compiles better.

[raymond.hettinger]

http://hg.python.org/cpython/rev/56bff9a8cfdd
changeset:   85048:56bff9a8cfdd
user:        Raymond Hettinger <python at rcn.com>
date:        Mon Aug 05 22:24:50 2013 -0700
summary:
  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

files:
  Objects/setobject.c |  6 +++---
  1 files changed, 3 insertions(+), 3 deletions(-)


diff --git a/Objects/setobject.c b/Objects/setobject.c
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -118,7 +118,7 @@
     /* 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 @@
     /* 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 @@
     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++;

-- 
Repository URL: http://hg.python.org/cpython