Optimize set.pop() to advance a pointer instead of indexing. (pythonGH-10429)

rhettinger · miss-islington · commit cf5863faabe0 · 2018-11-09T02:31:56.000-08:00
Gives approx 20% speed-up using clang depending on the number of elements in the set (the less dense the set, the more the speed-up).

Uses the same entry++ logic used elsewhere in the setobject.c code.
diff --git a/Objects/setobject.c b/Objects/setobject.c
@@ -701,8 +701,7 @@ static PyObject *
 set_pop(PySetObject *so, PyObject *Py_UNUSED(ignored))
 {
     /* Make sure the search finger is in bounds */
-    Py_ssize_t i = so->finger & so->mask;
-    setentry *entry;
+    setentry *entry, *limit;
     PyObject *key;
 
     assert (PyAnySet_Check(so));
@@ -711,16 +710,18 @@ set_pop(PySetObject *so, PyObject *Py_UNUSED(ignored))
         return NULL;
     }
 
-    while ((entry = &so->table[i])->key == NULL || entry->key==dummy) {
-        i++;
-        if (i > so->mask)
-            i = 0;
+    entry = so->table + (so->finger & so->mask);
+    limit = so->table + so->mask;
+    while (entry->key == NULL || entry->key==dummy) {
+        entry++;
+        if (entry > limit)
+            entry = so->table;
     }
     key = entry->key;
     entry->key = dummy;
     entry->hash = -1;
     so->used--;
-    so->finger = i + 1;         /* next place to start */
+    so->finger = entry - so->table + 1;   /* next place to start */
     return key;
 }
 
