cpython: d40a65658ff0 (original) (raw)

Mercurial > cpython

changeset 85486:d40a65658ff0

Further reduce the cost of hash collisions by inspecting an additional nearby entry.

Raymond Hettinger python@rcn.com
date	Sat, 31 Aug 2013 21:27:08 -0700
parents	4d604f1f0219
children	47ccca4b27ce
files	Objects/setobject.c
diffstat	1 files changed, 39 insertions(+), 4 deletions(-)[+] [-] Objects/setobject.c 43

line wrap: on

line diff

--- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -65,10 +65,11 @@ chaining would be substantial (100% with 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 @@ set_lookkey(PySetObject *so, PyObject *k if (entry->key == dummy && freeslot == NULL) freeslot = entry;

```
   entry = &table[j ^ 2];[](#l1.23)
```
```
   if (entry->key == NULL)[](#l1.24)
```
```
       break;[](#l1.25)
```
```
   if (entry->key == key)[](#l1.26)
```
```
       return entry;[](#l1.27)
```

   if (entry->hash == hash && entry->key != dummy) {[](#l1.28)

       PyObject *startkey = entry->key;[](#l1.29)

```
       Py_INCREF(startkey);[](#l1.30)
```

       cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);[](#l1.31)

```
       Py_DECREF(startkey);[](#l1.32)
```
```
       if (cmp < 0)[](#l1.33)
```
```
           return NULL;[](#l1.34)
```

       if (table != so->table || entry->key != startkey)[](#l1.35)

           return set_lookkey(so, key, hash);[](#l1.36)

```
       if (cmp > 0)[](#l1.37)
```
```
           return entry;[](#l1.38)
```
```
   }[](#l1.39)
```

   if (entry->key == dummy && freeslot == NULL)[](#l1.40)

```
       freeslot = entry;[](#l1.41)
```

+ i = i * 5 + perturb + 1; j = i & mask; perturb >>= PERTURB_SHIFT; @@ -190,6 +211,17 @@ set_lookkey_unicode(PySetObject *so, PyO if (entry->key == dummy && freeslot == NULL) freeslot = entry;

```
   entry = &table[j ^ 2];[](#l1.50)
```
```
   if (entry->key == NULL)[](#l1.51)
```
```
       break;[](#l1.52)
```
```
   if (entry->key == key[](#l1.53)
```

       || (entry->hash == hash[](#l1.54)

```
       && entry->key != dummy[](#l1.55)
```

       && unicode_eq(entry->key, key)))[](#l1.56)

```
       return entry;[](#l1.57)
```

   if (entry->key == dummy && freeslot == NULL)[](#l1.58)

```
       freeslot = entry;[](#l1.59)
```

+ i = i * 5 + perturb + 1; j = i & mask; perturb >>= PERTURB_SHIFT; @@ -258,6 +290,9 @@ set_insert_clean(PySetObject *so, PyObje entry = &table[j ^ 1]; if (entry->key == NULL) break;

```
   entry = &table[j ^ 2];[](#l1.68)
```
```
   if (entry->key == NULL)[](#l1.69)
```

       break;[](#l1.70)
   i = i * 5 + perturb + 1;[](#l1.71)
   j = i & mask;[](#l1.72)
   perturb >>= PERTURB_SHIFT;[](#l1.73)