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-115999: Make list and tuple iteration more thread-safe. by Yhg1s · Pull Request #128637 · python/cpython

Conversation

@Yhg1s

@Yhg1s Yhg1s commented Jan 8, 2025 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Member

Make tuple iteration more thread-safe, and actually test concurrent iteration of tuple, range and list. (This is prep work for enabling specialization of FOR_ITER in free-threaded builds.) The basic premise is:

  • Iterating over a shared iterable (list, tuple or range) should be safe, not involve data races, and behave like iteration normally does.

  • Using a shared iterator should not crash or involve data races, and should only produce items regular iteration would produce. It is not guaranteed to produce all items, or produce each item only once. (This is not the case for range iteration even after this PR.)

Providing stronger guarantees is possible for some of these iterators, but it's not always straight-forward and can significantly hamper the common case. Since iterators in general aren't shared between threads, and it's simply impossible to concurrently use many iterators (like generators), better to make sharing iterators without explicit synchronization clearly wrong.

Specific issues fixed in order to make the tests pass:

  • List iteration could occasionally fail an assertion when a shared list was shrunk and an item past the new end was retrieved concurrently. There's still some unsafety when deleting/inserting multiple items through for example slice assignment, which uses memmove/memcpy.

  • Tuple iteration could occasionally crash when the iterator's reference to the tuple was cleared on exhaustion. Like with list iteration, in free-threaded builds we can't safely and efficiently clear the iterator's reference to the iterable (doing it safely would mean extra, slow refcount operations), so just keep the iterable reference around.

  • Issue: Make the specializing interpreter thread-safe in --disable-gil builds #115999

Sorry, something went wrong.

Uh oh!

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

eendebakpt reacted with eyes emoji
All reactions
  • 👀 1 reaction
@Yhg1s
Make list, tuple and range iteration more thread-safe, and actually test
1533d1d
concurrent iteration. (This is prep work for enabling specialization of
FOR_ITER in free-threaded builds.) The basic premise is:

 - Iterating over a shared _iterable_ (list, tuple or range) should be safe,
   not involve data races, and behave like iteration normally does.

 - Using a shared _iterator_ should not crash or involve data races, and
   should only produce items regular iteration would produce. It is _not_
   guaranteed to produce all items, or produce each item only once.

Providing stronger guarantees is possible for some of these iterators, but
it's not always straight-forward and can significantly hamper the common
case. Since iterators in general aren't shared between threads, and it's
simply impossible to concurrently use many iterators (like generators),
better to make sharing iterators without explicit synchronization clearly
wrong.

Specific issues fixed in order to make the tests pass:

 - List iteration could occasionally crash when a shared list wasn't already
   marked as shared when reallocated.

 - Tuple iteration could occasionally crash when the iterator's reference to
   the tuple was cleared on exhaustion. Like with list iteration, in
   free-threaded builds we can't safely and efficiently clear the iterator's
   reference to the iterable (doing it safely would mean extra, slow
   refcount operations), so just keep the iterable reference around.

 - Fast range iterators (for integers that fit in C longs) shared between
   threads would sometimes produce values past the end of the range, because
   the iterators use two bits of state that we can't efficiently update
   atomically. Rewriting the iterators to have a single bit of state is
   possible, but probably means more math for each iteration and may not be
   worth it.

 - Long range iterators (for other numbers) shared between threads would
   crash catastrophically in a variety of ways. This now uses a critical
   section. Rewriting this to be more efficient is probably possible, but
   since it deals with arbitrary Python objects it's difficult to get right.

There seem to be no more exising races in list_get_item_ref, so drop it from
the tsan suppression list.
@Yhg1s
Yhg1s requested review from colesbury and mpage January 8, 2025 14:56
@Yhg1s
Yhg1s marked this pull request as ready for review January 8, 2025 14:56
@bedevere-app bedevere-app Bot mentioned this pull request Jan 8, 2025
Make the specializing interpreter thread-safe in --disable-gil builds #115999
Closed
@bedevere-app bedevere-app Bot added the awaiting core review label Jan 8, 2025
@Yhg1s
Fix lint issues.
a069f9b
@Yhg1s Yhg1s added the skip news label Jan 8, 2025
corona10
corona10 reviewed Jan 8, 2025
View reviewed changes
Comment thread Objects/rangeobject.c Resolved

Uh oh!

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

Yhg1s added 4 commits January 9, 2025 16:10
@Yhg1s
Restore the original guard for list_get_item_ref's fast path, since it's
661dc7b
actually correct and the real problem was an incorrect assert. The fast path
still contains notionally unsafe uses of memcpy/memmove, so add
list_get_item_ref back to the TSan suppressions file.
@Yhg1s
Merge branch 'main' into list-realloc
7263d1e
@Yhg1s
Fix test failures in test_sys because of the changed size of range
484c6b2
iterators, and fix build failures because labels can't technically be at the
end of compound statements (a statement must follow the label, even if it's
empty).
@Yhg1s
Merge branch 'list-realloc' of github.com:Yhg1s/cpython into list-rea…
89c4629
…lloc
mpage
mpage reviewed Jan 9, 2025
View reviewed changes
Comment thread Lib/test/test_free_threading/test_iteration.py Resolved

