gh-120608: Make reversed thread-safe by eendebakpt · Pull Request #120609 · python/cpython

eendebakpt · 2024-06-16T22:28:37Z

The reversed builtin is not thread-safe. In reversed_next the object index can be read and decremented by multiple threads leading to incorrect results. The part that needs to happen atomically is the check (index >= 0) and the decrement ro->index--;.

A reproducing example will be included in the tests later.

Issue reversed is not thread-safe #120608
We could perhaps make the code more efficient (no locks required), by using a _Py_atomic_compare_exchange on the ro->index (exchanging with ro->index--). This would make the code more complex and I am not sure lock contention is a performance issue here.
The macro Py_EXIT_CRITICAL_SECTION is the same as proposed in gh-120496: Make enum_iter thread safe #120591

Issue: reversed is not thread-safe #120608

Misc/NEWS.d/next/Core and Builtins/2024-06-16-22-42-47.gh-issue-120608._-YtWX.rst

sobolevn · 2024-06-17T07:16:55Z

Include/internal/pycore_critical_section.h

 # define Py_END_CRITICAL_SECTION()                                      \
        _PyCriticalSection_End(&_cs);                                   \
    }
+# define Py_EXIT_CRITICAL_SECTION()                                     \


Maybe it is better to define a local API instead of a global one? For example END_TYPE_LOCK() does that.

You can just extract the critical section into a helper function and then wrap the helper with the existing macros.

For this PR, I'd just extract most of reversed_next into a reversed_next_impl and wrap that with the Py_{BEGIN,END}_CRITICAL_SECTION macros. See also #120318.

FWIW we ended up not doing that in #120318. There's this comment though that explains the approach and gives an example.

Thanks for the feedback everyone! I added the Py_EXIT_CRITICAL_SECTION in this PR (and some others) to deal with return and goto statements. I am not in favor of adding a local API, since it will leak details of the locking implementation to modules. Changing the Py_EXIT_CRITICAL_SECTION to a more private _Py_EXIT_CRITICAL_SECTION (or something like that) would be fine with me.

In this case we can indeed refactor to create a reversed_next_impl and put a global lock around it. I am not too worried about performance here, and if it turns out performance is an issue we can change later.

Unless more suggestions come it, I will refactor to reversed_next_impl in the coming days.

…e-120608._-YtWX.rst Co-authored-by: Nikita Sobolev <[email protected]>

corona10 · 2024-06-18T12:40:53Z

Do you have a benchmark for the single thread case?
And PTAL the comment: #120496 (comment)

corona10 · 2024-06-18T12:46:11Z

