From cf5863faabe011a61827b9b9982dba3d6a381f0f Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Fri, 9 Nov 2018 02:31:56 -0800 Subject: 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. --- Objects/setobject.c | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) diff --git a/Objects/setobject.c b/Objects/setobject.c index 42fe80f..ce50921 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; } -- cgit v0.12