cpython: b708b3190ecb (original) (raw)

Mercurial > cpython

changeset 105286:b708b3190ecb

Issue #28731: Optimize _PyDict_NewPresized() to create correct size dict Improve speed of dict literal with constant keys up to 30%. [#28731]

INADA Naoki songofacandy@gmail.com
date	Tue, 22 Nov 2016 00:57:02 +0900
parents	da042eec6743
children	12b4e7209d03
files	Misc/NEWS Objects/dictobject.c
diffstat	2 files changed, 22 insertions(+), 5 deletions(-)[+] [-] Misc/NEWS 3 Objects/dictobject.c 24

line wrap: on

line diff

--- a/Misc/NEWS +++ b/Misc/NEWS @@ -10,6 +10,9 @@ What's New in Python 3.7.0 alpha 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 #28532: Show sys.version when -V option is supplied twice.
Issue #28746: Fix the set_inheritable() file descriptor method on platforms

--- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -389,7 +389,7 @@ dk_set_index(PyDictKeysObject *keys, Py_

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. @@ -1361,12 +1361,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;[](#l2.20)

```
    newsize <<= 1)[](#l2.21)
```
```
   ;[](#l2.22)
```

/* There are no strict guarantee that returned dict can contain minused

* items without resize.  So we create medium size dict instead of very[](#l2.25)

```
* large dict or MemoryError.[](#l2.26)
```
```
*/[](#l2.27)
```
if (minused > USABLE_FRACTION(max_presize)) {
```
   newsize = max_presize;[](#l2.29)
```
}
else {

   Py_ssize_t minsize = ESTIMATE_SIZE(minused);[](#l2.32)

```
   newsize = PyDict_MINSIZE;[](#l2.33)
```

   while (newsize < minsize) {[](#l2.34)

```
       newsize <<= 1;[](#l2.35)
```
```
   }[](#l2.36)
```
}
assert(IS_POWER_OF_2(newsize));

+ new_keys = new_keys_object(newsize); if (new_keys == NULL) return NULL;