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 — gh-126703: Add freelists for iterators and range, method and builtin_function_or_method objects by eendebakpt · Pull Request #128368 · python/cpython

Conversation

@eendebakpt

@eendebakpt eendebakpt commented Dec 30, 2024 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Contributor

In this PR we add freelists for the top most allocated objects (measured using pyperformance benchmark). Some often allocated objects that have not yet been added: ints with 2 or 3 digits, exceptions (StopIteration, IndexError) and generators.

If the freelists increase performance, the PR should probably be split into multiple ones.

Microbenchmarks:

bench_list: Mean +- std dev: [main] 14.9 us +- 0.2 us -> [pr] 14.5 us +- 0.3 us: 1.03x faster
bench_int: Mean +- std dev: [main] 383 us +- 5 us -> [pr] 386 us +- 7 us: 1.01x slower
bench_float: Mean +- std dev: [main] 113 us +- 2 us -> [pr] 111 us +- 3 us: 1.02x faster
bench_builtin_or_method: Mean +- std dev: [main] 6.14 us +- 0.45 us -> [pr] 4.17 us +- 0.07 us: 1.47x faster
bench_list_iter: Mean +- std dev: [main] 141 ns +- 4 ns -> [pr] 126 ns +- 4 ns: 1.12x faster
bench_tuple_iter: Mean +- std dev: [main] 140 ns +- 7 ns -> [pr] 125 ns +- 2 ns: 1.12x faster
bench_range_iter: Mean +- std dev: [main] 144 ns +- 5 ns -> [pr] 138 ns +- 3 ns: 1.04x faster
bench_property: Mean +- std dev: [main] 2.06 us +- 0.04 us -> [pr] 2.03 us +- 0.02 us: 1.01x faster
bench_class_method: Mean +- std dev: [main] 2.30 us +- 0.02 us -> [pr] 2.32 us +- 0.05 us: 1.01x slower

Geometric mean: 1.08x faster

The list, float and int freelists are already in main, so we don't expect an improvement there. The iterator benchmarks show a modest improvement. bench_builtin_or_method shows an improvement, but is a a bit artificial benchmark.

Benchmark script
# Quick benchmark for cpython freelists

import pyperf


def bench_list(loops):
    range_it = iter(range(loops))
    tpl = tuple(range(100))

    t0 = pyperf.perf_counter()
    for ii in range_it:
        for ii in tpl:
            _ = [ii]
            _ = [ii, ii + 1]
            _ = [ii, ii + 1, ii]
    return pyperf.perf_counter() - t0


def collatz(a):
    while a > 1:
        if a % 2 == 0:
            a = a // 2
        else:
            a = 3 * a + 1


def bench_int(loops):
    range_it = range(loops)
    tpl = tuple(range(200, 300))

    t0 = pyperf.perf_counter()
    for ii in range_it:
        for jj in tpl:
            collatz(jj)
    return pyperf.perf_counter() - t0


def bench_float(loops):
    range_it = iter(range(loops))
    tpl = tuple(range(500))

    t0 = pyperf.perf_counter()
    for ii in range_it:
        x = 0
        for ii in tpl:
            x += float(ii + 1) ** 2 - float(ii + 1) ** 2
    return pyperf.perf_counter() - t0


def bench_builtin_or_method(loops):
    range_it = iter(range(loops))
    tpl = tuple(range(50))

    lst = []
    it = iter(set([2, 3, 4]))
    t0 = pyperf.perf_counter()
    for ii in range_it:
        for ii in tpl:
            lst.append
            it.__length_hint__
    return pyperf.perf_counter() - t0


class A:
    def __init__(self, value):
        self.value = value

    def x(self):
        return self.value

    @property
    def v(self):
        return self.value


def bench_property(loops):
    range_it = iter(range(loops))
    tpl = tuple(range(50))

    t0 = pyperf.perf_counter()
    for ii in range_it:
        a = A(ii)
        for ii in tpl:
            _ = a.v
    return pyperf.perf_counter() - t0


