[New-bugs-announce] [issue31179] Speed-up dict.copy() up to 5.5 times.

[Yury Selivanov]

New submission from Yury Selivanov:

It's possible to significantly improve performance of shallow dict copy.  Currently, PyDict_Copy creates a new empty dict object and then inserts key/values into it one by one.

My idea is to simply memcpy the whole keys/items region and do the necessary increfs after it.  This works just fine for non-key-sharing dicts.

With the following simple microbenchmark:

    import time

    N = 1000000

    for size in [0, 1, 10, 20, 50, 100, 500, 1000]:
        d = dict([(str(i), i) for i in range(size)])

        t = time.monotonic()
        for i in range(N):
            d.copy()
        e = time.monotonic() - t

        print(f'dict(size={size}).copy() x {N} times:\t {e:.4f}')


Output for 3.7 master:

    dict(size=0).copy() x 1000000 times:     0.1299
    dict(size=1).copy() x 1000000 times:     0.1499
    dict(size=10).copy() x 1000000 times:    0.3758
    dict(size=20).copy() x 1000000 times:    0.7722
    dict(size=50).copy() x 1000000 times:    1.2784
    dict(size=100).copy() x 1000000 times:   2.5128
    dict(size=500).copy() x 1000000 times:   12.8968
    dict(size=1000).copy() x 1000000 times:  25.4276


Output for patched 3.7:

    dict(size=0).copy() x 1000000 times:     0.1352
    dict(size=1).copy() x 1000000 times:     0.1285
    dict(size=10).copy() x 1000000 times:    0.1632
    dict(size=20).copy() x 1000000 times:    0.3076
    dict(size=50).copy() x 1000000 times:    0.3663
    dict(size=100).copy() x 1000000 times:   0.5140
    dict(size=500).copy() x 1000000 times:   2.3419
    dict(size=1000).copy() x 1000000 times:  4.6176

----------
components: Interpreter Core
messages: 300117
nosy: haypo, inada.naoki, yselivanov
priority: normal
severity: normal
stage: patch review
status: open
title: Speed-up dict.copy() up to 5.5 times.
type: performance
versions: Python 3.7

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue31179>
_______________________________________