_PyDict_NewPresized() creates too small dict

[methane]

BPO	28731
Nosy	@vstinner, @methane, @serhiy-storchaka
PRs	[Do Not Merge] Convert Misc/NEWS so that it is managed by towncrier #552
Files	PyDict_NewPresized-too-small.patch 28731-PyDict_NewPresized-too-small-2.patch 28731-PyDict_NewPresized-too-small-3.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/methane'
closed_at = <Date 2016-12-07.09:40:06.027>
created_at = <Date 2016-11-18.11:03:05.310>
labels = ['3.7', 'performance']
title = '_PyDict_NewPresized() creates too small dict'
updated_at = <Date 2017-03-31.16:36:13.778>
user = 'https://github.com/methane'

bugs.python.org fields:

activity = <Date 2017-03-31.16:36:13.778>
actor = 'dstufft'
assignee = 'methane'
closed = True
closed_date = <Date 2016-12-07.09:40:06.027>
closer = 'methane'
components = []
creation = <Date 2016-11-18.11:03:05.310>
creator = 'methane'
dependencies = []
files = ['45531', '45583', '45586']
hgrepos = []
issue_num = 28731
keywords = ['patch']
message_count = 22.0
messages = ['281092', '281093', '281098', '281105', '281106', '281108', '281109', '281113', '281117', '281118', '281120', '281121', '281122', '281123', '281124', '281136', '281353', '281354', '281355', '281370', '281372', '282606']
nosy_count = 4.0
nosy_names = ['vstinner', 'methane', 'python-dev', 'serhiy.storchaka']
pr_nums = ['552']
priority = 'normal'
resolution = 'fixed'
stage = 'commit review'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue28731'
versions = ['Python 3.6', 'Python 3.7']

[methane]

_PyDict_NewPresized(6) creates dict which keysize is 8.
But it's capacity is 5 (8 * 2 // 3 = 5).

This internal API is used by BUILD_MAP and BUILD_CONST_KEYMAP.

[methane]

This patch includes fix for ESTIMATE_SIZE macro. (see below)
Same fix is included in patch for bpo-28147.

>>> def estimate_size(n):
...     return n * 3 // 2  # Current ESTIMATE_SIZE
...
>>> def usable(n):
...     return n * 2 // 3
...
>>> def keysize(minsize):
...     size = 8
...     while size < minsize:  # Current implementation uses <=
...         size *= 2
...     return size
...
>>> def check():
...     for i in range(1000):
...         estimate = estimate_size(i)
...         size = keysize(estimate)
...         cap = usable(size)
...         if cap < i:
...             print(i, estimate, size, cap)
...
>>> check()
11 16 16 10
43 64 64 42
171 256 256 170
683 1024 1024 682
>>> # 
>>> estimate_size = lambda n: (n * 3 +1) // 2  # Fixed version
>>> check()
>>>

[methane]

current:
$ ~/work/python36/bin/python3 -m perf timeit -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6}'
.....................
Median +- std dev: 925 ns +- 49 ns

patched:
$ ~/work/python36/bin/python3 -m perf timeit -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6}'
.....................
Median +- std dev: 726 ns +- 30 ns

[vstinner]

FYI if you rename Python binaries, you can use:

./python-patched perf timeit --compare-to=./python-orig

[vstinner]

Median +- std dev: 925 ns +- 49 ns
Median +- std dev: 726 ns +- 30 ns

Nice speedup. Can you please compare Python 3.5? Better if you compile it
yourself with the same options.

I'm curious if 925 ns is slower than py3.5 or if 726 ns is faster than
py3.5.

[serhiy-storchaka]

The condition in the loop in _PyDict_NewPresized() contains the test newsize > 0. This is a check for integer overflow. But it doesn't make much sense. First, the overflow is undefined behavior, and it is too late to detect it when it already is happen. Second, after detecting the negative value just is passed to new_keys_object() which either is crashed in debug build or makes other integer overflow and creates invalid object.

I would add a runtime check that minused is less than PY_SSIZE_MAX/3 (or more strong PY_SSIZE_MAX/3*2/sizeof(Pobject *)). This would guarantee that integer overflow is not possible. The test "newsize > 0" could be removed.

