FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

bpo-47009: Streamline list.append for the common case by sweeneyde · Pull Request #31864 · python/cpython · GitHub

/ cpython Public

bpo-47009: Streamline list.append for the common case - #31864

Merged
markshannon merged 4 commits into
python:mainfrom
sweeneyde:listappend
Apr 1, 2022
ConversationCommits (4)ChecksFiles changed
Merged

bpo-47009: Streamline list.append for the common case#31864
markshannon merged 4 commits into
python:mainfrom
sweeneyde:listappend

Conversation

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

Copy link
Copy Markdown
Member

sweeneyde requested a review from markshannon as a code owner March 14, 2022 04:58

sweeneyde commented Mar 14, 2022 •
edited
Loading

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

sweeneyde requested a review from methane March 14, 2022 05:16
sweeneyde added the performance Performance or resource usage label Mar 14, 2022
markshannon reviewed Mar 18, 2022
View reviewed changes

markshannon left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

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.

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

static inline int

markshannon Mar 18, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

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

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

markshannon Mar 18, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

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

sweeneyde Mar 18, 2022

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

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.

markshannon Mar 18, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

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?

sweeneyde Mar 18, 2022

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

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

Geometric mean: 1.00x faster

sweeneyde Mar 18, 2022

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

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

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

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?

markshannon commented Apr 1, 2022

Copy link
Copy Markdown
Member

Sorry, this dropped off my radar.

markshannon merged commit a0ea7a1 into python:main Apr 1, 2022
sweeneyde deleted the listappend branch April 1, 2022 16:13
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

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

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.

5 participants

Back | FazBrowse Home | New Git URL