gh-154756: Fix data race in list.sort() by weixlu · Pull Request #154572 · python/cpython · GitHub

This PR try to fix #154756, it uses RCU (read-copy-update) method:

copy ob_item to a newly allocated memory address
do the in place sort normally
swap the sorted array back into ob_item at the end.

Testing

The reproducer now runs clean.
PASS ./python -m test test_sort test_list
Benchmark sortperf.py shows no perf regression

Issue: Data race in list.sort() on no-gil build #154756

Could you create a new issue instead of referencing the parent?
Are you sure using a lot of release atomics is the best approach?

Could you create a new issue instead of referencing the parent?

Are you sure using a lot of release atomics is the best approach?

@brijkapadia Thanks for your review. Sure, I’ve created a separate issue.

You’re right that this PR introduces quite a few release atomic stores. However, I think most of them are necessary to preserve the required atomicity.

listobject.c already contains 19 release atomic stores used by methods such as list.clear() and list.extend(), and I believe list.sort() requires similar changes.
That said, 6 atomic stores can be removed. They are in the original ordinary insertion sort implementation, which has been superseded by binary insertion sort and is currently guarded by #if 0. Since this code no longer appears to be used, there is probably no need to update it. I initially added the atomic stores there as well simply to keep the implementations consistent.

What is the performance impact for lists of various size?

What is the performance impact for lists of various size?

@picnixz Hi, I have run sortperf.py on a --disable-gil --enable-optimizations build

For random input, it's 5%-7% slower
For already-ordered / all-equal / worst-case inputs, it has little impact.

Random data (list_sort) across sizes

size	before	after	ratio
16	180 ns	198 ns	1.10x slower
64	944 ns	1.08 us	1.14x slower
256	5.86 us	6.21 us	1.06x slower
1024	52.6 us	55.2 us	1.05x slower
4096	330 us	354 us	1.07x slower
16384(default)	1.70 ms	1.83 ms	1.07x slower
65536	8.81 ms	9.42 ms	1.07x slower
262144	51.8 ms	54.3 ms	1.05x slower

All input patterns at size = 16384 (default)

benchmark	before	after	ratio
list_sort (random)	1.70 ms	1.83 ms	1.08x slower
list_sort_ascending	—	—	not significant
list_sort_ascending_exchanged	—	—	not significant
list_sort_ascending_one_percent	—	—	not significant
list_sort_ascending_random	127 us	123 us	1.03x faster
list_sort_descending	158 us	143 us	1.10x faster
list_sort_duplicates	323 us	343 us	1.06x slower
list_sort_equal	—	—	not significant
list_sort_worst_case	122 us	124 us	1.02x slower

I think we can use a simpler approach, memcpy the ob_item to a newly allocated memory address, then do the in place sort normally, and swap the sorted array back into ob_item at the end.

This keeps the code not too complicated, and should have better performance because we don't need to call atomic operations multiple times. And during the sort process, other threads which may access the old ob_item directly won't see the inner state of the sort.

The list_resize method has the same approach under the free-threaded build:

cpython/Objects/listobject.c

Lines 141 to 171 in a528a24

    
           #ifdef Py_GIL_DISABLED 
        
               _PyListArray *array = list_allocate_array(new_allocated); 
        
               if (array == NULL) { 
        
                   if (newsize < allocated) { 
        
                       // Never fail when shrinking allocations 
        
                       Py_SET_SIZE(self, newsize); 
        
                       return 0; 
        
                   } 
        
                   PyErr_NoMemory(); 
        
                   return -1; 
        
               } 
        
               PyObject **old_items = self->ob_item; 
        
               if (self->ob_item) { 
        
                   if (new_allocated < (size_t)allocated) { 
        
                       target_bytes = new_allocated * sizeof(PyObject*); 
        
                   } 
        
                   else { 
        
                       target_bytes = allocated * sizeof(PyObject*); 
        
                   } 
        
                   memcpy(array->ob_item, self->ob_item, target_bytes); 
        
               } 
        
               if (new_allocated > (size_t)allocated) { 
        
                   memset(array->ob_item + allocated, 0, sizeof(PyObject *) * (new_allocated - allocated)); 
        
               } 
        
                _Py_atomic_store_ptr_release(&self->ob_item, &array->ob_item); 
        
               self->allocated = new_allocated; 
        
               Py_SET_SIZE(self, newsize); 
        
               if (old_items != NULL) { 
        
                   free_list_items(old_items, _PyObject_GC_IS_SHARED(self)); 
        
               } 
        
           #else

I think we can use a simpler approach, memcpy the ob_item to a newly allocated memory address...

Great idea! This sounds like RCU (read-copy-update) in Linux kernel. I'll re-implement it and re-run the benchmarks. I expect the numbers to be much better.

Maybe I misunderstand, and I don't know how important it is now, but copying the entire array seems to go directly against what @tim-one once expressed here:

cpython/Objects/listsort.txt

Lines 17 to 30 in f4b1d3e

    
           + timsort can require a temp array containing as many as N//2 pointers, 
        
             which means as many as 2*N extra bytes on 32-bit boxes.  It can be 
        
             expected to require a temp array this large when sorting random data; on 
        
             data with significant structure, it may get away without using any extra 
        
             heap memory.  This appears to be the strongest argument against it, but 
        
             compared to the size of an object, 2 temp bytes worst-case (also expected- 
        
             case for random data) doesn't scare me much. 
        
             It turns out that Perl is moving to a stable mergesort, and the code for 
        
             that appears always to require a temp array with room for at least N 
        
             pointers. (Note that I wouldn't want to do that even if space weren't an 
        
             issue; I believe its efforts at memory frugality also save timsort 
        
             significant pointer-copying costs, and allow it to have a smaller working 
        
             set.)

