GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — bpo-47009: Streamline list.append for the common case by sweeneyde · Pull Request #31864 · python/cpython

Conversation

@sweeneyde

@sweeneyde sweeneyde commented Mar 14, 2022 •
edited by bedevere-bot
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

https://bugs.python.org/issue47009

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@sweeneyde
sweeneyde requested a review from markshannon as a code owner March 14, 2022 04:58
@bedevere-bot bedevere-bot added the awaiting core review label Mar 14, 2022
@the-knights-who-say-ni the-knights-who-say-ni added the CLA signed label Mar 14, 2022
@sweeneyde

sweeneyde commented Mar 14, 2022 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

Benchmarks are good:

from pyperf import Runner, perf_counter

def bench_listcomp(loops, length):
    src = list(map(float, range(length)))
    t0 = perf_counter()
    for i in range(loops):
        [x for x in src]
    return perf_counter() - t0

def bench_append(loops, length):
    src = list(map(float, range(length)))
    t0 = perf_counter()
    for i in range(loops):
        arr = []
        for x in src:
            arr.append(x)
    return perf_counter() - t0

runner = Runner()
for n in [100, 1_000, 10_000, 100_000]:
    runner.bench_time_func(f"listcomp {n}", bench_listcomp, n)
    runner.bench_time_func(f"append {n}", bench_append, n)

Results from GCC on WSL with --enable-optimizations --with-lto

Faster (8):
- listcomp 10000: 118 us +- 2 us -> 92.6 us +- 1.5 us: 1.28x faster
- listcomp 100000: 1.16 ms +- 0.02 ms -> 916 us +- 26 us: 1.27x faster
- listcomp 1000: 12.3 us +- 0.2 us -> 9.89 us +- 0.41 us: 1.25x faster
- listcomp 100: 1.59 us +- 0.03 us -> 1.32 us +- 0.05 us: 1.21x faster
- append 100000: 1.69 ms +- 0.05 ms -> 1.45 ms +- 0.04 ms: 1.17x faster
- append 10000: 168 us +- 4 us -> 145 us +- 3 us: 1.16x faster
- append 1000: 17.4 us +- 0.3 us -> 15.2 us +- 0.6 us: 1.14x faster
- append 100: 2.03 us +- 0.06 us -> 1.81 us +- 0.08 us: 1.12x faster

Geometric mean: 1.20x faster
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@sweeneyde
sweeneyde requested a review from methane March 14, 2022 05:16
@sweeneyde sweeneyde added the performance Performance or resource usage label Mar 14, 2022
@sweeneyde
Streamline list.append for the common case
a240df1
@sweeneyde
sweeneyde force-pushed the listappend branch from f1951b6 to a240df1 Compare March 14, 2022 09:43
@blurb-it
📜🤖 Added by blurb_it.
e038176
markshannon
markshannon reviewed Mar 18, 2022
View reviewed changes

@markshannon markshannon left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this would be simpler, and just as fast, by renaming app1 to _PyList_AppendTakeRef (with appropriate refcount adjustments).
No need for the inline functions.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Include/internal/pycore_list.h
PyAPI_FUNC(int)
_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem);

static inline int

@markshannon markshannon Mar 18, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No need for an inline function.
Let the LTO pass decide if it wants to inline it.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Objects/listobject.c
app1(PyListObject *self, PyObject *v)
/* internal, used by _PyList_AppendTakeRef */
int
_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)

@markshannon markshannon Mar 18, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do we need the extra function?
Converting app1 to _PyList_AppendTakeRef would seem to be enough.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@sweeneyde sweeneyde Mar 18, 2022

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I tried something like that and the results are on the bpo issue, but it seems there is a significant benefit to having the separate as-small-as-possible function that always gets inlined as opposed to a slightly longer version that we let the compiler figure out.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@markshannon markshannon Mar 18, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Presumably the compiler isn't inlining the function because it isn't hot enough.
PRECALL_NO_KW_LIST_APPEND and LIST_APPEND are only 0.3% of all instructions executed, so maybe it is best not to inline.

Do you have benchmark numbers for the standard suite?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@sweeneyde sweeneyde Mar 18, 2022

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

https://gist.github.com/sweeneyde/6cbbe1c9d216d117370a809c704b6cfc

Geometric mean: 1.00x faster

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@sweeneyde sweeneyde Mar 18, 2022

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also, IMO there is a relative lack of list comprehensions in the pyperformance suite.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
kumaraditya303
kumaraditya303 reviewed Mar 21, 2022
View reviewed changes
Comment thread Include/internal/pycore_list.h Resolved

Uh oh!

There was an error while loading. Please reload this page.

sweeneyde and others added 2 commits March 21, 2022 03:21
@sweeneyde
PyAPI_FUNC --> extern
8ad202f
@sweeneyde
Merge branch 'main' into listappend
ea3f634
@sweeneyde

sweeneyde commented Mar 31, 2022

Copy link
Copy Markdown
Member Author

@markshannon Since pyperformance results were negligible and this has a significant speedup on operations that live in hot loops (albeit not in pyperformance), is it okay if I merge this?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@markshannon

markshannon commented Apr 1, 2022

Copy link
Copy Markdown
Member

Sorry, this dropped off my radar.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@markshannon
markshannon merged commit a0ea7a1 into python:main Apr 1, 2022
@bedevere-bot bedevere-bot removed the awaiting core review label Apr 1, 2022
@sweeneyde
sweeneyde deleted the listappend branch April 1, 2022 16:13
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@markshannon markshannon markshannon left review comments
@kumaraditya303 kumaraditya303 kumaraditya303 left review comments
@methane methane Awaiting requested review from methane

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

performance Performance or resource usage

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

5 participants

@sweeneyde @markshannon @kumaraditya303 @the-knights-who-say-ni @bedevere-bot
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.