def bench_class_method(loops):
    range_it = iter(range(loops))
    tpl = tuple(range(50))

    t0 = pyperf.perf_counter()
    for ii in range_it:
        a = A(ii)
        for ii in tpl:
            _ = a.x()
    return pyperf.perf_counter() - t0


def bench_list_iter(loops):
    range_it = iter(range(loops))

    lst = list(range(5))
    t0 = pyperf.perf_counter()
    for ii in range_it:
        x = 0
        for ii in lst:
            x += ii
    return pyperf.perf_counter() - t0


def bench_tuple_iter(loops):
    range_it = iter(range(loops))

    tpl = tuple(range(5))
    t0 = pyperf.perf_counter()
    for ii in range_it:
        x = 0
        for ii in tpl:
            x += ii
    return pyperf.perf_counter() - t0


def bench_range_iter(loops):
    range_it = iter(range(loops))

    r = range(5)
    t0 = pyperf.perf_counter()
    for ii in range_it:
        x = 0
        for ii in r:
            x += ii
    return pyperf.perf_counter() - t0


# %timeit bench_list(1000)

if __name__ == "__main__":
    runner = pyperf.Runner()
    runner.bench_time_func("bench_list", bench_list)
    runner.bench_time_func("bench_int", bench_int)
    runner.bench_time_func("bench_float", bench_float)
    runner.bench_time_func("bench_builtin_or_method", bench_builtin_or_method)
    runner.bench_time_func("bench_list_iter", bench_list_iter)
    runner.bench_time_func("bench_tuple_iter", bench_tuple_iter)
    runner.bench_time_func("bench_range_iter", bench_range_iter)
    runner.bench_time_func("bench_property", bench_property)
    runner.bench_time_func("bench_class_method", bench_class_method)
  • Issue: Use freelist for range object, iterator objects and other often used objects #126703

Sorry, something went wrong.

Uh oh!

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

All reactions
eendebakpt added 5 commits December 29, 2024 22:48
@eendebakpt
Use freelist for range object
cb83490
@eendebakpt
Use freelist for rangeiter object
6adf31c
@eendebakpt
cleanup debug code
94cbc7c
@eendebakpt
set types
17100c0
@eendebakpt
add more freelists
ea98fa1
@eendebakpt
eendebakpt requested a review from ericsnowcurrently as a code owner December 30, 2024 22:33
@bedevere-app bedevere-app Bot mentioned this pull request Dec 30, 2024
Use freelist for range object, iterator objects and other often used objects #126703
Closed
@bedevere-app bedevere-app Bot added the awaiting review label Dec 30, 2024
@eendebakpt
eendebakpt marked this pull request as draft December 30, 2024 22:34
@bedevere-app bedevere-app Bot removed the awaiting review label Dec 30, 2024
eendebakpt added 5 commits January 1, 2025 20:16
@eendebakpt
clear freelists
64be6c4
@eendebakpt
freelist for range iterators
2551f29
@eendebakpt
enable all freelists again
fce4651
@eendebakpt
add PyCFunctionObject
5d13675
@eendebakpt
Merge branch 'main' into iter_freelists
e296fbb
@Fidget-Spinner

Fidget-Spinner commented Jan 1, 2025

Copy link
Copy Markdown
Member

I don't think we should share the freelists for iterators. We're not using that much memory and it's really bug-prone to share them.

All reactions

Sorry, something went wrong.

Uh oh!

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

@eendebakpt

eendebakpt commented Jan 1, 2025

Copy link
Copy Markdown
Contributor Author

I don't think we should share the freelists for iterators. We're not using that much memory and it's really bug-prone to share them.

I agree with you. I am experimenting a bit to see whether it is possible at all to do this this with different types (maybe for PyType_GenericAlloc, or some size based freelist), but for the iterators I will probably split it again.

All reactions

Sorry, something went wrong.

Uh oh!

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

@eendebakpt
Merge branch 'main' into iter_freelists
05f479c
@ericsnowcurrently

ericsnowcurrently commented Jan 3, 2025

Copy link
Copy Markdown
Member

benchmarking results: https://github.com/faster-cpython/benchmarking-public/tree/main/results/bm-20250102-3.14.0a3%2B-05f479c

