diff options
author | Raymond Hettinger <python@rcn.com> | 2017-02-04 02:43:42 -0800 |
---|---|---|
committer | Raymond Hettinger <python@rcn.com> | 2017-02-04 02:43:42 -0800 |
commit | 7a46b9a1dd0da5ef1362330ee4c94ca1fdc06d0c (patch) | |
tree | d4c55a70d6837de11103ae2ae2cf298674ae1893 | |
parent | b97948eadf46cef282f6978e3caefd7c7a365f13 (diff) | |
download | cpython-7a46b9a1dd0da5ef1362330ee4c94ca1fdc06d0c.tar.gz |
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).
-rw-r--r-- | Objects/setobject.c | 6 |
1 files 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; } |