Reduce load factor (from 66% to 60%) to improve effectiveness of linear probing.
Decreased density gives better collision statistics (average of 2.5 probes in a
full table versus 3.0 previously) and fewer occurences of starting a second
possibly overlapping sequence of 10 linear probes. Makes resizes a little more
frequent but each with less work (fewer insertions and fewer collisions).
diff --git a/Objects/setobject.c b/Objects/setobject.c
index c72c0fa..4f04f49 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -234,7 +234,7 @@
so->used++;
entry->key = key;
entry->hash = hash;
- if ((size_t)so->fill*3 < mask*2)
+ if ((size_t)so->fill*5 < mask*3)
return 0;
return set_table_resize(so, so->used);
@@ -642,7 +642,7 @@
* incrementally resizing as we insert new keys. Expect
* that there will be no (or few) overlapping keys.
*/
- if ((so->fill + other->used)*3 >= so->mask*2) {
+ if ((so->fill + other->used)*5 >= so->mask*3) {
if (set_table_resize(so, so->used + other->used) != 0)
return -1;
}
@@ -986,7 +986,7 @@
*/
if (dictsize < 0)
return -1;
- if ((so->fill + dictsize)*3 >= so->mask*2) {
+ if ((so->fill + dictsize)*5 >= so->mask*3) {
if (set_table_resize(so, so->used + dictsize) != 0)
return -1;
}