cpython: a887596b841f (original) (raw)

--- a/Include/setobject.h +++ b/Include/setobject.h @@ -51,9 +51,9 @@ struct _setobject { */ setentry *table; setentry *(*lookup)(PySetObject *so, PyObject *key, Py_hash_t hash);

Py_hash_t hash; /* only used by frozenset objects */ setentry smalltable[PySet_MINSIZE];

Py_hash_t hash; /* only used by frozenset objects */ PyObject weakreflist; / List of weak references */ };

#endif /* Py_LIMITED_API */

--- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -68,6 +68,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. + All arithmetic on hash should ignore overflow. Unlike the dictionary implementation, the lookkey functions can return @@ -77,7 +82,7 @@ NULL if the rich comparison returns an e static setentry * set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) {

size_t i; /* Unsigned for defined overflow behavior. */

size_t i, j; /* Unsigned for defined overflow behavior. */ size_t perturb; setentry *freeslot; size_t mask = so->mask; @@ -90,7 +95,6 @@ set_lookkey(PySetObject *so, PyObject *k entry = &table[i]; if (entry->key == NULL || entry->key == key) return entry;

- if (entry->hash == hash) { startkey = entry->key; Py_INCREF(startkey); @@ -107,14 +111,15 @@ set_lookkey(PySetObject *so, PyObject k return set_lookkey(so, key, hash); } } - freeslot = (entry->key == dummy) ? entry : NULL; / In the loop, key == dummy is by far (factor of 100s) the least likely outcome, so test for that last. */

for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
```
   i = i * 5 + perturb + 1;[](#l2.42)
```
```
   entry = &table[i & mask];[](#l2.43)
```

j = i;
perturb = hash;
while (1) {
```
   j ^= 1;[](#l2.47)
```

   entry = &table[j];[](#l2.48)
   if (entry->key == NULL) {[](#l2.49)
       if (freeslot != NULL)[](#l2.50)
           entry = freeslot;[](#l2.51)

@@ -134,14 +139,42 @@ set_lookkey(PySetObject *so, PyObject *k break; } else {

           /* The compare did major nasty stuff to the[](#l2.56)

            * set:  start over.[](#l2.57)

            */[](#l2.58)
           return set_lookkey(so, key, hash);[](#l2.59)
       }[](#l2.60)
   }[](#l2.61)
   if (entry->key == dummy && freeslot == NULL)[](#l2.62)
       freeslot = entry;[](#l2.63)

```
   i = i * 5 + perturb + 1;[](#l2.65)
```
```
   j = i & mask;[](#l2.66)
```
```
   perturb >>= PERTURB_SHIFT;[](#l2.67)
```

```
   entry = &table[j];[](#l2.69)
```
```
   if (entry->key == NULL) {[](#l2.70)
```
```
       if (freeslot != NULL)[](#l2.71)
```
```
           entry = freeslot;[](#l2.72)
```
```
       break;[](#l2.73)
```
```
   }[](#l2.74)
```
```
   if (entry->key == key)[](#l2.75)
```
```
       break;[](#l2.76)
```
```
   if (entry->hash == hash) {[](#l2.77)
```
```
       startkey = entry->key;[](#l2.78)
```
```
       Py_INCREF(startkey);[](#l2.79)
```

       cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);[](#l2.80)

```
       Py_DECREF(startkey);[](#l2.81)
```
```
       if (cmp < 0)[](#l2.82)
```
```
           return NULL;[](#l2.83)
```

       if (table == so->table && entry->key == startkey) {[](#l2.84)

```
           if (cmp > 0)[](#l2.85)
```
```
               break;[](#l2.86)
```
```
       }[](#l2.87)
```
```
       else {[](#l2.88)
```

           return set_lookkey(so, key, hash);[](#l2.89)

```
       }[](#l2.90)
```
```
   }[](#l2.91)
```

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

```
       freeslot = entry;[](#l2.93)
```

+ } return entry; } @@ -154,7 +187,7 @@ set_lookkey(PySetObject *so, PyObject *k static setentry * set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash) {

size_t i; /* Unsigned for defined overflow behavior. */

size_t i, j; /* Unsigned for defined overflow behavior. */ size_t perturb; setentry *freeslot; size_t mask = so->mask; @@ -169,6 +202,7 @@ set_lookkey_unicode(PySetObject *so, PyO so->lookup = set_lookkey; return set_lookkey(so, key, hash); } + i = (size_t)hash & mask; entry = &table[i]; if (entry->key == NULL || entry->key == key) @@ -181,11 +215,37 @@ set_lookkey_unicode(PySetObject *so, PyO freeslot = NULL; }

/* In the loop, key == dummy is by far (factor of 100s) the

  least likely outcome, so test for that last. */[](#l2.120)

for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {

entry = &table[i ^ 1];
if (entry->key == NULL)

   return freeslot == NULL ? entry : freeslot;[](#l2.124)

if (entry->key == key
```
   || (entry->hash == hash[](#l2.126)
```

       && entry->key != dummy[](#l2.127)

       && unicode_eq(entry->key, key)))[](#l2.128)

```
   return entry;[](#l2.129)
```
if (entry->key == dummy && freeslot == NULL)
```
   freeslot = entry;[](#l2.131)
```

j = i;
perturb = hash;
while (1) {
```
   j ^= 1;[](#l2.136)
```
```
   entry = &table[j];[](#l2.137)
```
```
   if (entry->key == NULL)[](#l2.138)
```

       return freeslot == NULL ? entry : freeslot;[](#l2.139)

```
   if (entry->key == key[](#l2.140)
```

       || (entry->hash == hash[](#l2.141)

       && entry->key != dummy[](#l2.142)

       && unicode_eq(entry->key, key)))[](#l2.143)

```
       return entry;[](#l2.144)
```

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

```
       freeslot = entry;[](#l2.146)
```

+ i = i * 5 + perturb + 1;

```
   entry = &table[i & mask];[](#l2.149)
```

```
   j = i & mask;[](#l2.150)
```

   perturb >>= PERTURB_SHIFT;[](#l2.151)

   entry = &table[j];[](#l2.153)
   if (entry->key == NULL)[](#l2.154)
       return freeslot == NULL ? entry : freeslot;[](#l2.155)
   if (entry->key == key[](#l2.156)

@@ -244,17 +304,23 @@ is responsible for incref'ing key. static void set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash) {

size_t i;
size_t perturb;
size_t mask = (size_t)so->mask; setentry *table = so->table; setentry *entry;

size_t perturb = hash;
size_t mask = (size_t)so->mask;
size_t i, j;

i = (size_t)hash & mask;
entry = &table[i];
for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {

i = j = (size_t)hash & mask;
while (1) {
```
   entry = &table[j];[](#l2.175)
```
```
   if (entry->key == NULL)[](#l2.176)
```
```
       break;[](#l2.177)
```
```
   entry = &table[j ^ 1];[](#l2.178)
```
```
   if (entry->key == NULL)[](#l2.179)
```

       break;[](#l2.180)
   i = i * 5 + perturb + 1;[](#l2.181)

```
   entry = &table[i & mask];[](#l2.182)
```

```
   j = i & mask;[](#l2.183)
```

   perturb >>= PERTURB_SHIFT;[](#l2.184)

} so->fill++; entry->key = key;