Potentially serious regression in garbage collector performance in Python 3.14

[pgdr]

Bug report

Bug description:

The following code, consisting of a bunch of dict lookups and writes, runs in

• < 1 second on Python 3.13
• > 2 seconds on Python 3.14

n = 1000
d = {}
for i in range(n):
    d[(i, i)] = d[(i, 0)] = d[(0, i)] = 0
for i in range(1, n):
    for j in range(1, n):
        d[(i, j)] = i + j + d[(i - 1, j)] + d[(i, j - 1)] + d[(i - 1, j - 1)]
print(d[(n - 1, n - 1)])

Tests are run on a Dell Precision 5490, running Ubuntu:

Linux precision 6.14.0-33-generic #33-Ubuntu SMP PREEMPT_DYNAMIC Wed Sep 17 23:22:02 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux

Ubuntu 25.04 (Plucky)

The cpython is from python-build-standalone

• cpython-3.14.0+20251010-x86_64-unknown-linux-gnu-install_only.tar.gz
• cpython-3.13.8+20251010-x86_64-unknown-linux-gnu-install_only.tar.gz

Log

[~/regression-testing]$ hyperfine --warmup=10 "cp313/python/bin/python3.13 dicttest.py" "cp314/python/bin/python3.14 dicttest.py"
Benchmark 1: cp313/python/bin/python3.13 dicttest.py
  Time (mean ± σ):     880.8 ms ± 119.7 ms    [User: 730.1 ms, System: 150.1 ms]
  Range (min … max):   713.3 ms … 1066.2 ms    10 runs
 
Benchmark 2: cp314/python/bin/python3.14 dicttest.py
  Time (mean ± σ):      2.235 s ±  0.035 s    [User: 2.066 s, System: 0.168 s]
  Range (min … max):    2.168 s …  2.295 s    10 runs
 
Summary
  cp313/python/bin/python3.13 dicttest.py ran
    2.54 ± 0.35 times faster than cp314/python/bin/python3.14 dicttest.py

It seems to scale very poorly too. With the same code, but n = 2000 (instead of n = 1000), leads to 3.3 sec (Python 3.13) vs 20 seconds (Python 3.14)! I.e., Python 3.13 being 5 times faster.

[~/regression-testing]$ hyperfine --warmup=10 "cp313/python/bin/python3.13 dicttest.py" "cp314/python/bin/python3.14 dicttest.py"
Benchmark 1: cp313/python/bin/python3.13 dicttest.py
  Time (mean ± σ):      3.458 s ±  0.048 s    [User: 2.889 s, System: 0.568 s]
  Range (min … max):    3.375 s …  3.521 s    10 runs
 
Benchmark 2: cp314/python/bin/python3.14 dicttest.py
  Time (mean ± σ):     20.084 s ±  0.230 s    [User: 19.503 s, System: 0.577 s]
  Range (min … max):   19.749 s … 20.345 s    10 runs
 
Summary
  cp313/python/bin/python3.13 dicttest.py ran
    5.81 ± 0.10 times faster than cp314/python/bin/python3.14 dicttest.py

Plotting time (in seconds) of the script run with n = 0 ... 2000.

CPython versions tested on:

3.14

Operating systems tested on:

Linux

Linked PRs

• gh-139951: Do not track immutable tuples in GC #140204
• GH-139951: Fix major GC performance regression #140262
• gh-139951: Test on GC collection disabled if threshold is zero #140304

[picnixz]

This looks similar to #137636 and the issue was PGO magic. The issue was explicitly for dict[int, int] and hash collisions algorithm.

[pgdr]

