gh-131757: allow lru_cache functions to execute concurrently by tom-pytel · Pull Request #131758 · python/cpython

tom-pytel · 2025-03-26T10:54:12Z

This PR changes functools.lru_cache to only hold critical sections when it is performing operations on itself and not when it calls the wrapped function being cached.

Example script timing, current code:

$ ./python ../bench_lrucache.py
Time: 31.0s

This PR:

$ ./python ../bench_lrucache.py
Time: 2.4s

Explanation: The script is 16 threads doing a long operation. In the current code they run sequentially because they are serialized by lru_cache. In this PR they are allowed to run concurrently.

Script:

import threading
from functools import lru_cache
from time import time


@lru_cache
def func(v):
    for i in range(100000000):
        pass
    return v

threads = [threading.Thread(target=func, args=(i,)) for i in range(16)]

t0 = time()

for thread in threads:
    thread.start()

for thread in threads:
    thread.join()

print(f'Time: {time() - t0:0.1f}s')

More detail: There are three caching functions that can be used, currently they all execute locked (and by extension the function being cached):

uncached_lru_cache_wrapper - Used when lru_cache(maxsize=0). Just a passthrough call, this doesn't need a lock at all.
infinite_lru_cache_wrapper - Used when lru_cache(maxsize=None). This can just rely on the possible lock when doing dict operations.
bounded_lru_cache_wrapper - Used otherwise. This has been split up into a pre-call function and a post-call function which are both locked individually, with the critical section being released during the actual call to the cached function. This can be done because lru_cache is thread-safe and accomodates for the possibility of the cache dictionary changing during execution of the cached function.

NOTE: This can be reduced to a single critical section if the locked function is only ever called in its owner thread, but not sure is necessary and wanted to keep things simple for this PR.

Issue: functools.lru_cache prevents function being cached from executing concurrently under free-threading #131757

vstinner · 2025-03-26T11:28:53Z

The difference is that func(arg) can now be called with the same arg multiple times in parallel, no?

tom-pytel · 2025-03-26T11:30:21Z

The difference is that func(arg) can now be called with the same arg multiple times in parallel, no?

Yes, and it behaves the same way as before free-threading - it can get into the same function with the same args multiple times if the calls arrive roughly at the same time.

rhettinger · 2025-03-26T16:20:27Z

This PR changes functools.lru_cache to only hold critical sections when it is performing operations on itself and not when it calls the wrapped function being cache

+1 in principle. The C version should be at least as good as the pure python version. In practice, this is tricky to get right.

@colesbury This PR modifies you previous work. Do you want to take a look at it?

@serhiy-storchaka This is mostly your C code. Do you want to look this over?

@tom-pytel I suggest looking at the pure python version in /Lib/functools.py to verify that the C version handles all of the cases listed in the comments. In particular, look at the one that starts with "Getting here means that this same key was added to the cache while the lock was released." The wrapped function can reenter the cache, clear the cache, add to the cache, age out old keys, or be recursive.

serhiy-storchaka

How safe is to execute self->hits++ or self->misses++ without critical section?

Modules/_functoolsmodule.c

tom-pytel · 2025-03-26T17:09:17Z

How safe is to execute self->hits++ or self->misses++ without critical section?

In infinite_lru_cache_wrapper you mean, good catch, can change to atomics.

serhiy-storchaka · 2025-03-26T17:19:14Z

And in uncached_lru_cache_wrapper.

tom-pytel · 2025-03-26T17:42:58Z

And in uncached_lru_cache_wrapper.

Also _functools__lru_cache_wrapper_cache_info_impl and _functools__lru_cache_wrapper_cache_clear_impl as they may be called on the uncached or infinite non-critical wrappers. The atomics in bounded_lru_cache_get_lock_held are unnecessary I just realized so will remove.

serhiy-storchaka

LGTM.

Modules/_functoolsmodule.c

colesbury · 2025-03-26T18:02:59Z

Also, can you share bench_lrucache.py?

tom-pytel · 2025-03-26T18:06:18Z

Also, can you share bench_lrucache.py?

Its in the header of this PR.

tom-pytel · 2025-03-27T10:36:48Z

@tom-pytel I suggest looking at the pure python version in /Lib/functools.py to verify that the C version handles all of the cases listed in the comments.

I double checked all these cases as you suggested and its fine. Which makes sense since all this PR really amounts to is releasing the lock on the call to the function, no other behavior is changed.

ZeroIntensity

I'm a little late to the party, but this looks pretty good.

Modules/_functoolsmodule.c

Misc/NEWS.d/next/Library/2025-03-26-10-56-22.gh-issue-131757.pFRdmN.rst

Modules/_functoolsmodule.c

ZeroIntensity

LGTM as well, thanks for doing this.

Include/internal/pycore_pyatomic_ft_wrappers.h

serhiy-storchaka

Do not overdo this. If is a simple macro to make the code in that file clearer. We do not need a return value. Other similar macros do not use inline functions. If we need that macro in other places, we can update the implementation.

