diff options
| author | INADA Naoki <methane@users.noreply.github.com> | 2018-04-17 06:53:34 (GMT) |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2018-04-17 06:53:34 (GMT) |
| commit | 5fbc511f56688654a05b9eba23d140318bb9b2d5 (patch) | |
| tree | 997259ef50c3ef66fb9ee6ea339f0d7089c61509 | |
| parent | acfb087f9f5590e5174a30eced3c2fe911f49d70 (diff) | |
| download | cpython-5fbc511f56688654a05b9eba23d140318bb9b2d5.zip cpython-5fbc511f56688654a05b9eba23d140318bb9b2d5.tar.gz cpython-5fbc511f56688654a05b9eba23d140318bb9b2d5.tar.bz2 | |
bpo-33205: dict: Change GROWTH_RATE to `used*3` (GH-6350)
| -rw-r--r-- | Misc/NEWS.d/next/Core and Builtins/2018-04-03-00-58-41.bpo-33205.lk2F3r.rst | 3 | ||||
| -rw-r--r-- | Objects/dictobject.c | 11 |
2 files changed, 8 insertions, 6 deletions
diff --git a/Misc/NEWS.d/next/Core and Builtins/2018-04-03-00-58-41.bpo-33205.lk2F3r.rst b/Misc/NEWS.d/next/Core and Builtins/2018-04-03-00-58-41.bpo-33205.lk2F3r.rst new file mode 100644 index 0000000..4451186 --- /dev/null +++ b/Misc/NEWS.d/next/Core and Builtins/2018-04-03-00-58-41.bpo-33205.lk2F3r.rst @@ -0,0 +1,3 @@ +Change dict growth function from ``round_up_to_power_2(used*2+hashtable_size/2)`` to +``round_up_to_power_2(used*3)``. Previously, dict is shrinked only when ``used == 0``. +Now dict has more chance to be shrinked. diff --git a/Objects/dictobject.c b/Objects/dictobject.c index be895d4..01d913b 100644 --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -396,17 +396,16 @@ dk_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix) */ /* GROWTH_RATE. Growth rate upon hitting maximum load. - * Currently set to used*2 + capacity/2. + * Currently set to used*3. * This means that dicts double in size when growing without deletions, * but have more head room when the number of deletions is on a par with the - * number of insertions. - * Raising this to used*4 doubles memory consumption depending on the size of - * the dictionary, but results in half the number of resizes, less effort to - * resize. + * number of insertions. See also bpo-17563 and bpo-33205. + * * GROWTH_RATE was set to used*4 up to version 3.2. * GROWTH_RATE was set to used*2 in version 3.3.0 + * GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0. */ -#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1)) +#define GROWTH_RATE(d) ((d)->ma_used*3) #define ENSURE_ALLOWS_DELETIONS(d) \ if ((d)->ma_keys->dk_lookup == lookdict_unicode_nodummy) { \ |