summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRaymond Hettinger <python@rcn.com>2013-05-17 10:24:54 (GMT)
committerRaymond Hettinger <python@rcn.com>2013-05-17 10:24:54 (GMT)
commit2f6fe518601eb23880d8f925cd1dcd33e83f7310 (patch)
tree3a93d6609063c14e21683a5af13b1292f5739d5b
parent5c71079d06685e14f39209a730c8b59519803325 (diff)
parent36f74aa7f711c9defc01ab8522117b2b7db8ccd3 (diff)
downloadcpython-2f6fe518601eb23880d8f925cd1dcd33e83f7310.zip
cpython-2f6fe518601eb23880d8f925cd1dcd33e83f7310.tar.gz
cpython-2f6fe518601eb23880d8f925cd1dcd33e83f7310.tar.bz2
merge
-rw-r--r--Objects/dictobject.c18
1 files changed, 11 insertions, 7 deletions
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index bf9ec55..250c890 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -305,14 +305,18 @@ PyDict_Fini(void)
* #define USABLE_FRACTION(n) (((n) >> 1) + ((n) >> 2) - ((n) >> 3))
*/
-/* GROWTH_RATE. Growth rate upon hitting maximum load. Currently set to *2.
- * Raising this to *4 doubles memory consumption depending on the size of
+/* GROWTH_RATE. Growth rate upon hitting maximum load.
+ * Currently set to used*2 + capacity/2.
+ * 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 and better sparseness for some (but not all dict sizes).
- * Setting to *4 eliminates every other resize step.
- * GROWTH_RATE was set to *4 up to version 3.2.
+ * resize.
+ * GROWTH_RATE was set to used*4 up to version 3.2.
+ * GROWTH_RATE was set to used*2 in version 3.3.0
*/
-#define GROWTH_RATE(x) ((x) * 2)
+#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))
#define ENSURE_ALLOWS_DELETIONS(d) \
if ((d)->ma_keys->dk_lookup == lookdict_unicode_nodummy) { \
@@ -790,7 +794,7 @@ find_empty_slot(PyDictObject *mp, PyObject *key, Py_hash_t hash,
static int
insertion_resize(PyDictObject *mp)
{
- return dictresize(mp, GROWTH_RATE(mp->ma_used));
+ return dictresize(mp, GROWTH_RATE(mp));
}
/*