(original) (raw)

changeset: 85486:d40a65658ff0 parent: 85482:4d604f1f0219 user: Raymond Hettinger python@rcn.com date: Sat Aug 31 21:27:08 2013 -0700 files: Objects/setobject.c description: Further reduce the cost of hash collisions by inspecting an additional nearby entry. diff -r 4d604f1f0219 -r d40a65658ff0 Objects/setobject.c --- a/Objects/setobject.c Sat Aug 31 15🔞48 2013 -0700 +++ b/Objects/setobject.c Sat Aug 31 21:27:08 2013 -0700 @@ -65,10 +65,11 @@ The initial probe index is computed as hash mod the table size. Subsequent probe indices are computed as explained in Objects/dictobject.c. -To improve cache locality, each probe is done in pairs. -After the probe is examined, an adjacent entry is then examined as well. -The likelihood is that an adjacent entry is in the same cache line and -can be examined more cheaply than another probe elsewhere in memory. +To improve cache locality, each probe inspects nearby entries before +moving on to probes elsewhere in memory. Depending on alignment and the +size of a cache line, the nearby entries are cheaper to inspect than +other probes elsewhere in memory. This probe strategy reduces the cost +of hash collisions. All arithmetic on hash should ignore overflow. @@ -130,6 +131,26 @@ if (entry->key == dummy && freeslot == NULL) freeslot = entry; + entry = &table[j ^ 2]; + if (entry->key == NULL) + break; + if (entry->key == key) + return entry; + if (entry->hash == hash && entry->key != dummy) { + PyObject *startkey = entry->key; + 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; + i = i * 5 + perturb + 1; j = i & mask; perturb >>= PERTURB_SHIFT; @@ -190,6 +211,17 @@ if (entry->key == dummy && freeslot == NULL) freeslot = entry; + entry = &table[j ^ 2]; + if (entry->key == NULL) + break; + if (entry->key == key + || (entry->hash == hash + && entry->key != dummy + && unicode_eq(entry->key, key))) + return entry; + if (entry->key == dummy && freeslot == NULL) + freeslot = entry; + i = i * 5 + perturb + 1; j = i & mask; perturb >>= PERTURB_SHIFT; @@ -258,6 +290,9 @@ entry = &table[j ^ 1]; if (entry->key == NULL) break; + entry = &table[j ^ 2]; + if (entry->key == NULL) + break; i = i * 5 + perturb + 1; j = i & mask; perturb >>= PERTURB_SHIFT; /python@rcn.com