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

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

/ cpython Public

gh-131757: allow lru_cache functions to execute concurrently - #131758

Merged
vstinner merged 19 commits into
python:mainfrom
tom-pytel:fix-issue-131757
Apr 14, 2025
ConversationCommits (19)ChecksFiles changed
Merged

gh-131757: allow lru_cache functions to execute concurrently#131758
vstinner merged 19 commits into
python:mainfrom
tom-pytel:fix-issue-131757

Conversation

tom-pytel commented Mar 26, 2025 •
edited
Loading

Copy link
Copy Markdown
Contributor

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.

tom-pytel requested a review from rhettinger as a code owner March 26, 2025 10:54
bedevere-app Bot mentioned this pull request Mar 26, 2025
Closed

vstinner commented Mar 26, 2025

Copy link
Copy Markdown
Member

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

tom-pytel commented Mar 26, 2025

Copy link
Copy Markdown
Contributor Author

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 commented Mar 26, 2025

Copy link
Copy Markdown
Contributor

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 reviewed Mar 26, 2025
View reviewed changes

serhiy-storchaka 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

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

Comment thread Modules/_functoolsmodule.c Outdated

tom-pytel commented Mar 26, 2025

Copy link
Copy Markdown
Contributor Author

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 commented Mar 26, 2025

Copy link
Copy Markdown
Member

And in uncached_lru_cache_wrapper.

tom-pytel commented Mar 26, 2025

Copy link
Copy Markdown
Contributor Author

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 approved these changes Mar 26, 2025
View reviewed changes

serhiy-storchaka 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

LGTM.

Comment thread Modules/_functoolsmodule.c Outdated
colesbury reviewed Mar 26, 2025
View reviewed changes
Comment thread Modules/_functoolsmodule.c
Comment thread Modules/_functoolsmodule.c Outdated

colesbury commented Mar 26, 2025

Copy link
Copy Markdown
Contributor

Also, can you share bench_lrucache.py?

tom-pytel commented Mar 26, 2025

Copy link
Copy Markdown
Contributor Author

Also, can you share bench_lrucache.py?

Its in the header of this PR.

tom-pytel commented Mar 27, 2025

Copy link
Copy Markdown
Contributor Author

@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 reviewed Mar 27, 2025
View reviewed changes

ZeroIntensity 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'm a little late to the party, but this looks pretty good.

Comment thread Modules/_functoolsmodule.c Outdated
Comment thread Modules/_functoolsmodule.c Outdated
Comment thread Modules/_functoolsmodule.c Outdated
Comment thread Modules/_functoolsmodule.c Outdated
Comment thread Modules/_functoolsmodule.c
Comment thread Misc/NEWS.d/next/Library/2025-03-26-10-56-22.gh-issue-131757.pFRdmN.rst Outdated
Comment thread Modules/_functoolsmodule.c Outdated
ZeroIntensity reviewed Mar 27, 2025
View reviewed changes
Comment thread Modules/_functoolsmodule.c Outdated
ZeroIntensity approved these changes Mar 27, 2025
View reviewed changes

ZeroIntensity 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

LGTM as well, thanks for doing this.

mansidhall-CAW mentioned this pull request Mar 28, 2025
Open
colesbury reviewed Mar 28, 2025
View reviewed changes
Comment thread Include/internal/pycore_pyatomic_ft_wrappers.h Outdated
vstinner reviewed Mar 28, 2025
View reviewed changes
Comment thread Include/internal/pycore_pyatomic_ft_wrappers.h Outdated
serhiy-storchaka reviewed Mar 28, 2025
View reviewed changes

serhiy-storchaka 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

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.

vstinner reviewed Apr 14, 2025
View reviewed changes
Comment thread Modules/_functoolsmodule.c Outdated
Comment thread Modules/_functoolsmodule.c Outdated
vstinner approved these changes Apr 14, 2025
View reviewed changes

vstinner 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

LGTM

Comment thread Modules/_functoolsmodule.c Outdated
vstinner merged commit 4c12a2d into python:main Apr 14, 2025

vstinner commented Apr 14, 2025

Copy link
Copy Markdown
Member

Merged, thank you for this new optimization.

tom-pytel mentioned this pull request May 10, 2025
Merged
devdanzin mentioned this pull request Apr 6, 2026
Open
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

colesbury colesbury left review comments
serhiy-storchaka serhiy-storchaka approved these changes
vstinner vstinner approved these changes
ZeroIntensity ZeroIntensity approved these changes
rhettinger Awaiting requested review from rhettinger rhettinger is a code owner

Assignees

No one assigned

Labels

topic-free-threading

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

6 participants

Back | FazBrowse Home | New Git URL