I suggested to implement a simple increment. value++ returns an old value, if this is important.

Modules/_functoolsmodule.c

vstinner

LGTM

Modules/_functoolsmodule.c

vstinner · 2025-04-14T16:31:36Z

Merged, thank you for this new optimization.

pythongh-131757: allow lru_cache functions to execute concurrently

d60c12c

tom-pytel requested a review from rhettinger as a code owner March 26, 2025 10:54

bedevere-app bot added the awaiting review label Mar 26, 2025

bedevere-app bot mentioned this pull request Mar 26, 2025

functools.lru_cache prevents function being cached from executing concurrently under free-threading #131757

Closed

blurb-it bot and others added 3 commits March 26, 2025 10:56

📜🤖 Added by blurb_it.

2dfcea3

fix smelly symbols

c700d1e

fix smelly symbols for real this time

24d4f7a

rhettinger requested review from colesbury and serhiy-storchaka March 26, 2025 16:03

serhiy-storchaka reviewed Mar 26, 2025

View reviewed changes

Modules/_functoolsmodule.c Outdated Show resolved Hide resolved

requested changes

7ead4ee

remove unnecessary atomics

68d14ea

serhiy-storchaka approved these changes Mar 26, 2025

View reviewed changes

Modules/_functoolsmodule.c Outdated Show resolved Hide resolved

bedevere-app bot added awaiting merge and removed awaiting review labels Mar 26, 2025

add FT_ATOMIC_ADD_SSIZE just in this file

028f18b

colesbury reviewed Mar 26, 2025

View reviewed changes

Modules/_functoolsmodule.c Show resolved Hide resolved

Modules/_functoolsmodule.c Outdated Show resolved Hide resolved

_PyDict_GetItemRef_KnownHash_LockHeld()

6c74b26

serhiy-storchaka approved these changes Mar 27, 2025

View reviewed changes

ZeroIntensity reviewed Mar 27, 2025

View reviewed changes

requested changes

2910429

stupid news

1282325

ZeroIntensity reviewed Mar 27, 2025

View reviewed changes

Modules/_functoolsmodule.c Outdated Show resolved Hide resolved

requested changes

34f7fe7

ZeroIntensity approved these changes Mar 27, 2025

View reviewed changes

ZeroIntensity added the topic-free-threading label Mar 27, 2025

mansidhall-CAW mentioned this pull request Mar 28, 2025

Caw/fix issue 131757 knacklabs/cpython#1

Open

FT_ATOMIC_ADD_SSIZE into pyatomic_ft_wrappers.h

60a475d

colesbury reviewed Mar 28, 2025

View reviewed changes

Include/internal/pycore_pyatomic_ft_wrappers.h Outdated Show resolved Hide resolved

vstinner reviewed Mar 28, 2025

View reviewed changes

Include/internal/pycore_pyatomic_ft_wrappers.h Outdated Show resolved Hide resolved

tom-pytel added 3 commits March 28, 2025 12:18

stupid warnings

4200582

return type

aed9b45

FT_ATOMIC_ADD_SSIZE no return value

47e47d5

serhiy-storchaka reviewed Mar 28, 2025

View reviewed changes

tom-pytel added 2 commits April 4, 2025 07:26

Merge branch 'main' into fix-issue-131757

416defe

Merge branch 'main' into fix-issue-131757

2e7bcf4

vstinner reviewed Apr 14, 2025

View reviewed changes

Modules/_functoolsmodule.c Outdated Show resolved Hide resolved

Modules/_functoolsmodule.c Outdated Show resolved Hide resolved

bounded_lru_cache_get_lock_held atomic writes so tsan doesn't complain

11eab6d

vstinner approved these changes Apr 14, 2025

View reviewed changes

Modules/_functoolsmodule.c Outdated Show resolved Hide resolved

fix indentation

5d1bf31

vstinner merged commit 4c12a2d into python:main Apr 14, 2025
42 checks passed

bedevere-app bot removed the awaiting merge label Apr 14, 2025

tom-pytel mentioned this pull request May 10, 2025

gh-132641: fix race in lru_cache under free-threading #133787

Merged

Uh oh!

Conversation

tom-pytel commented Mar 26, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vstinner commented Mar 26, 2025

Uh oh!

tom-pytel commented Mar 26, 2025

Uh oh!

rhettinger commented Mar 26, 2025

Uh oh!

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

tom-pytel commented Mar 26, 2025

Uh oh!

serhiy-storchaka commented Mar 26, 2025

Uh oh!

tom-pytel commented Mar 26, 2025

Uh oh!

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

colesbury commented Mar 26, 2025

Uh oh!

tom-pytel commented Mar 26, 2025

Uh oh!

tom-pytel commented Mar 27, 2025

Uh oh!

ZeroIntensity left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

ZeroIntensity left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

serhiy-storchaka left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

vstinner left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

vstinner commented Apr 14, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

tom-pytel commented Mar 26, 2025 •

edited

Loading