Objects/enumobject.c

    if (index >= 0) {
        item = PySequence_GetItem(ro->seq, index);
        if (item != NULL) {
            ro->index--;


We don't declare the critical section for the list_next

cpython/Objects/listobject.c

Lines 3890 to 3911 in dacc5ac

listiter_next(PyObject *self)

{

_PyListIterObject *it = (_PyListIterObject *)self;

Py_ssize_t index = FT_ATOMIC_LOAD_SSIZE_RELAXED(it->it_index);

if (index < 0) {

return NULL;

}

PyObject *item = list_get_item_ref(it->it_seq, index);

if (item == NULL) {

// out-of-bounds

FT_ATOMIC_STORE_SSIZE_RELAXED(it->it_index, -1);

#ifndef Py_GIL_DISABLED

PyListObject *seq = it->it_seq;

it->it_seq = NULL;

Py_DECREF(seq);

#endif

return NULL;

}

FT_ATOMIC_STORE_SSIZE_RELAXED(it->it_index, index + 1);

return item;

}

Why do we have to declare the critical section here?
And what about just handling as the out-of-bound,
and if the ro->index needs to be decremented, why not just use atomic operation in here?

cc @colesbury

The check index >= 0 and decrement ro->index-- need to happen atomically. We could use the atomic _Py_atomic_compare_exchange for this, but it would increase code complexity. If performance is a concern, I can update the PR with this approach. The PySequence_GetItem is not inside the critical section, but I assumed it to be (or to be made later) thread safe

eendebakpt · 2024-06-23T20:25:47Z

@corona10 Here is a benchmark for the PR using a critical section. Based on comments on the issue #120496 I believe that using atomics might be a better option, I will look into that a bit later.

Benchmark script:

import pyperf
runner = pyperf.Runner()

setup = """

from collections import UserList

range10 = range(10)
range1000 = range(1000)
x = list(range(100))
t = tuple(range(100))

userlist100 = UserList(x)

"""

runner.timeit(name="reversed(range10)", stmt="reversed(range10)", setup=setup)
runner.timeit(name="list(reversed(range10))", stmt="list(reversed(range10))", setup=setup)
runner.timeit(name="list(reversed(range1000))", stmt="list(reversed(range1000))", setup=setup)
runner.timeit(name="list(reversed(list100))", stmt="list(reversed(x))", setup=setup)
runner.timeit(name="list(reversed(tuple100))", stmt="list(reversed(t))", setup=setup)
runner.timeit(name="list(reversed(userlist100))", stmt="list(reversed(userlist100))", setup=setup)

Result

list(reversed(range10)): Mean +- std dev: [ft2] 428 ns +- 55 ns -> [ft_pr] 413 ns +- 14 ns: 1.04x faster
list(reversed(list100)): Mean +- std dev: [ft2] 846 ns +- 25 ns -> [ft_pr] 833 ns +- 7 ns: 1.02x faster
list(reversed(tuple100)): Mean +- std dev: [ft2] 1.01 us +- 0.08 us -> [ft_pr] 2.23 us +- 0.02 us: 2.21x slower
list(reversed(userlist100)): Mean +- std dev: [ft2] 34.0 us +- 1.7 us -> [ft_pr] 33.4 us +- 1.8 us: 1.02x faster

Benchmark hidden because not significant (2): reversed(range10), list(reversed(range1000))

Geometric mean: 1.13x slower

The performance for range and list is not affected. This makes sense as these methods have a custom __reversed__ method. For a user-defined iterable supporting the sequence protocol (the UserList) the performance impact is very small.
The main performance degradation is for tuple. Maybe this can be resolved by using a custom __reversed__, just as for list.

eendebakpt · 2024-06-24T20:11:22Z

@corona10 I created #120971 to make reversed thread-safe using atomics. I will close this one.

eendebakpt added 2 commits June 17, 2024 00:23

Make reversed thread-safe

f5d81ba

Add Py_EXIT_CRITICAL_SECTION

40018a1

eendebakpt requested a review from ethanfurman as a code owner June 16, 2024 22:28

bedevere-app bot added the awaiting review label Jun 16, 2024

eendebakpt changed the title ~~gh-20608: Make reversed thread-safe~~ gh-120608: Make reversed thread-safe Jun 16, 2024

bedevere-app bot mentioned this pull request Jun 16, 2024

reversed is not thread-safe #120608

Closed

📜🤖 Added by blurb_it.

726f6ca

sobolevn reviewed Jun 17, 2024

View reviewed changes

Update Misc/NEWS.d/next/Core and Builtins/2024-06-16-22-42-47.gh-issu…

8c82d5e

…e-120608._-YtWX.rst Co-authored-by: Nikita Sobolev <[email protected]>

corona10 reviewed Jun 18, 2024

View reviewed changes

eendebakpt closed this Jun 24, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Comments

gh-120608: Make reversed thread-safe#120609

gh-120608: Make reversed thread-safe#120609
eendebakpt wants to merge 4 commits intopython:mainfrom
eendebakpt:reverse_ft

eendebakpt commented Jun 16, 2024 •

edited

Loading

Uh oh!

Uh oh!

sobolevn Jun 17, 2024

Uh oh!

erlend-aasland Jun 17, 2024

Uh oh!

erlend-aasland Jun 17, 2024 •

edited

Loading

Uh oh!

lysnikolaou Jun 17, 2024

Uh oh!

eendebakpt Jun 17, 2024

Uh oh!

corona10 commented Jun 18, 2024

Uh oh!

corona10 Jun 18, 2024

Uh oh!

eendebakpt Jun 18, 2024

Uh oh!

eendebakpt commented Jun 23, 2024 •

edited

Loading

Uh oh!

eendebakpt commented Jun 24, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

	listiter_next(PyObject *self)
	{
	_PyListIterObject it = (_PyListIterObject )self;
	Py_ssize_t index = FT_ATOMIC_LOAD_SSIZE_RELAXED(it->it_index);
	if (index < 0) {
	return NULL;
	}

	PyObject *item = list_get_item_ref(it->it_seq, index);
	if (item == NULL) {
	// out-of-bounds
	FT_ATOMIC_STORE_SSIZE_RELAXED(it->it_index, -1);
	#ifndef Py_GIL_DISABLED
	PyListObject *seq = it->it_seq;
	it->it_seq = NULL;
	Py_DECREF(seq);
	#endif
	return NULL;
	}
	FT_ATOMIC_STORE_SSIZE_RELAXED(it->it_index, index + 1);
	return item;
	}

Uh oh!

Comments

Conversation

eendebakpt commented Jun 16, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

sobolevn Jun 17, 2024

Choose a reason for hiding this comment

Uh oh!

erlend-aasland Jun 17, 2024

Choose a reason for hiding this comment

Uh oh!

erlend-aasland Jun 17, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lysnikolaou Jun 17, 2024

Choose a reason for hiding this comment

Uh oh!

eendebakpt Jun 17, 2024

Choose a reason for hiding this comment

Uh oh!

corona10 commented Jun 18, 2024

Uh oh!

corona10 Jun 18, 2024

Choose a reason for hiding this comment

Uh oh!

eendebakpt Jun 18, 2024

Choose a reason for hiding this comment

Uh oh!

eendebakpt commented Jun 23, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

eendebakpt commented Jun 24, 2024

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

eendebakpt commented Jun 16, 2024 •

edited

Loading

erlend-aasland Jun 17, 2024 •

edited

Loading

eendebakpt commented Jun 23, 2024 •

edited

Loading