◐ Shell
reader mode source ↗
Skip to content

gh-126868: Add freelist for compact int objects#126865

Merged
markshannon merged 25 commits into
python:mainfrom
eendebakpt:int_freelist
Dec 13, 2024
Merged

gh-126868: Add freelist for compact int objects#126865
markshannon merged 25 commits into
python:mainfrom
eendebakpt:int_freelist

Conversation

@eendebakpt

@eendebakpt eendebakpt commented Nov 15, 2024 •
edited
Loading

Copy link
Copy Markdown
Contributor

We can add freelists for the int object to improve performance. Using the new methods from #121934 the amount of code needed for adding a freelist is quite small. We only implement the freelist for compact ints (e.g. a single digit). For multi-digit int objects adding freelists is more complex (we need a size-based freelist) and the gains are smaller (for very large int objects the allocation is not a significant part of the computation time)

Notes:

  • The freelist size was chosen to be 100 (equal to the freelist size of float), but perhaps this can be tuned better
  • The long_dealloc and _PyLong_ExactDealloc are almost identical, we could keep just long_dealloc at the cost of a tiny bit of performance.

Some references to discussions on freelists

The freelist improves performance of int operations in microbenchmarks:

bench_long: Mean +- std dev: [main_long] 106 ns +- 5 ns -> [pr_long1c] 99.8 ns +- 4.4 ns: 1.07x faster
bench_alloc: Mean +- std dev: [main_long] 210 us +- 6 us -> [pr_long1c] 177 us +- 10 us: 1.19x faster

Benchmark hidden because not significant (1): bench_collatz

Geometric mean: 1.08x faster
Benchmark script 
# Quick benchmark for cpython long objects

import pyperf


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


def bench_collatz(loops):
    range_it = range(loops)
    t0 = pyperf.perf_counter()
    for ii in range_it:
        collatz(ii)
    return pyperf.perf_counter() - t0


def bench_long(loops):
    range_it = range(loops)
    t0 = pyperf.perf_counter()
    x = 10
    for ii in range_it:
        x = x * x
        y = x // 2
        x = y + ii + x
        if x > 10**10:
            x = x % 1000
    return pyperf.perf_counter() - t0


def bench_alloc(loops):
    range_it = range(loops)
    t0 = pyperf.perf_counter()
    for ii in range_it:
        for kk in range(20_000):
            del kk
    return pyperf.perf_counter() - t0


# %timeit bench_long(1000)

if __name__ == "__main__":
    runner = pyperf.Runner()
    runner.bench_time_func("bench_collatz", bench_collatz)
    runner.bench_time_func("bench_long", bench_long)
    runner.bench_time_func("bench_alloc", bench_alloc)

On the pyperformance test suite (actually, a subset of the suite, not all benchmarks run on my system) shows the percentage of successfull freelist allocations increases significantly

Main:

Allocations from freelist 	2,004,971,371 	39.8%
Frees to freelist 	2,005,350,418 	
Allocations 	3,034,877,938 	60.2%
Allocations to 512 bytes 	3,008,791,812 	59.7%
Allocations to 4 kbytes 	18,648,072 	0.4%
Allocations over 4 kbytes 	7,438,054 	0.1%
Frees 	3,142,033,922

PR

Allocations from freelist 	3,058,347,887 	58.6%
Frees to freelist 	3,058,576,117 	
Allocations 	2,159,771,546 	41.4%
Allocations to 512 bytes 	2,133,373,693 	40.9%
Allocations to 4 kbytes 	18,802,328 	0.4%
Allocations over 4 kbytes 	7,595,525 	0.1%
Frees 	2,267,538,686

@eendebakpt eendebakpt changed the title Draft: Add freelist of compact int objects Nov 15, 2024
@eendebakpt eendebakpt marked this pull request as draft November 15, 2024 12:50
@bedevere-app bedevere-app Bot mentioned this pull request Nov 15, 2024
Closed
@mdboom

mdboom commented Nov 15, 2024

Copy link
Copy Markdown
Contributor

I'm running this PR over pyperformance on our benchmarking hardware. It will take ~3 hours.

@mdboom

mdboom commented Nov 15, 2024

Copy link
Copy Markdown
Contributor

I'm running this PR over pyperformance on our benchmarking hardware. It will take ~3 hours.

Actually, scratch that -- I'll wait until the tests are passing here. That's required for PGO builds.

@eendebakpt

eendebakpt commented Nov 16, 2024

Copy link
Copy Markdown
Contributor Author

Tests are passing now, but I disabled returning objects to the freelist at a couple of places. Changing PyObject_Free to _PyLong_ExactDealloc on the lines of code marked with "needs to be converted to freelist" introduces refleaks. It seems related to #125323. @fidgetSpinner Do you perhaps have an idea what is going on?

@markshannon

markshannon commented Nov 18, 2024

Copy link
Copy Markdown
Member

What happens exactly when you change these lines:

PyStackRef_CLOSE_SPECIALIZED(left, (destructor)PyObject_Free); // needs to be converted to freelist

to

PyStackRef_CLOSE_SPECIALIZED(left, (destructor)_PyLong_ExactDealloc);

?

@eendebakpt

eendebakpt commented Nov 18, 2024

Copy link
Copy Markdown
Contributor Author

@markshannon When I change the lines several tests related to refleaks in the CI are failing. For example test_no_memleak, which can be reproduced from the command line with:

python -Xshowrefcount -c  "[x+x*x for x in range(1000)]"

The output should be [0 refs, 0 blocks], but instead I get [982 refs, 0 blocks] (exact numbers depending on which lines I change and the exact code executed).

Fidget-Spinner
Fidget-Spinner reviewed Nov 20, 2024
View reviewed changes

