[Python-checkins] cpython: Further reduce the cost of hash collisions by inspecting an additional nearby

[raymond.hettinger]

http://hg.python.org/cpython/rev/d40a65658ff0
changeset:   85486:d40a65658ff0
parent:      85482:4d604f1f0219
user:        Raymond Hettinger <python at rcn.com>
date:        Sat Aug 31 21:27:08 2013 -0700
summary:
  Further reduce the cost of hash collisions by inspecting an additional nearby entry.

files:
  Objects/setobject.c |  43 +++++++++++++++++++++++++++++---
  1 files changed, 39 insertions(+), 4 deletions(-)


diff --git a/Objects/setobject.c b/Objects/setobject.c
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -65,10 +65,11 @@
 The initial probe index is computed as hash mod the table size. Subsequent
 probe indices are computed as explained in Objects/dictobject.c.
 
-To improve cache locality, each probe is done in pairs.
-After the probe is examined, an adjacent entry is then examined as well.
-The likelihood is that an adjacent entry is in the same cache line and
-can be examined more cheaply than another probe elsewhere in memory.
+To improve cache locality, each probe inspects nearby entries before
+moving on to probes elsewhere in memory.  Depending on alignment and the
+size of a cache line, the nearby entries are cheaper to inspect than
+other probes elsewhere in memory.  This probe strategy reduces the cost
+of hash collisions.
 
 All arithmetic on hash should ignore overflow.
 
@@ -130,6 +131,26 @@
         if (entry->key == dummy && freeslot == NULL)
             freeslot = entry;
 
+        entry = &table[j ^ 2];
+        if (entry->key == NULL)
+            break;
+        if (entry->key == key)
+            return entry;
+        if (entry->hash == hash && entry->key != dummy) {
+            PyObject *startkey = entry->key;
+            Py_INCREF(startkey);
+            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
+            Py_DECREF(startkey);
+            if (cmp < 0)
+                return NULL;
+            if (table != so->table || entry->key != startkey)
+                return set_lookkey(so, key, hash);
+            if (cmp > 0)
+                return entry;
+        }
+        if (entry->key == dummy && freeslot == NULL)
+            freeslot = entry;
+
         i = i * 5 + perturb + 1;
         j = i & mask;
         perturb >>= PERTURB_SHIFT;
@@ -190,6 +211,17 @@
         if (entry->key == dummy && freeslot == NULL)
             freeslot = entry;
 
+        entry = &table[j ^ 2];
+        if (entry->key == NULL)
+            break;
+        if (entry->key == key
+            || (entry->hash == hash
+            && entry->key != dummy
+            && unicode_eq(entry->key, key)))
+            return entry;
+        if (entry->key == dummy && freeslot == NULL)
+            freeslot = entry;
+
         i = i * 5 + perturb + 1;
         j = i & mask;
         perturb >>= PERTURB_SHIFT;
@@ -258,6 +290,9 @@
         entry = &table[j ^ 1];
         if (entry->key == NULL)
             break;
+        entry = &table[j ^ 2];
+        if (entry->key == NULL)
+            break;
         i = i * 5 + perturb + 1;
         j = i & mask;
         perturb >>= PERTURB_SHIFT;

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