FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Issue18771: Reduce the cost of hash collisions for set objects. · python-emscripten/cpython@3c0a4f5 · GitHub

  1. python-emscripten
  2. cpython

Repository navigation

Commit 3c0a4f5

Browse files
rhettinger
committed
Issue18771: Reduce the cost of hash collisions for set objects.
1 parent 319f3a1 commit 3c0a4f5

2 files changed

Lines changed: 87 additions & 21 deletions

File tree

‎Include/setobject.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -51,9 +51,9 @@ struct _setobject {
5151
*/
5252
setentry *table;
5353
setentry *(*lookup)(PySetObject *so, PyObject *key, Py_hash_t hash);
54+
Py_hash_t hash; /* only used by frozenset objects */
5455
setentry smalltable[PySet_MINSIZE];
5556

56-
Py_hash_t hash; /* only used by frozenset objects */
5757
PyObject *weakreflist; /* List of weak references */
5858
};
5959
#endif /* Py_LIMITED_API */

‎Objects/setobject.c‎

Lines changed: 86 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -68,6 +68,11 @@ chaining would be substantial (100% with typical malloc overhead).
6868
The initial probe index is computed as hash mod the table size. Subsequent
6969
probe indices are computed as explained in Objects/dictobject.c.
7070
71+
To improve cache locality, each probe is done in pairs.
72+
After the probe is examined, an adjacent entry is then examined as well.
73+
The likelihood is that an adjacent entry is in the same cache line and
74+
can be examined more cheaply than another probe elsewhere in memory.
75+
7176
All arithmetic on hash should ignore overflow.
7277
7378
Unlike the dictionary implementation, the lookkey functions can return
@@ -77,7 +82,7 @@ NULL if the rich comparison returns an error.
7782
static setentry *
7883
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
7984
{
80-
size_t i; /* Unsigned for defined overflow behavior. */
85+
size_t i, j; /* Unsigned for defined overflow behavior. */
8186
size_t perturb;
8287
setentry *freeslot;
8388
size_t mask = so->mask;
@@ -90,7 +95,6 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
9095
entry = &table[i];
9196
if (entry->key == NULL || entry->key == key)
9297
return entry;
93-
9498
if (entry->hash == hash) {
9599
startkey = entry->key;
96100
Py_INCREF(startkey);
@@ -107,14 +111,45 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
107111
return set_lookkey(so, key, hash);
108112
}
109113
}
110-
111114
freeslot = (entry->key == dummy) ? entry : NULL;
112115

113116
/* In the loop, key == dummy is by far (factor of 100s)
114117
the least likely outcome, so test for that last. */
115-
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
118+
j = i;
119+
perturb = hash;
120+
while (1) {
121+
j ^= 1;
122+
entry = &table[j];
123+
if (entry->key == NULL) {
124+
if (freeslot != NULL)
125+
entry = freeslot;
126+
break;
127+
}
128+
if (entry->key == key)
129+
break;
130+
if (entry->hash == hash) {
131+
startkey = entry->key;
132+
Py_INCREF(startkey);
133+
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
134+
Py_DECREF(startkey);
135+
if (cmp < 0)
136+
return NULL;
137+
if (table == so->table && entry->key == startkey) {
138+
if (cmp > 0)
139+
break;
140+
}
141+
else {
142+
return set_lookkey(so, key, hash);
143+
}
144+
}
145+
if (entry->key == dummy && freeslot == NULL)
146+
freeslot = entry;
147+
116148
i = i * 5 + perturb + 1;
117-
entry = &table[i & mask];
149+
j = i & mask;
150+
perturb >>= PERTURB_SHIFT;
151+
152+
entry = &table[j];
118153
if (entry->key == NULL) {
119154
if (freeslot != NULL)
120155
entry = freeslot;
@@ -134,14 +169,12 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
134169
break;
135170
}
136171
else {
137-
/* The compare did major nasty stuff to the
138-
* set: start over.
139-
*/
140172
return set_lookkey(so, key, hash);
141173
}
142174
}
143175
if (entry->key == dummy && freeslot == NULL)
144176
freeslot = entry;
177+
145178
}
146179
return entry;
147180
}
@@ -154,7 +187,7 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
154187
static setentry *
155188
set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash)
156189
{
157-
size_t i; /* Unsigned for defined overflow behavior. */
190+
size_t i, j; /* Unsigned for defined overflow behavior. */
158191
size_t perturb;
159192
setentry *freeslot;
160193
size_t mask = so->mask;
@@ -169,6 +202,7 @@ set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash)
169202
so->lookup = set_lookkey;
170203
return set_lookkey(so, key, hash);
171204
}
205+
172206
i = (size_t)hash & mask;
173207
entry = &table[i];
174208
if (entry->key == NULL || entry->key == key)
@@ -181,11 +215,37 @@ set_lookkey_unicode(PySetObject *so, PyObject *key, Py_hash_t hash)
181215
freeslot = NULL;
182216
}
183217

184-
/* In the loop, key == dummy is by far (factor of 100s) the
185-
least likely outcome, so test for that last. */
186-
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
218+
entry = &table[i ^ 1];
219+
if (entry->key == NULL)
220+
return freeslot == NULL ? entry : freeslot;
221+
if (entry->key == key
222+
|| (entry->hash == hash
223+
&& entry->key != dummy
224+
&& unicode_eq(entry->key, key)))
225+
return entry;
226+
if (entry->key == dummy && freeslot == NULL)
227+
freeslot = entry;
228+
229+
j = i;
230+
perturb = hash;
231+
while (1) {
232+
j ^= 1;
233+
entry = &table[j];
234+
if (entry->key == NULL)
235+
return freeslot == NULL ? entry : freeslot;
236+
if (entry->key == key
237+
|| (entry->hash == hash
238+
&& entry->key != dummy
239+
&& unicode_eq(entry->key, key)))
240+
return entry;
241+
if (entry->key == dummy && freeslot == NULL)
242+
freeslot = entry;
243+
187244
i = i * 5 + perturb + 1;
188-
entry = &table[i & mask];
245+
j = i & mask;
246+
perturb >>= PERTURB_SHIFT;
247+
248+
entry = &table[j];
189249
if (entry->key == NULL)
190250
return freeslot == NULL ? entry : freeslot;
191251
if (entry->key == key
@@ -244,17 +304,23 @@ is responsible for incref'ing `key`.
244304
static void
245305
set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash)
246306
{
247-
size_t i;
248-
size_t perturb;
249-
size_t mask = (size_t)so->mask;
250307
setentry *table = so->table;
251308
setentry *entry;
309+
size_t perturb = hash;
310+
size_t mask = (size_t)so->mask;
311+
size_t i, j;
252312

253-
i = (size_t)hash & mask;
254-
entry = &table[i];
255-
for (perturb = hash; entry->key != NULL; perturb >>= PERTURB_SHIFT) {
313+
i = j = (size_t)hash & mask;
314+
while (1) {
315+
entry = &table[j];
316+
if (entry->key == NULL)
317+
break;
318+
entry = &table[j ^ 1];
319+
if (entry->key == NULL)
320+
break;
256321
i = i * 5 + perturb + 1;
257-
entry = &table[i & mask];
322+
j = i & mask;
323+
perturb >>= PERTURB_SHIFT;
258324
}
259325
so->fill++;
260326
entry->key = key;

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL