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-112050: Make collections.deque thread-safe in free-threaded builds by mpage · Pull Request #113830 · python/cpython

Conversation

@mpage

@mpage mpage commented Jan 8, 2024 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Contributor

This uses critical sections to make deque methods that operate on mutable state thread-safe when the GIL is disabled. This is mostly accomplished by using the @critical_section clinic directive, though there are a few places where this was not possible and critical sections had to be manually acquired/released.

  • Issue: Make collections.deque thread-safe in --disable-gil builds #112050

Sorry, something went wrong.

Uh oh!

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

itamaro and erlend-aasland reacted with rocket emoji
All reactions
  • 🚀 2 reactions
mpage added 30 commits December 21, 2023 19:49
@mpage
Convert most collections.deque method use clinic
de90440
Convert most methods on collections.deque to use clinic. This will
allow us to use clinic's `@critical_section` directive when making
deques thread-safe for `--gil-disabled`, simplifying the implementation.
@mpage
Make deque.pop thread-safe
010d12c
@mpage
Make deque.popleft thread-safe
32452db
@mpage
Make deque.append thread-safe
a73aa10
@mpage
Make deque.appendleft thread-safe
759d149
@mpage
Make deque.count thread-safe
c0b14ea
@mpage
Make deque.index thread-safe
72bee62
@mpage
Make deque.insert thread-safe
2fd397a
@mpage
Make deque.remove thread-safe
dbe49a0
@mpage
Make deque.rotate thread-safe
5af87e4
@mpage
Make deque.reverse thread-safe
6fcd551
@mpage
Make deque.contains thread-safe
70f07a7
@mpage
Make deque indexing thread-safe
16bbe58
@mpage
Make deque item assignment thread-safe
cbd01c7
@mpage
Make deque.extend thread-safe
92782b1
@mpage
Make deque.extendleft thread-safe
112b6c9
@mpage
Add note about why inplace concat doesn't need a critical section
a4201f1
@mpage
Make deque.clear thread-safe
1e7d0b8
@mpage
Make deque's inplace repeat thread-safe
54975b9
@mpage
Make deque.copy thread-safe
1deb61c
@mpage
Make deque.repeat thread-safe
6b1cb43
@mpage
Make deque concat thread-safe
1957c92
@mpage
Make deque.__reduce__ thread-safe
6141ce5
@mpage
Make deque.len thread-safe
182a034
@mpage
Make deque.__init__ thread-safe
c8fdcec
@mpage
Make deque.__sizeof__ thread-safe
125d253
@mpage
Remove critical section around deque's tp_clear
7cea52d
Clear is used only by the GC; no other threads are running.
@mpage
Make dequeiter ctor thread-safe
f0f86d2
@mpage
Make dequeiter_next thread-safe
02efe9b
@mpage
Make dequiter_len thread-safe
99ffbba
@erlend-aasland

erlend-aasland commented Feb 1, 2024

Copy link
Copy Markdown
Contributor

I'll get some benchmark numbers in a bit.

Great; let's wait with landing this until we've got those.

All reactions

Sorry, something went wrong.

Uh oh!

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

@mpage

mpage commented Feb 2, 2024

Copy link
Copy Markdown
Contributor Author

@erlend-aasland Here are some benchmark numbers using the default -O3. Let me know if you'd like me to run others. The only substantive change in this PR for default builds is to len, where we're now using an atomic load. I would expect that to be slower, though the benchmark numbers don't appear to confirm that assumption. If we're concerned about a slowdown there we could consider using an ifdef to limit the atomic load to only free-threaded builds.

len

I would expect a slowdown due to the use of atomics, but the data doesn't appear to support that.

This PR:

> ./python -m timeit -s "import collections; d = collections.deque(list(range(100)))" "len(d)"
10000000 loops, best of 5: 21.2 nsec per loop

main:

> ./python -m timeit -s "import collections; d = collections.deque(list(range(100)))" "len(d)"
10000000 loops, best of 5: 20.8 nsec per loop
__init__

This should be representative of methods that were annotated with the @critical_section directive. I wouldn't expect any performance change here; the generated acquire/release pair should be a no-op.

This PR:

> ./python -m timeit -s "import collections; L = list(range(100))" "collections.deque(L, 50)"
500000 loops, best of 5: 733 nsec per loop

> ./python -m timeit -s "import collections; L = list(range(100))" "collections.deque(L)"
500000 loops, best of 5: 769 nsec per loop

Main:

> ./python -m timeit -s "import collections; L = list(range(100))" "collections.deque(L, 50)"
500000 loops, best of 5: 731 nsec per loop

> ./python -m timeit -s "import collections; L = list(range(100))" "collections.deque(L)"
500000 loops, best of 5: 746 nsec per loop
contains

This should be representative of methods that had critical sections added manually. In the case of contains, that split the function into two. I wouldn't expect any performance change here in default builds. The compiler should still be able to fully optimize the refactored code.

This PR:

> ./python -m timeit -s "import collections; L = list(range(100))" "50 in L"
500000 loops, best of 5: 512 nsec per loop
> ./python -m timeit -s "import collections; L = list(range(100))" "1 in L"
10000000 loops, best of 5: 29.6 nsec per loop
> ./python -m timeit -s "import collections; L = list(range(100))" "100 in L"
500000 loops, best of 5: 1.02 usec per loop

main:

