From 2c5a830f2ac654e643eaa29ef60bd51977700376 Mon Sep 17 00:00:00 2001 From: INADA Naoki Date: Wed, 7 Dec 2016 18:34:44 +0900 Subject: Issue #28731: Optimize _PyDict_NewPresized() to create correct size dict. Improve speed of dict literal with constant keys up to 30%. --- Misc/NEWS | 3 +++ Objects/dictobject.c | 24 +++++++++++++++++++----- 2 files changed, 22 insertions(+), 5 deletions(-) diff --git a/Misc/NEWS b/Misc/NEWS index c625435..8023df3 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -10,6 +10,9 @@ What's New in Python 3.6.1 release candidate 1 Core and Builtins ----------------- +- Issue #28731: Optimize _PyDict_NewPresized() to create correct size dict. + Improve speed of dict literal with constant keys up to 30%. + - Issue #5322: Fixed setting __new__ to a PyCFunction inside Python code. Original patch by Andreas Stührk. diff --git a/Objects/dictobject.c b/Objects/dictobject.c index d8ab91f..97f0418 100644 --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -388,7 +388,7 @@ dk_set_index(PyDictKeysObject *keys, Py_ssize_t i, Py_ssize_t ix) * This can be used to reserve enough size to insert n entries without * resizing. */ -#define ESTIMATE_SIZE(n) (((n)*3) >> 1) +#define ESTIMATE_SIZE(n) (((n)*3+1) >> 1) /* Alternative fraction that is otherwise close enough to 2n/3 to make * little difference. 8 * 2/3 == 8 * 5/8 == 5. 16 * 2/3 == 16 * 5/8 == 10. @@ -1357,12 +1357,26 @@ make_keys_shared(PyObject *op) PyObject * _PyDict_NewPresized(Py_ssize_t minused) { + const Py_ssize_t max_presize = 128 * 1024; Py_ssize_t newsize; PyDictKeysObject *new_keys; - for (newsize = PyDict_MINSIZE; - newsize <= minused && newsize > 0; - newsize <<= 1) - ; + + /* There are no strict guarantee that returned dict can contain minused + * items without resize. So we create medium size dict instead of very + * large dict or MemoryError. + */ + if (minused > USABLE_FRACTION(max_presize)) { + newsize = max_presize; + } + else { + Py_ssize_t minsize = ESTIMATE_SIZE(minused); + newsize = PyDict_MINSIZE; + while (newsize < minsize) { + newsize <<= 1; + } + } + assert(IS_POWER_OF_2(newsize)); + new_keys = new_keys_object(newsize); if (new_keys == NULL) return NULL; -- cgit v0.12