[Python-checkins] bpo-33205: dict: Change GROWTH_RATE to `used*3` (GH-6350)
Miss Islington (bot)
webhook-mailer at python.org
Tue Apr 17 13:17:29 EDT 2018
https://github.com/python/cpython/commit/902bb62d5af21526b68892a1032c63aa86ded247
commit: 902bb62d5af21526b68892a1032c63aa86ded247
branch: 3.7
author: Miss Islington (bot) <31488909+miss-islington at users.noreply.github.com>
committer: GitHub <noreply at github.com>
date: 2018-04-17T10:17:19-07:00
summary:
bpo-33205: dict: Change GROWTH_RATE to `used*3` (GH-6350)
(cherry picked from commit 5fbc511f56688654a05b9eba23d140318bb9b2d5)
Co-authored-by: INADA Naoki <methane at users.noreply.github.com>
files:
A Misc/NEWS.d/next/Core and Builtins/2018-04-03-00-58-41.bpo-33205.lk2F3r.rst
M Objects/dictobject.c
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 000000000000..44511865abfa
--- /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 be895d4c1524..01d913bfce4f 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) { \
More information about the Python-checkins
mailing list