classification
Title: Speed up the creation time of constant list and set literals.
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.9
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: brandtbucher, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2019-09-30 16:57 by brandtbucher, last changed 2019-11-26 06:17 by inada.naoki. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 16498 closed brandtbucher, 2019-09-30 16:58
PR 16878 closed brandtbucher, 2019-10-22 00:54
PR 17114 merged brandtbucher, 2019-11-12 07:47
Messages (7)
msg353599 - (view) Author: Brandt Bucher (brandtbucher) * (Python triager) Date: 2019-09-30 16:57
The attached PR contains a small change to the peephole optimizer that converts sequences of:

LOAD_CONST(a), LOAD_CONST(b), ..., BUILD_LIST(n)

to

LOAD_CONST((a, b, ...)), BUILD_LIST_UNPACK(1)

The improvement quickly becomes significant for lists larger than a few items (elements vs speedup):

 5:  ~5%
10: ~20%
15: ~25%
20: ~30%
25: ~35%
30: ~45%
35: ~50%

This can be tested on any version of Python by comparing the performance of "[0, 1, 2, ...]" vs "[*(0, 1, 2, ...)]". The common cases of empty and single-element lists are not affected by this change.

This is related to bpo-33325, but that was an invasive change for all collection literals that had an unknown affect on performance. I've limited this one to lists and kept it to a few lines in the peephole optimizer.
msg353964 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-10-04 17:56
Great! I withdrew the original proposition in issue33325 because the part of the optimization was not so good as I expected. But this part is good.

$ ./python -m timeit "[$(seq -s, 10)]"
5000000 loops, best of 5: 75.5 nsec per loop
$ ./python -m timeit "[*($(seq -s, 10))]"
5000000 loops, best of 5: 57.2 nsec per loop

Would you consider to optimize also creating a set of constants?

$ ./python -m timeit "{$(seq -s, 10)}"
2000000 loops, best of 5: 186 nsec per loop
$ ./python -m timeit -s "a = frozenset(($(seq -s, 10)))"  "{*a}"
2000000 loops, best of 5: 116 nsec per loop
msg353965 - (view) Author: Brandt Bucher (brandtbucher) * (Python triager) Date: 2019-10-04 18:17
Yes, I was thinking about that (and BUILD_CONST_KEY_MAP as well). I'll open another PR with those as soon as this one is in.
msg353973 - (view) Author: Brandt Bucher (brandtbucher) * (Python triager) Date: 2019-10-04 20:57
...unless you'd prefer that I add them to this PR. But I think it's a better idea to add and review them separately.
msg353974 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-10-04 22:03
Okay, but first I want to solve an issue with list overallocation.
msg356424 - (view) Author: Brandt Bucher (brandtbucher) * (Python triager) Date: 2019-11-12 07:50
I have created a new patch (PR 17114) that performs this optimization directly in the compiler, rather than the peephole optimizer. I think I like the new one better.
msg357484 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-11-26 06:17
New changeset 6dd9b64770af8905bef293c81d541eaaf8d8df52 by Inada Naoki (Brandt Bucher) in branch 'master':
bpo-38328: Speed up the creation time of constant list and set display. (GH-17114)
https://github.com/python/cpython/commit/6dd9b64770af8905bef293c81d541eaaf8d8df52
History
Date User Action Args
2019-11-26 06:17:35inada.naokisetstatus: open -> closed
nosy: - inada.naoki

resolution: fixed
stage: patch review -> resolved
2019-11-26 06:17:13inada.naokisetnosy: + inada.naoki
messages: + msg357484
2019-11-12 07:54:31brandtbuchersettitle: Speed up the creation time of constant list literals. -> Speed up the creation time of constant list and set literals.
2019-11-12 07:50:18brandtbuchersetmessages: + msg356424
2019-11-12 07:47:50brandtbuchersetpull_requests: + pull_request16621
2019-10-22 00:54:22brandtbuchersetpull_requests: + pull_request16423
2019-10-04 22:03:38serhiy.storchakasetmessages: + msg353974
2019-10-04 20:57:03brandtbuchersetmessages: + msg353973
2019-10-04 18:17:07brandtbuchersetmessages: + msg353965
2019-10-04 17:56:00serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg353964
2019-09-30 16:58:31brandtbuchersetkeywords: + patch
stage: patch review
pull_requests: + pull_request16087
2019-09-30 16:57:25brandtbuchercreate