From 5cd87a8d61246b0a6233bfb8503d4718b693cef0 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sat, 4 Feb 2017 02:43:42 -0800 Subject: [PATCH] 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). --- Objects/setobject.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/Objects/setobject.c b/Objects/setobject.c index c72c0fae62..4f04f49efa 100644 --- 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; } -- 2.40.0