[Python-checkins] cpython: Issue 23359: Tighten inner search loop for sets (don't and-mask every entry

[raymond.hettinger]

https://hg.python.org/cpython/rev/0b3bc51341aa
changeset:   94463:0b3bc51341aa
user:        Raymond Hettinger <python at rcn.com>
date:        Mon Feb 02 08:35:00 2015 -0800
summary:
  Issue 23359: Tighten inner search loop for sets (don't and-mask every entry lookup).

files:
  Objects/setobject.c |  77 ++++++++++++++++++++++----------
  1 files changed, 53 insertions(+), 24 deletions(-)


diff --git a/Objects/setobject.c b/Objects/setobject.c
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -88,31 +88,60 @@
         if (entry->key == dummy && freeslot == NULL)
             freeslot = entry;
 
-        for (j = 1 ; j <= LINEAR_PROBES ; j++) {
-            entry = &table[(i + j) & mask];
-            if (entry->key == NULL)
-                goto found_null;
-            if (entry->hash == hash) {
-                PyObject *startkey = entry->key;
-                assert(startkey != dummy);
-                if (startkey == key)
-                    return entry;
-                if (PyUnicode_CheckExact(startkey)
-                    && PyUnicode_CheckExact(key)
-                    && unicode_eq(startkey, key))
-                    return entry;
-                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 (i + LINEAR_PROBES <= mask) {
+            for (j = 1 ; j <= LINEAR_PROBES ; j++) {
+                entry++;
+                if (entry->key == NULL)
+                    goto found_null;
+                if (entry->hash == hash) {
+                    PyObject *startkey = entry->key;
+                    assert(startkey != dummy);
+                    if (startkey == key)
+                        return entry;
+                    if (PyUnicode_CheckExact(startkey)
+                        && PyUnicode_CheckExact(key)
+                        && unicode_eq(startkey, key))
+                        return entry;
+                    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;
             }
-            if (entry->key == dummy && freeslot == NULL)
-                freeslot = entry;
+        } else {
+            for (j = 1 ; j <= LINEAR_PROBES ; j++) {
+                entry = &table[(i + j) & mask];
+                if (entry->key == NULL)
+                    goto found_null;
+                if (entry->hash == hash) {
+                    PyObject *startkey = entry->key;
+                    assert(startkey != dummy);
+                    if (startkey == key)
+                        return entry;
+                    if (PyUnicode_CheckExact(startkey)
+                        && PyUnicode_CheckExact(key)
+                        && unicode_eq(startkey, key))
+                        return entry;
+                    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;
+            }
         }
 
         perturb >>= PERTURB_SHIFT;

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