> ./python -m timeit -s "import collections; L = list(range(100))" "50 in L"
500000 loops, best of 5: 520 nsec per loop
> ./python -m timeit -s "import collections; L = list(range(100))" "1 in L"
10000000 loops, best of 5: 30.2 nsec per loop
> ./python -m timeit -s "import collections; L = list(range(100))" "100 in L"
200000 loops, best of 5: 1 usec per loop
>
erlend-aasland reacted with rocket emoji
All reactions
  • 🚀 1 reaction

Sorry, something went wrong.

Uh oh!

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

corona10
corona10 reviewed Feb 2, 2024
View reviewed changes
Comment thread Modules/_collectionsmodule.c Resolved

Uh oh!

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

@erlend-aasland erlend-aasland assigned corona10 Feb 5, 2024
@mpage
Merge branch 'main' into ft-thread-safe-deque
3c10498
@mpage mpage mentioned this pull request Feb 5, 2024
Atomic operations for only free-threaded builds #115041
Closed
@mpage mpage mentioned this pull request Feb 13, 2024
gh-115041: Add wrappers that are atomic only in free-threaded builds #115046
Merged
@mpage mpage added the topic-free-threading label Feb 13, 2024
mpage added 4 commits February 14, 2024 11:55
@mpage
Merge branch 'main' into ft-thread-safe-deque
1d00d9f
@mpage
Merge branch 'main' into ft-thread-safe-deque
b166202
@mpage
Use free-threaded atomic wrapper for loading deque_iter len
6e64ef4
@mpage
Merge remote-tracking branch 'origin/ft-thread-safe-deque' into ft-th…
6ffad44
…read-safe-deque
@mpage

mpage commented Feb 14, 2024

Copy link
Copy Markdown
Contributor Author

@erlend-aasland - I think everything is addressed now. Would you please have another look?

All reactions

Sorry, something went wrong.

Uh oh!

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

erlend-aasland
erlend-aasland approved these changes Feb 14, 2024
View reviewed changes

@erlend-aasland erlend-aasland left a comment

Copy link
Copy Markdown
Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks!

Sorry, something went wrong.

Uh oh!

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

mpage reacted with heart emoji
All reactions
  • ❤️ 1 reaction
@erlend-aasland

erlend-aasland commented Feb 14, 2024

Copy link
Copy Markdown
Contributor

I'm inclined to run the buildbots on this; Thomas is cooking up the release right now, so we really don't want one of the bots to turn red right now.

colesbury 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.

@erlend-aasland erlend-aasland added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Feb 14, 2024
@bedevere-bot

bedevere-bot commented Feb 14, 2024

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @erlend-aasland for commit 6ffad44 🤖

If you want to schedule another build, you need to add the 🔨 test-with-buildbots label again.

All reactions

Sorry, something went wrong.

Uh oh!

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

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Feb 14, 2024
@mpage
Use free-threaded atomic wrapper in deque_len, too
fa7e8a8
@mpage

mpage commented Feb 14, 2024

Copy link
Copy Markdown
Contributor Author

@erlend-aasland - Just noticed one last place where we want to use the macro wrapper. Would you please kick off another buildbot run. Sorry for the churn.

erlend-aasland 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.

@AlexWaygood

AlexWaygood commented Feb 14, 2024

Copy link
Copy Markdown
Member

@erlend-aasland - Just noticed one last place where we want to use the macro wrapper. Would you please kick off another buildbot run. Sorry for the churn.

You should be able to trigger the buildbot run yourself, now you're a triager! :)

erlend-aasland reacted with rocket emoji
All reactions
  • 🚀 1 reaction

Sorry, something went wrong.

Uh oh!

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

@mpage mpage added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Feb 14, 2024
@bedevere-bot

bedevere-bot commented Feb 14, 2024

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @mpage for commit fa7e8a8 🤖

If you want to schedule another build, you need to add the 🔨 test-with-buildbots label again.

All reactions

Sorry, something went wrong.

Uh oh!

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

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Feb 14, 2024
@mpage

mpage commented Feb 14, 2024

Copy link
Copy Markdown
Contributor Author

You should be able to trigger the buildbot run yourself, now you're a triager! :)

Oho - I'm drunk with power now! :P

erlend-aasland reacted with laugh emoji AlexWaygood reacted with rocket emoji
All reactions
  • 😄 1 reaction
  • 🚀 1 reaction

Sorry, something went wrong.

Uh oh!

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

corona10
corona10 approved these changes Feb 14, 2024
View reviewed changes

@corona10 corona10 left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

Sorry, something went wrong.

Uh oh!

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

All reactions
@erlend-aasland
erlend-aasland merged commit dc978f6 into python:main Feb 15, 2024
@bedevere-app bedevere-app Bot removed the awaiting merge label Feb 15, 2024
@yilei yilei mentioned this pull request Feb 16, 2026
collections.deque is not atomic during copy #144809
Closed
@coderabbitai coderabbitai Bot mentioned this pull request Jul 24, 2026
⚡ Bolt: Optimize ConsciousnessMatrix database writes and deque operations AuraFrameFxDev/A.u.r.a.K.a.i_ReGensis#167
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@colesbury colesbury colesbury left review comments
@corona10 corona10 corona10 approved these changes
@erlend-aasland erlend-aasland erlend-aasland approved these changes
@rhettinger rhettinger Awaiting requested review from rhettinger rhettinger is a code owner

Uh oh!

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

Assignees

@corona10 corona10

Labels

topic-free-threading

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.

7 participants

@mpage @erlend-aasland @vstinner @corona10 @colesbury @bedevere-bot @AlexWaygood
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.