Uh oh!

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

colesbury
colesbury reviewed Jan 9, 2025
View reviewed changes
Comment thread Objects/listobject.c Resolved

Uh oh!

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

colesbury
colesbury reviewed Jan 9, 2025
View reviewed changes
Comment thread Objects/rangeobject.c Resolved

Uh oh!

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

Comment thread Objects/rangeobject.c Resolved

Uh oh!

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

Yhg1s added 3 commits January 10, 2025 13:47
@Yhg1s
Fix tupleiter_reduce for test_iter's assumptions, and make tupleiter_…
daacf82
…len and

tupleiter_setstate appropriately relaxed.
@Yhg1s
Undo the range iterator changes (leave them for later), adjust the range
94ab0c6
iterator test to accept the current behaviour of the fast range iterator and
avoid testing the (very unsafe) long range iterator, use threading.Barrier
where appropriate, and add comments to the unsafe uses of memcpy/memmove in
free-threaded builds.
@Yhg1s
Remove edit snafu.
c6b9200
@Yhg1s Yhg1s changed the title gh-115999: Make list, tuple and range iteration more thread-safe. gh-115999: Make list and tuple iteration more thread-safe. Jan 12, 2025
@Yhg1s
Merge branch 'main' into list-realloc
ed7e8c7
@Yhg1s

Yhg1s commented Jan 12, 2025

Copy link
Copy Markdown
Member Author

PTAL.

All reactions

Sorry, something went wrong.

Uh oh!

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

@Yhg1s Yhg1s mentioned this pull request Jan 13, 2025
gh-115999: Add free-threaded specialization for FOR_ITER #128798
Merged
eendebakpt
eendebakpt reviewed Jan 16, 2025
View reviewed changes
Comment thread Objects/tupleobject.c Resolved

Uh oh!

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

Comment thread Objects/tupleobject.c Resolved

Uh oh!

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

@Yhg1s Yhg1s mentioned this pull request Jan 20, 2025
Race in concurrent iteration over range iterators #129068
Closed
Yhg1s added 3 commits January 20, 2025 15:03
@Yhg1s
Extend tests a little, add suppressions with links to GH issues.
dd56d89
@Yhg1s
Address reviewer comments.
4028dfe
@Yhg1s
Turn the last few stores/loads of list iterator/reversed iterator into
ef5ca7c
relaxed atomics. (These are not performance-sensitive parts of the code, and
this lets us detect races elsewhere involving the iterators.)
@Yhg1s
Yhg1s force-pushed the list-realloc branch from 31efc4f to ef5ca7c Compare January 21, 2025 14:55
@Yhg1s
Merge branch 'main' into list-realloc
e1dd5f8
@eendebakpt eendebakpt mentioned this pull request Jan 21, 2025
list iterator __setstate__() differs for exhausted iterator GIL vs. non-GIL #129139
Open
@mpage
mpage requested review from colesbury and mpage January 23, 2025 19:40
mpage
mpage reviewed Jan 23, 2025
View reviewed changes
Comment thread Lib/test/test_free_threading/test_iteration.py Resolved

Uh oh!

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

Yhg1s added 2 commits January 26, 2025 22:40
@Yhg1s
Address reviewer comments.
f689a8a
@Yhg1s
Merge branch 'list-realloc' of github.com:Yhg1s/cpython into list-rea…
2923f6a
…lloc
@eendebakpt eendebakpt mentioned this pull request Jan 28, 2025
gh-123471: make itertools.batched thread-safe #129416
Merged
@corona10 corona10 mentioned this pull request Feb 18, 2025
gh-130263: fix list iterators to use atomics for storing index #130266
Closed
@Yhg1s
Merge branch 'main' into list-realloc
08f0647
@Yhg1s

Yhg1s commented Feb 19, 2025

Copy link
Copy Markdown
Member Author

@colesbury Do you still want to look at this?

All reactions

Sorry, something went wrong.

Uh oh!

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

colesbury
colesbury approved these changes Feb 19, 2025
View reviewed changes

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

LGTM

Sorry, something went wrong.

Uh oh!

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

All reactions
@bedevere-app bedevere-app Bot added awaiting merge and removed awaiting core review labels Feb 19, 2025
@Yhg1s
Yhg1s merged commit 388e1ca into python:main Feb 19, 2025
@bedevere-app bedevere-app Bot removed the awaiting merge label Feb 19, 2025
@Yhg1s
Yhg1s deleted the list-realloc branch February 19, 2025 00:52
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@mpage mpage mpage left review comments
@eendebakpt eendebakpt eendebakpt left review comments
@corona10 corona10 corona10 left review comments
@colesbury colesbury colesbury approved these changes

Uh oh!

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

Assignees

No one assigned

Labels

skip news

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.

5 participants

@Yhg1s @mpage @colesbury @eendebakpt @corona10
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.