[Python-checkins] Optimize set.pop() to advance a pointer instead of indexing. (GH-10429)

[Miss Islington (bot)]

https://github.com/python/cpython/commit/cf5863faabe011a61827b9b9982dba3d6a381f0f
commit: cf5863faabe011a61827b9b9982dba3d6a381f0f
branch: master
author: Raymond Hettinger <rhettinger at users.noreply.github.com>
committer: Miss Islington (bot) <31488909+miss-islington at users.noreply.github.com>
date: 2018-11-09T02:31:56-08:00
summary:

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



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.

files:
M Objects/setobject.c

diff --git a/Objects/setobject.c b/Objects/setobject.c
index 42fe80fc0503..ce5092195975 100644
--- 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;
 }