Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
brandtbucher opened this issue Sep 30, 2019 · 7 comments
Closed

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

brandtbucher opened this issue Sep 30, 2019 · 7 comments
Labels
3.9 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@brandtbucher
Copy link
Member

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
    Copy link
    Member Author

    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.

    @brandtbucher brandtbucher added 3.9 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Sep 30, 2019
    @serhiy-storchaka
    Copy link
    Member

    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
    Copy link
    Member Author

    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
    Copy link
    Member Author

    ...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
    Copy link
    Member

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

    @brandtbucher
    Copy link
    Member Author

    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.

    @brandtbucher brandtbucher changed the title Speed up the creation time of constant list literals. Speed up the creation time of constant list and set literals. Nov 12, 2019
    @methane
    Copy link
    Member

    methane commented Nov 26, 2019

    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

    @methane methane closed this as completed Nov 26, 2019
    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    3.9 only security fixes interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Development

    No branches or pull requests

    3 participants