@picnixz It could be that it is some hash collision/PGO stuff, but by bisecting, I found that the first commit that makes the following code run in more than just a couple of seconds, is e28477f (from #117120 --- Change the size of the GC increment to about 1% of the total heap size).

• In e28477f the code takes more than a minute to run
• In e2e0b4b the code runs in 4 seconds.

n = 2000
d = {}
for i in range(n):
    d[(i, i)] = d[(i, 0)] = d[(0, i)] = 0
for i in range(1, n):
    for j in range(1, n):
        d[(i, j)] = (
            i + j + d[(i - 1, j)] + d[(i, j - 1)] + d[(i - 1, j - 1)]
        ) % ((2**20) - 1)
print((d[(n - 1, n - 1)] % 2) != 0)

That said, the code base today runs the code in around 20 seconds on my computer. Which means that Python went from 4 seconds to 60 seconds down to 20 seconds.

Appendix: bisection log

git bisect start
# status: waiting for both good and bad commits
# bad: [52996aaa78706e0f2a70953feaf97b474eb438e7] gh-107073: fix relevant typo in `PyObject_ClearManagedDict` (#140032)
git bisect bad 52996aaa78706e0f2a70953feaf97b474eb438e7
# status: waiting for good commit(s), bad commit known
# good: [357bed0bcd3c5d7c4a8caad451754a9a172aca3e] GH-104668: Don't call PyOS_* hooks in subinterpreters (GH-104674)
git bisect good 357bed0bcd3c5d7c4a8caad451754a9a172aca3e
# bad: [422855ad21f09b82c0bfa891dfb8fb48182c6d2b] gh-120823: Fix doc for ftplib.FTP.retrbinary() (GH-121697)
git bisect bad 422855ad21f09b82c0bfa891dfb8fb48182c6d2b
# good: [cfa25fe3e39e09612a6ba8409c46cf35a091de3c] gh-113149: Improve error message when JSON has trailing comma (GH-113227)
git bisect good cfa25fe3e39e09612a6ba8409c46cf35a091de3c
# bad: [26d328b2ba26374fb8d9ffe8215ecef7c5e3f7a2] GH-117121: Add pystats to JIT builds (GH-117346)
git bisect bad 26d328b2ba26374fb8d9ffe8215ecef7c5e3f7a2
# good: [72340d15cdfdfa4796fdd7c702094c852c2b32d2] gh-114563: C decimal falls back to pydecimal for unsupported format strings (GH-114879)
git bisect good 72340d15cdfdfa4796fdd7c702094c852c2b32d2
# good: [eb22e2b251002b65f3b93e67c990c21e1151b25d] gh-115490: Make the interpreter.channels and interpreter.queues Modules Handle Reloading Properly (gh-115493)
git bisect good eb22e2b251002b65f3b93e67c990c21e1151b25d
# good: [ce2c996b2f645cd886d05f6ef8f1ba60ced7d4b7] gh-111926: Simplify proxy creation logic (#116844)
git bisect good ce2c996b2f645cd886d05f6ef8f1ba60ced7d4b7
# good: [f4cc77d494ee0e10ed84ce369f0910c70a2f6d44] gh-116869: Enable -Werror in test_cext for Free Threading (#117106)
git bisect good f4cc77d494ee0e10ed84ce369f0910c70a2f6d44
# bad: [507896d97dcff2d7999efa264b29d9003c525c49] gh-116936: Add PyType_GetModuleByDef() to the limited C API (#116937)
git bisect bad 507896d97dcff2d7999efa264b29d9003c525c49
# good: [42ae924d278c48a719fb0ab86357f3235a9f7ab9] gh-117127: glob tests: Reopen dir_fd to pick up directory changes (GH-117128)
git bisect good 42ae924d278c48a719fb0ab86357f3235a9f7ab9
# bad: [f11d0d8be8af28e1368c3c7c116218cf65ddf93e] gh-91227: Ignore ERROR_PORT_UNREACHABLE in proactor recvfrom() (#32011)
git bisect bad f11d0d8be8af28e1368c3c7c116218cf65ddf93e
# good: [5a78f6e798d5c2af1dba2df6c9f1f1e5aac02a86] gh-117134: Microoptimize glob() for include_hidden=True (GH-117135)
git bisect good 5a78f6e798d5c2af1dba2df6c9f1f1e5aac02a86
# bad: [e28477f214276db941e715eebc8cdfb96c1207d9] GH-117108: Change the size of the GC increment to about 1% of the total heap size. (GH-117120)
git bisect bad e28477f214276db941e715eebc8cdfb96c1207d9
# good: [e2e0b4b4b92694ba894e02b4a66fd87c166ed10f] gh-113024: C API: Add PyObject_GenericHash() function (GH-113025)
git bisect good e2e0b4b4b92694ba894e02b4a66fd87c166ed10f
# first bad commit: [e28477f214276db941e715eebc8cdfb96c1207d9] GH-117108: Change the size of the GC increment to about 1% of the total heap size. (GH-117120)

First bad commit

e28477f is the first bad commit

commit e28477f214276db941e715eebc8cdfb96c1207d9
Author: Mark Shannon <mark@hotpy.org>
Date:   Fri Mar 22 18:43:25 2024 +0000

    GH-117108: Change the size of the GC increment to about 1% of the total heap size. (GH-117120)

 Include/internal/pycore_gc.h                       |  3 +-
 Lib/test/test_gc.py                                | 35 +++++++++++++++-------
 .../2024-03-21-12-10-11.gh-issue-117108._6jIrB.rst |  3 ++
 Modules/gcmodule.c                                 |  2 +-
 Python/gc.c                                        | 30 +++++++++----------
 Python/gc_free_threading.c                         |  2 +-
 6 files changed, 47 insertions(+), 28 deletions(-)
 create mode 100644 Misc/NEWS.d/next/Core and Builtins/2024-03-21-12-10-11.gh-issue-117108._6jIrB.rst

[picnixz]

cc @markshannon

[pgdr]

Perhaps interestingly, we see the exact same behavior if we use functools.cache and recursion:

from functools import cache
n = 2000

@cache
def d(i, j):
    if i == 0 or j == 0 or i == j:
        return 0
    return (i + j + d(i - 1, j) + d(i, j - 1) + d(i - 1, j - 1)) % ((2**20) - 1)

count = 0
for i in range(n):
    for j in range(n):
        count += (d(i, j) % 2) != 0
print(count)

This probably just shows that cache uses dict to memoize.

[~]$ time pypy3 memo.py

real    0m4,820s
[~]$ time python memo.py

real    0m4,476s
[~]$ time cpython/python memo.py

real    0m16,431s

[sergey-miryanov]

It seems that your example abuses the GC.
If you set gc.set_threshold(2000*2000), for example, you will get a better result.

After some digging, I found the following.

1. The default value for the first GC threshold is 2000.
2. Each innermost cycle creates a few tuples.
3. These tuples are short-living and will be destroyed in either BINARY_OP or STORE_SUBSCR
4. Creating each tuple increments the value of gc.young.count.
5. And this is a problem because gc.young.count grows until it reaches gc.threshold[0] value, at which point the GC will be scheduled
6. At the end of the loop iteration (after JUMP_BACKWARD) the scheduled GC will be run.
7. In your example, you get a lot of GC runs despite the short-lived tuples.

Where is the problem?

In the tuple_dealloc:

cpython/Objects/tupleobject.c

Lines 215 to 218 in 13e9c2d

	// This will abort on the empty singleton (if there is one).
	if (!maybe_freelist_push(op)) {
	Py_TYPE(op)->tp_free((PyObject *)op);
	}

There is a condition that checks the freelist and calls tp_free under certain conditions. tp_free for PyTuple is a PyObject_GC_Del which decrements the value of gc.young.count.

For some reason, the condition is false in our case, so we don't call PyObject_GC_Del and don't decrement gc.young.count.

I don't yet know how to fix this. However, I will investigate further.

[sergey-miryanov]

Ok, I studied a bit further how freelists work.
So tuple_dealloc works as expected.

What is going on:
Runtime has a set of freelists for tuples (for different sizes - from 1 to 10), size of the each freelist for tuples are 2000 elements.

When we create new tuple, we call tuple_alloc and if freelist has available items - we get one and use it.

In our case we create 4 tuples on each iteration. One of them we store as a key in our dict. Other 3 tuples are short-living and tuple_dealloc called for them and they returned to freelist. But we took 4 and return 3. This leads to the situation when after some iteration there are no available items in freelist and we create new one with PyObject_GC_NewVar and incref gc.young.count.

Created tuple then will be returned to the freelist. And after some repetitions of this situation, we get gc.young.count == 2000 and GC will be scheduled and run.

When we run the schedule GC then the incremental version is called. The incremental version has to check local variables/frames and mark live objects and exclude them from the list to process.

So, we run the GC in our cycles may times. Each run will check the local d dict and all keys and values of it. On each run we have to check more and more keys.

This is a problem as I see it. And @pgdr right about bisected commit.

There are two approaches to work around the problem for now - disable the GC before and enable after filling the local dictionary. Or change the value of the first threshold for more appropriate value.

[pgdr]

I can confirm that the following code

import gc
#gc.disable()
n = 2000
d = {}
for i in range(1, n):
    for j in range(1, n):
        d[(i, j)] = i

takes Python 3.14 from 10 seconds to 1.4 seconds by toggling disable.

[pgdr]

Apologies for the noise.

With test.py as:

import sys, gc
if len(sys.argv) == 2 and sys.argv[1].strip().lower() == "disable":
    gc.disable()
n = 2000
d = {}
for i in range(1, n):
    for j in range(1, n):
        d[(i, j)] = i

[...]$ hyperfine "python3.13 test.py" "python3.13 test.py disable" "python3.14 test.py" "python3.14 test.py disable"
Benchmark 1: python3.13 test.py
  Time (mean ± σ):      1.488 s ±  0.061 s    [User: 1.217 s, System: 0.257 s]
  Range (min … max):    1.441 s …  1.643 s    10 runs
 
Benchmark 2: python3.13 test.py disable
  Time (mean ± σ):      1.287 s ±  0.015 s    [User: 1.024 s, System: 0.251 s]
  Range (min … max):    1.270 s …  1.311 s    10 runs
 
Benchmark 3: python3.14 test.py
  Time (mean ± σ):     10.982 s ±  0.033 s    [User: 10.678 s, System: 0.267 s]
  Range (min … max):   10.955 s … 11.064 s    10 runs
 
Benchmark 4: python3.14 test.py disable
  Time (mean ± σ):      1.428 s ±  0.023 s    [User: 1.147 s, System: 0.264 s]
  Range (min … max):    1.409 s …  1.489 s    10 runs
 
Summary
  'python3.13 test.py disable' ran
    1.11 ± 0.02 times faster than 'python3.14 test.py disable'
    1.16 ± 0.05 times faster than 'python3.13 test.py'
    8.53 ± 0.10 times faster than 'python3.14 test.py'

[efimov-mikhail]

It sounds like critical problem with 3.14. IMO, we should fix it ASAP.
cc @nascheme @hugovk