There's also this section later:

cpython/Objects/listsort.txt

Line 512 in f4b1d3e

Merge Memory

@pochmann Thanks for pointing this out. When designing a sort algorithm, space complexity really is something you have to think about carefully — it's a trade-off between performance and memory footprint, and this PR is no exception:

using copy-on-write approach does use noticeably more memory, but the benchmarks show little perf regression
using atomic stores avoids the copy but does come at a performance cost.

Personally I'm open to either approach

Two small notes on the current copy-on-write implementation:

The copy is only made when _PyObject_GC_IS_SHARED(self), so the common (non-shared) list.sort() case is unaffected.
I allocate the copy with the list's allocated capacity rather than ob_size, so that when I swap the sorted array back into ob_item,nothing has to change. To save memory it would in principle be possible to copy only ob_size elements.

benchmark result for copy-on-write implementation: Across sizes I see no meaningful regression

size	before	after	ratio
16	179 ns	182 ns	1.01x slower
64	942 ns	937 ns	1.00x faster
256	5.87 us	5.75 us	1.02x faster
1024	52.9 us	52.6 us	1.01x faster
4096	330 us	329 us	1.00x faster
16384(default)	1.70 ms	1.69 ms	1.00x faster
65536	8.82 ms	8.75 ms	1.01x faster
262144	52.2 ms	51.7 ms	1.01x faster

I don't see an RCU-based implementation in the commit history, but that wouldn't be necessary anyway.

The stores in the sorting routines indeed produce undefined behaviour when running concurrently with a lock-free reader, and that needs to be fixed.

There is no necessity for release ordering, though. Relaxed ordering will be sufficient to remove the UB, and should have negligible performance impact.

This reverts commit 8df9f79.

@dpdani Hi, thanks for your reminder, let me upload the RCU-based code.

There is no necessity for release ordering, though. Relaxed ordering will be sufficient to remove the UB, and should have negligible performance impact.

Yes, I also think so :)

TBC, I don't think an RCU implementation is needed here.

bedevere-app Bot added the awaiting review label Jul 24, 2026

bedevere-app Bot mentioned this pull request Jul 24, 2026

Free-threading data races in CPython: 15 findings (9 new + 6 residual of existing FT work) #153852

Open

weixlu force-pushed the list branch from 321cd38 to 645293d Compare July 27, 2026 03:19

weixlu changed the title gh-153852: Fix data race in list.sort() gh-154756: Fix data race in list.sort() Jul 27, 2026

bedevere-app Bot mentioned this pull request Jul 27, 2026

Data race in list.sort() on no-gil build #154756

Open

pythongh-154756 : Fix data race in list.sort()

8df9f79

weixlu force-pushed the list branch from 645293d to 8df9f79 Compare July 27, 2026 03:20

weixlu added 2 commits August 24, 2026 19:35

Revert "pythongh-154756 : Fix data race in list.sort()"

b9ed966

This reverts commit 8df9f79.

pythongh-154756 : Fix data race in list.sort()

5b39f25

gh-154756: Fix data race in list.sort() by weixlu · Pull Request #154572 · python/cpython · GitHub

Uh oh!

Uh oh!

gh-154756: Fix data race in list.sort() - #154572

gh-154756: Fix data race in list.sort()#154572
weixlu wants to merge 3 commits into
python:mainfrom
weixlu:list

weixlu commented Jul 24, 2026 •
edited
Loading

Uh oh!

Uh oh!

brijkapadia commented Jul 24, 2026

Uh oh!

weixlu commented Jul 27, 2026

Uh oh!

picnixz commented Jul 27, 2026

Uh oh!

weixlu commented Jul 28, 2026

Uh oh!

aisk commented Jul 29, 2026

Uh oh!

weixlu commented Jul 30, 2026

Uh oh!

pochmann commented Jul 30, 2026

Uh oh!

weixlu commented Jul 30, 2026

Uh oh!

weixlu commented Jul 30, 2026

Uh oh!

dpdani commented Aug 18, 2026

Uh oh!

weixlu commented Aug 24, 2026

Uh oh!

dpdani commented Aug 24, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

gh-154756: Fix data race in list.sort() by weixlu · Pull Request #154572 · python/cpython · GitHub

Uh oh!

Uh oh!

gh-154756: Fix data race in list.sort() - #154572

gh-154756: Fix data race in list.sort()#154572weixlu wants to merge 3 commits intopython:mainpython/cpython:mainfrom weixlu:listweixlu/cpython:listCopy head branch name to clipboard

Conversation

weixlu commented Jul 24, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

brijkapadia commented Jul 24, 2026

Uh oh!

weixlu commented Jul 27, 2026

Uh oh!

picnixz commented Jul 27, 2026

Uh oh!

weixlu commented Jul 28, 2026

Uh oh!

aisk commented Jul 29, 2026

Uh oh!

weixlu commented Jul 30, 2026

Uh oh!

pochmann commented Jul 30, 2026

Uh oh!

weixlu commented Jul 30, 2026

Uh oh!

weixlu commented Jul 30, 2026

Uh oh!

dpdani commented Aug 18, 2026

Uh oh!

weixlu commented Aug 24, 2026

Uh oh!

dpdani commented Aug 24, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

gh-154756: Fix data race in list.sort()#154572
weixlu wants to merge 3 commits into
python:mainfrom
weixlu:list

weixlu commented Jul 24, 2026 •
edited
Loading