diff options
| author | Raymond Hettinger <python@rcn.com> | 2015-02-02 16:35:00 (GMT) |
|---|---|---|
| committer | Raymond Hettinger <python@rcn.com> | 2015-02-02 16:35:00 (GMT) |
| commit | c658d85487142099c1abe8e916c9864f7fc7b7a4 (patch) | |
| tree | 4522b7c744690d4c0f7690a0a12e6a118a604b3f /Objects | |
| parent | f86d1fdab79cd6cab150fffecbc76388cb5b7f92 (diff) | |
| download | cpython-c658d85487142099c1abe8e916c9864f7fc7b7a4.zip cpython-c658d85487142099c1abe8e916c9864f7fc7b7a4.tar.gz cpython-c658d85487142099c1abe8e916c9864f7fc7b7a4.tar.bz2 | |
Issue 23359: Tighten inner search loop for sets (don't and-mask every entry lookup).
Diffstat (limited to 'Objects')
| -rw-r--r-- | Objects/setobject.c | 77 |
1 files changed, 53 insertions, 24 deletions
diff --git a/Objects/setobject.c b/Objects/setobject.c index 021b83e..ff832d5 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -88,31 +88,60 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) 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; + } + } 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; } - if (entry->key == dummy && freeslot == NULL) - freeslot = entry; } perturb >>= PERTURB_SHIFT; |