Speed up the creation time of constant list and set literals.

[brandtbucher]

BPO	38328
Nosy	@serhiy-storchaka, @brandtbucher
PRs	bpo-38328: Speed up the creation time of constant list literals. #16498 bpo-38328: Speed up the creation time of constant set literals. #16878 bpo-38328: Speed up the creation time of constant list and set literals. #17114

^{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 = None
closed_at = <Date 2019-11-26.06:17:35.396>
created_at = <Date 2019-09-30.16:57:25.330>
labels = ['interpreter-core', '3.9', 'performance']
title = 'Speed up the creation time of constant list and set literals.'
updated_at = <Date 2019-11-26.06:17:35.391>
user = 'https://github.com/brandtbucher'

bugs.python.org fields:

activity = <Date 2019-11-26.06:17:35.391>
actor = 'methane'
assignee = 'none'
closed = True
closed_date = <Date 2019-11-26.06:17:35.396>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2019-09-30.16:57:25.330>
creator = 'brandtbucher'
dependencies = []
files = []
hgrepos = []
issue_num = 38328
keywords = ['patch']
message_count = 7.0
messages = ['353599', '353964', '353965', '353973', '353974', '356424', '357484']
nosy_count = 2.0
nosy_names = ['serhiy.storchaka', 'brandtbucher']
pr_nums = ['16498', '16878', '17114']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue38328'
versions = ['Python 3.9']

[brandtbucher]

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.

[serhiy-storchaka]

Great! I withdrew the original proposition in bpo-33325 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

[brandtbucher]

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.

[brandtbucher]

...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.

[serhiy-storchaka]

Okay, but first I want to solve an issue with list overallocation.

[brandtbucher]

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.

[methane]

New changeset 6dd9b64 by Inada Naoki (Brandt Bucher) in branch 'master':
bpo-38328: Speed up the creation time of constant list and set display. (GH-17114)
6dd9b64