[Python-checkins] cpython: Reduce load factor (from 66% to 60%) to improve effectiveness of linear probing.

Sat Feb 4 05:43:52 EST 2017

https://hg.python.org/cpython/rev/ee64f4374daf
changeset: 106415:ee64f4374daf
user: Raymond Hettinger <python at rcn.com>
date: Sat Feb 04 02:43:42 2017 -0800
summary:
 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).
files:
 Objects/setobject.c | 6 +++---
 1 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/Objects/setobject.c b/Objects/setobject.c
--- 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;
 }
-- 
Repository URL: https://hg.python.org/cpython