There is similar code in dictresize().

[methane]

inada-n@test1:~/work/py36$ ~/local/py36/bin/patched -m perf timeit --compare-to ~/local/py36/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6}'
master: ..................... 910 ns +- 49 ns
patched: ..................... 713 ns +- 26 ns

Median +- std dev: [master] 910 ns +- 49 ns -> [patched] 713 ns +- 26 ns: 1.28x faster

inada-n@test1:~/work/py36$ ~/local/py36/bin/patched -m perf timeit --compare-to ~/local/py35/bin/python3.5 -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6}'
python3.5: ..................... 1.17 us +- 0.06 us
patched: ..................... 720 ns +- 24 ns

Median +- std dev: [python3.5] 1.17 us +- 0.06 us -> [patched] 720 ns +- 24 ns: 1.62x faster

[methane]

Python 3.5 has similar issue:
$ ~/local/py35/bin/patched -m perf timeit --compare-to ~/local/py35/bin/master -- 'd = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6}'
master: ..................... 1.15 us +- 0.09 us
patched: ..................... 885 ns +- 37 ns

Median +- std dev: [master] 1.15 us +- 0.09 us -> [patched] 885 ns +- 37 ns: 1.30x faster

patch:
diff -r 20f62e4a9c2f Objects/dictobject.c
--- a/Objects/dictobject.c      Wed Nov 16 16:32:22 2016 -0800
+++ b/Objects/dictobject.c      Fri Nov 18 12:56:38 2016 +0000
@@ -1015,8 +1015,9 @@ PyObject *
 {
     Py_ssize_t newsize;
     PyDictKeysObject *new_keys;
+    minused = (minused * 3 + 1) / 2;
     for (newsize = PyDict_MINSIZE_COMBINED;
-         newsize <= minused && newsize > 0;
+         newsize < minused && newsize > 0;
          newsize <<= 1)
         ;
     new_keys = new_keys_object(newsize);

[vstinner]

Ok, it's an optimization, not a performance regression of Python 3.6. In this case, I suggest to first push the change to Python 3.7, and after 3.6.0 release, backport to 3.6 (if you want to), and maybe even 3.5 if it makes sense (and if you want).

I didn't review the patch.

[methane]

On Fri, Nov 18, 2016 at 9:31 PM, Serhiy Storchaka
<report@bugs.python.org> wrote:

Serhiy Storchaka added the comment:

The condition in the loop in _PyDict_NewPresized() contains the test newsize > 0. This is a check for integer overflow. But it doesn't make much sense. First, the overflow is undefined behavior, and it is too late to detect it when it already is happen. Second, after detecting the negative value just is passed to new_keys_object() which either is crashed in debug build or makes other integer overflow and creates invalid object.

I would add a runtime check that minused is less than PY_SSIZE_MAX/3 (or more strong PY_SSIZE_MAX/3*2/sizeof(Pobject *)). This would guarantee that integer overflow is not possible. The test "newsize > 0" could be removed.

There is similar code in dictresize().

Nice idea. I'll update patch in bpo-28147.

In case of _PyDict_NewPresized(minused), it would be called from 3rd
party libraries, and there are no strong
guarantee about PyDict_SetItem() won't resize until minused items.
So how about more small, maximum presize?

#define MAX_INITSIZE (128 * 1024)

if (minused > USABLE_FRACTION(MAX_INITSIZE)) {
    newsize = MAX_INITSIZE;
}
else {
    newsize = PyDict_MINSIZE;
    whilie (newsize < minused)
        newsize <<= 1;   // Can't we assume *= 2 is optimized?
};

[vstinner]

Even if the use case is limited (creation of small dictionaries), it's a nice enhancement, good job Naoki! It's nice to see someone looking at this very important Python type!

1.28x faster or 1.62x faster is significant for a micro-optimization! (My personal threshold is at least 10% faster for a micro-optimization.)

[serhiy-storchaka]

So how about more small, maximum presize?

I don't know what is the benefit of this, but this change looks correct. The benefit of preresizing is vanishingly small for very large dicts.