[Python-checkins] cpython: Issue #23107: Tighten-up loops in setobject.c
raymond.hettinger
python-checkins at python.org
Sat Dec 27 05:14:10 CET 2014
https://hg.python.org/cpython/rev/c15f8debd6c9
changeset: 93976:c15f8debd6c9
user: Raymond Hettinger <python at rcn.com>
date: Fri Dec 26 20:14:00 2014 -0800
summary:
Issue #23107: Tighten-up loops in setobject.c
* Move the test for an exact key match to after a hash match
* Use "used" as a loop counter instead of "fill"
* Minor improvements to variable names and code consistency
files:
Objects/setobject.c | 103 ++++++++++++++-----------------
1 files changed, 47 insertions(+), 56 deletions(-)
diff --git a/Objects/setobject.c b/Objects/setobject.c
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -65,10 +65,10 @@
return entry;
while (1) {
- if (entry->key == key)
- return entry;
if (entry->hash == hash && entry->key != dummy) { /* dummy match unlikely */
PyObject *startkey = entry->key;
+ if (startkey == key)
+ return entry;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
@@ -86,10 +86,10 @@
entry = &table[(i + j) & mask];
if (entry->key == NULL)
goto found_null;
- if (entry->key == key)
- return entry;
if (entry->hash == hash && entry->key != dummy) {
PyObject *startkey = entry->key;
+ if (startkey == key)
+ return entry;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
@@ -145,10 +145,10 @@
return entry;
while (1) {
- if (entry->key == key
- || (entry->hash == hash
- && entry->key != dummy /* unlikely */
- && unicode_eq(entry->key, key))) /* likely */
+ if (entry->hash == hash
+ && (entry->key == key
+ || (entry->key != dummy /* unlikely */
+ && unicode_eq(entry->key, key)))) /* likely */
return entry;
if (entry->key == dummy && freeslot == NULL)
freeslot = entry;
@@ -157,10 +157,10 @@
entry = &table[(i + j) & mask];
if (entry->key == NULL)
goto found_null;
- if (entry->key == key
- || (entry->hash == hash
- && entry->key != dummy
- && unicode_eq(entry->key, key)))
+ if (entry->hash == hash
+ && (entry->key == key
+ || (entry->key != dummy /* unlikely */
+ && unicode_eq(entry->key, key)))) /* likely */
return entry;
if (entry->key == dummy && freeslot == NULL)
freeslot = entry;
@@ -196,10 +196,7 @@
size_t j;
while (1) {
- entry = &table[i & mask];
- if (entry->key == NULL)
- goto found_null;
- for (j = 1 ; j <= LINEAR_PROBES ; j++) {
+ for (j = 0 ; j <= LINEAR_PROBES ; j++) {
entry = &table[(i + j) & mask];
if (entry->key == NULL)
goto found_null;
@@ -234,9 +231,9 @@
return -1;
if (entry->key == NULL) {
/* UNUSED */
- so->fill++;
entry->key = key;
entry->hash = hash;
+ so->fill++;
so->used++;
} else if (entry->key == dummy) {
/* DUMMY */
@@ -260,7 +257,8 @@
{
Py_ssize_t newsize;
setentry *oldtable, *newtable, *entry;
- Py_ssize_t i;
+ Py_ssize_t oldfill = so->fill;
+ Py_ssize_t oldused = so->used;
int is_oldtable_malloced;
setentry small_copy[PySet_MINSIZE];
@@ -311,19 +309,27 @@
/* Make the set empty, using the new table. */
assert(newtable != oldtable);
+ memset(newtable, 0, sizeof(setentry) * newsize);
+ so->fill = 0;
+ so->used = 0;
+ so->mask = newsize - 1;
so->table = newtable;
- so->mask = newsize - 1;
- memset(newtable, 0, sizeof(setentry) * newsize);
- i = so->used;
- so->used = 0;
- so->fill = 0;
/* Copy the data over; this is refcount-neutral for active entries;
dummy entries aren't copied over, of course */
- for (entry = oldtable; i > 0; entry++) {
- if (entry->key != NULL && entry->key != dummy) {
- --i;
- set_insert_clean(so, entry->key, entry->hash);
+ if (oldfill == oldused) {
+ for (entry = oldtable; oldused > 0; entry++) {
+ if (entry->key != NULL) {
+ oldused--;
+ set_insert_clean(so, entry->key, entry->hash);
+ }
+ }
+ } else {
+ for (entry = oldtable; oldused > 0; entry++) {
+ if (entry->key != NULL && entry->key != dummy) {
+ oldused--;
+ set_insert_clean(so, entry->key, entry->hash);
+ }
}
}
@@ -438,20 +444,15 @@
static int
set_clear_internal(PySetObject *so)
{
- setentry *entry, *table;
- int table_is_malloced;
- Py_ssize_t fill;
+ setentry *entry;
+ setentry *table = so->table;
+ Py_ssize_t fill = so->fill;
+ Py_ssize_t used = so->used;
+ int table_is_malloced = table != so->smalltable;
setentry small_copy[PySet_MINSIZE];
-#ifdef Py_DEBUG
- Py_ssize_t i = 0;
- Py_ssize_t n = so->mask + 1;
-#endif
-
assert (PyAnySet_Check(so));
- table = so->table;
assert(table != NULL);
- table_is_malloced = table != so->smalltable;
/* This is delicate. During the process of clearing the set,
* decrefs can cause the set to mutate. To avoid fatal confusion
@@ -459,7 +460,6 @@
* clearing the slots, and never refer to anything via so->ref while
* clearing.
*/
- fill = so->fill;
if (table_is_malloced)
set_empty_to_minsize(so);
@@ -478,20 +478,11 @@
* assert that the refcount on table is 1 now, i.e. that this function
* has unique access to it, so decref side-effects can't alter it.
*/
- for (entry = table; fill > 0; ++entry) {
-#ifdef Py_DEBUG
- assert(i < n);
- ++i;
-#endif
- if (entry->key) {
- --fill;
- if (entry->key != dummy)
- Py_DECREF(entry->key);
+ for (entry = table; used > 0; entry++) {
+ if (entry->key && entry->key != dummy) {
+ used--;
+ Py_DECREF(entry->key);
}
-#ifdef Py_DEBUG
- else
- assert(entry->key == NULL);
-#endif
}
if (table_is_malloced)
@@ -538,16 +529,16 @@
set_dealloc(PySetObject *so)
{
setentry *entry;
- Py_ssize_t fill = so->fill;
+ Py_ssize_t used = so->used;
+
PyObject_GC_UnTrack(so);
Py_TRASHCAN_SAFE_BEGIN(so)
if (so->weakreflist != NULL)
PyObject_ClearWeakRefs((PyObject *) so);
- for (entry = so->table; fill > 0; entry++) {
- if (entry->key) {
- --fill;
- if (entry->key != dummy)
+ for (entry = so->table; used > 0; entry++) {
+ if (entry->key && entry->key != dummy) {
+ used--;
Py_DECREF(entry->key);
}
}
--
Repository URL: https://hg.python.org/cpython
More information about the Python-checkins
mailing list