Reduce load factor (from 66% to 60%) to improve effectiveness of linear probing.

rhettinger · rhettinger · commit 5cd87a8d6124 · 2017-02-04T02:43:42.000-08:00
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
@@ -234,7 +234,7 @@ set_add_entry(PySetObject *so, PyObject *key, Py_hash_t hash)
     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 @@ set_merge(PySetObject *so, PyObject *otherset)
      * 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 @@ set_update_internal(PySetObject *so, PyObject *other)
         */
         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;
         }