@Fidget-Spinner Fidget-Spinner 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.

Hide comment

The "leaks" are due to the freelist itself. They are a sign the freelist is working :).
Can you please convert all to _PyLong_ExactDealloc and apply the suggestion below, and tell me how many allocations this removes?

@Fidget-Spinner

Fidget-Spinner commented Nov 20, 2024

Copy link
Copy Markdown
Member

@eendebakpt sorry I pushed to your branch as I'm really eager to get benchmark results on this :).

@Fidget-Spinner

Fidget-Spinner commented Nov 20, 2024 •
edited
Loading

Copy link
Copy Markdown
Member

On my machine using the benchmark script provided above (release build, no PGO, no LTO):

bench_collatz: Mean +- std dev: [without_freelist] 9.41 us +- 0.08 us -> [with_freelist] 9.22 us +- 0.08 us: 1.02x faster
bench_long: Mean +- std dev: [without_freelist] 187 ns +- 1 ns -> [with_freelist] 164 ns +- 2 ns: 1.14x faster
bench_alloc: Mean +- std dev: [without_freelist] 411 us +- 4 us -> [with_freelist] 333 us +- 2 us: 1.24x faster

Geometric mean: 1.13x faster

@Fidget-Spinner

Fidget-Spinner commented Nov 21, 2024 •
edited
Loading

Copy link
Copy Markdown
Member

Results:

This is a great result! Congrats and great work @eendebakpt !

picnixz
picnixz reviewed Nov 21, 2024
View reviewed changes

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

Hide comment

Out of curiosity, are compact integers allowed to be signed or not? (you mentioned that we only focus on single digit numbers but the C API considers compact objects as being an implementation detail IIRC). If not, how hard would it be to make them support free lists? (I don't have much knowledge in free lists; for instance it's a mystery to me for how the free list grows)

31 hidden items Load more…
@bedevere-app

bedevere-app Bot commented Dec 4, 2024

Copy link
Copy Markdown

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.

@eendebakpt

eendebakpt commented Dec 7, 2024

Copy link
Copy Markdown
Contributor Author

The generated files need to be regenerated, and I'd like to rerun the benchmarks to confirm the additional small int checks don't impact performance too much.

I assume you mean the small int checks in _PyLong_ExactDealloc? In current main these checks are not present (PyObject_Free is called directly), so we could argue they are not needed in _PyLong_ExactDealloc either. On the other hand, if I understand things well to be correct they should be added.

@eendebakpt

eendebakpt commented Dec 9, 2024

Copy link
Copy Markdown
Contributor Author

I have made the requested changes; please review again

@bedevere-app

bedevere-app Bot commented Dec 9, 2024

Copy link
Copy Markdown

Thanks for making the requested changes!

@markshannon: please review the changes made to this pull request.

@bedevere-app bedevere-app Bot requested a review from markshannon December 9, 2024 10:42
@markshannon

markshannon commented Dec 12, 2024

Copy link
Copy Markdown
Member

0.6% speedup

markshannon
markshannon approved these changes Dec 12, 2024
View reviewed changes

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

Hide comment

Thanks for doing this. The code looks good now.

The speedup may not be as large as initially claimed due to addition checks for small integers, but it is a real speedup and should be further improved by #127620

@markshannon

markshannon commented Dec 12, 2024

Copy link
Copy Markdown
Member

It seems likely the thread sanitizer failure is not caused by this PR, but this PR does expose it.
Hopefully it will be fixed soon, but we'll need to wait a bit before merging this PR.

@colesbury

colesbury commented Dec 12, 2024

Copy link
Copy Markdown
Contributor

TSan failure is addressed in #127880.

@colesbury colesbury mentioned this pull request Dec 12, 2024
Merged
@colesbury

colesbury commented Dec 12, 2024

Copy link
Copy Markdown
Contributor

The TSan failure is fixed in main now, if you want to merge main back into the PR.

@markshannon markshannon merged commit 5fc6bb2 into python:main Dec 13, 2024
@markshannon markshannon mentioned this pull request Dec 13, 2024
Merged
@bedevere-bot

bedevere-bot commented Dec 13, 2024

Copy link
Copy Markdown

⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️

Hi! The buildbot iOS ARM64 Simulator 3.x has failed when building commit 5fc6bb2.

What do you need to do:

  1. Don't panic.
  2. Check the buildbot page in the devguide if you don't know what the buildbots are or how they work.
  3. Go to the page of the buildbot that failed (https://buildbot.python.org/#/builders/1380/builds/2109) and take a look at the build logs.
  4. Check if the failure is related to this commit (5fc6bb2) or if it is a false positive.
  5. If the failure is related to this commit, please, reflect that on the issue and make a new Pull Request with a fix.

You can take a look at the buildbot page here:

https://buildbot.python.org/#/builders/1380/builds/2109

Summary of the results of the build (if available):

==

Click to see traceback logs 
Traceback (most recent call last):

srinivasreddy pushed a commit to srinivasreddy/cpython that referenced this pull request Jan 8, 2025
@eendebakpt @srinivasreddy
pythongh-126868: Add freelist for compact int objects (pythonGH-126865)
abf3b83
@dg-pb dg-pb mentioned this pull request Apr 24, 2025
Closed
@KRRT7 KRRT7 mentioned this pull request May 28, 2026
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@picnixz picnixz picnixz left review comments

@Fidget-Spinner Fidget-Spinner Fidget-Spinner left review comments

@markshannon markshannon

@ericsnowcurrently ericsnowcurrently Awaiting requested review from ericsnowcurrently ericsnowcurrently is a code owner

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

7 participants

@eendebakpt @mdboom @markshannon @Fidget-Spinner @colesbury @bedevere-bot @picnixz