All reactions

Sorry, something went wrong.

Uh oh!

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

@Fidget-Spinner

Fidget-Spinner commented Jan 3, 2025

Copy link
Copy Markdown
Member

The results are excellent! 1% faster geomean. Great work and congrats Pieter!

ericsnowcurrently reacted with hooray emoji
All reactions
  • 🎉 1 reaction

Sorry, something went wrong.

Uh oh!

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

@corona10

corona10 commented Jan 3, 2025

Copy link
Copy Markdown
Member

I am not sure that it's worth adding the free list every time if there is a small margin (<3-5%).
Maybe we should trade-off between complexity and maintainability. (Not a strong disagree FYI)

All reactions

Sorry, something went wrong.

Uh oh!

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

@corona10

corona10 commented Jan 3, 2025

Copy link
Copy Markdown
Member

pycfunctionobject / pycmethodobject / class_method / shared_iters are maybe good to be added.
But not sure about ranges / range_iters..

All reactions

Sorry, something went wrong.

Uh oh!

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

@Fidget-Spinner

Fidget-Spinner commented Jan 3, 2025

Copy link
Copy Markdown
Member

I am not sure that it's worth adding the free list every time if there is a small margin (<3-5%).

Maybe we should trade-off between complexity and maintainability. (Not a strong disagree FYI)

Benchmark results show consistent 1% geomean speedup on pyperformance. That's pretty worth it (for comparison, the entire types optimizer in the JIT is only 1% speedup and is way more code). Though you're probably right that not all of them are worth it. I'm thinking the method and list/tuple iters are most worth it.

All reactions

Sorry, something went wrong.

Uh oh!

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

This was referenced Jan 7, 2025
gh-126703: Add freelists for list and tuple iterators #128592
Merged
gh-126703: Add freelist for PyMethodObject #128594
Merged
gh-126703: Add freelist for range and range_iter objects #128619
Merged
gh-126703: Add PyCFunction freelist #128692
Merged
@eendebakpt

eendebakpt commented Jan 10, 2025

Copy link
Copy Markdown
Contributor Author

I made PRs for the individual components that are worthwhile (based on the stats). The ones that do not have a PR yet (because the implementation would be more complex) are generators, StopIteration (or more general exceptions) and ints of small size (e.g. 2 of 3).

I will close this PR as it is superseded by the others.

All reactions

Sorry, something went wrong.

Uh oh!

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

@vstinner

vstinner commented Jan 13, 2025

Copy link
Copy Markdown
Member

bench_builtin_or_method: Mean +- std dev: [main] 6.14 us +- 0.45 us -> [pr] 4.17 us +- 0.07 us: 1.47x faster

This one looks promising. Maybe start to extract this free list from your PR as a new PR?

All reactions

Sorry, something went wrong.

Uh oh!

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

@eendebakpt

eendebakpt commented Jan 14, 2025

Copy link
Copy Markdown
Contributor Author

bench_builtin_or_method: Mean +- std dev: [main] 6.14 us +- 0.45 us -> [pr] 4.17 us +- 0.07 us: 1.47x faster

This one looks promising. Maybe start to extract this free list from your PR as a new PR?

I created 4 followup PRs. The bench_builtin_or_method is in #128692.

All reactions

Sorry, something went wrong.

Uh oh!

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

@eendebakpt

eendebakpt commented Apr 2, 2025

Copy link
Copy Markdown
Contributor Author

Closing in favor of the individual PRs

vstinner reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

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

@eendebakpt eendebakpt closed this Jul 1, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@ericsnowcurrently ericsnowcurrently Awaiting requested review from ericsnowcurrently ericsnowcurrently is a code owner
@ZeroIntensity ZeroIntensity Awaiting requested review from ZeroIntensity ZeroIntensity will be requested when the pull request is marked ready for review ZeroIntensity is a code owner

Uh oh!

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

Assignees

No one assigned

Labels

None yet

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

@eendebakpt @Fidget-Spinner @ericsnowcurrently @corona10 @vstinner
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.