Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork32.1k
gh-116738: Make _heapq module thread-safe#135036
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:main
Are you sure you want to change the base?
Conversation
python-cla-botbot commentedJun 2, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
All commit authors signed the Contributor License Agreement. |
StanFromIreland left a comment• edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
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.
There is a lot of duplication in tests because of min/max heaps, why not organize with subtests?
Also for testing the heap, it is probably best to reuse the existing methods fromtest_heapq
cpython/Lib/test/test_heapq.py
Lines 106 to 116 in0558275
| defcheck_invariant(self,heap): | |
| # Check the heap invariant. | |
| forpos,iteminenumerate(heap): | |
| ifpos:# pos 0 has no parent | |
| parentpos= (pos-1)>>1 | |
| self.assertTrue(heap[parentpos]<=item) | |
| defcheck_max_invariant(self,heap): | |
| forpos,iteminenumerate(heap[1:],start=1): | |
| parentpos= (pos-1)>>1 | |
| self.assertGreaterEqual(heap[parentpos],item) |
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.
I think it would also be a good idea to get rid of the borrowed reference usage here.
Uh oh!
There was an error while loading.Please reload this page.
The Modules/_heapqmodule.c change looks good to me. I haven't looked through the tests yet. I don't think should change the implementation to avoid borrowed references: I'd rather keep the change small and limited to the thread safety fix rather than try to "clean" things up, and I'm not really convinced that avoiding borrowed references here would make things better. @yoney - would you please add add a NEWS entry viablurb. You can use |
Ok, but we should definitely do this in a follow-up (possibly only for 3.15). There are definitely some things here that aren't safe. For example: lastelt=PyList_GET_ITEM(heap,n-1) ;Py_INCREF(lastelt);if (PyList_SetSlice(heap,n-1,n,NULL)) {Py_DECREF(lastelt);returnNULL;}n--;if (!n)returnlastelt;returnitem=PyList_GET_ITEM(heap,0); A finalizer could either release the critical section or explicitly clear the list, which could cause that There's also some incredibly horrible things going on, like this: returnitem=PyList_GET_ITEM(heap,0);PyList_SET_ITEM(heap,0,lastelt);
|
@ZeroIntensity I agree that there are things we should follow up on. I initially tried to address some of them as part of the free-threading change, but it introduces complexity to the review and makes the free-threading change harder to review, so I decided to follow up on those issues separately. |
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.
Nitpicks
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Misc/NEWS.d/next/Core_and_Builtins/2025-06-02-13-57-40.gh-issue-116738.ycJsL8.rst OutdatedShow resolvedHide resolved
Uh oh!
There was an error while loading.Please reload this page.
Modules/_heapqmodule.c Outdated
| @@ -128,7 +129,7 @@ Push item onto heap, maintaining the heap invariant. | |||
| staticPyObject* | |||
| _heapq_heappush_impl(PyObject*module,PyObject*heap,PyObject*item) | |||
| /*[clinic end generated code: output=912c094f47663935 input=7c69611f3698aceb]*/ | |||
| /*[clinic end generated code: output=912c094f47663935 input=f7a4f03ef8d52e67]*/ | |||
| { | |||
| if (PyList_Append(heap,item)) | |||
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.
PyList_Append acquires a critical section onheap:
Lines 531 to 543 in1ffe913
| int | |
| PyList_Append(PyObject*op,PyObject*newitem) | |
| { | |
| if (PyList_Check(op)&& (newitem!=NULL)) { | |
| intret; | |
| Py_BEGIN_CRITICAL_SECTION(op); | |
| ret=_PyList_AppendTakeRef((PyListObject*)op,Py_NewRef(newitem)); | |
| Py_END_CRITICAL_SECTION(); | |
| returnret; | |
| } | |
| PyErr_BadInternalCall(); | |
| return-1; | |
| } |
I think this is probably OK from a correctness perspective: if someone sneaks in and modifies the heap betweenPyList_Append releasing the critical section and us reacquiring the lock onheap the call tosiftdown should still execute correctly. However, it's not great for performance. It might be worth inlining the implementation ofPyList_Append here, sans the calls to acquire/release the critical section, to address that.
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.
I think#128126 avoids the problem we used to have where the secondPy_BEGIN_CRITICAL_SECTION() would trigger a release and re-acquisition of the lock.
There's still some extra unnecessary overhead, so using_PyList_AppendTakeRef(), which assumes the caller holds the lock, make sense to me.
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.
@mpage,@colesbury, Thank you for the review, updated to use_PyList_AppendTakeRef()
@StanFromIreland Thank you so much for your review! I've already refactored the code and moved some repeated parts into separate functions while addressing the other comments. I'm not sure if subtests will provide more code reuse here. What do you think? |
| defis_min_heap_property_satisfied(self,heap:list[object])->bool: | ||
| """ | ||
| The value of a parent node should be less than or equal to the | ||
| values of its children. | ||
| """ | ||
| returnself.is_heap_property_satisfied(heap,HeapKind.MIN) | ||
| defis_max_heap_property_satisfied(self,heap:list[object])->bool: | ||
| """ | ||
| The value of a parent node should be greater than or equal to the | ||
| values of its children. | ||
| """ | ||
| returnself.is_heap_property_satisfied(heap,HeapKind.MAX) | ||
| @staticmethod | ||
| defis_heap_property_satisfied( | ||
| heap:list[object],heap_kind:HeapKind | ||
| )->bool: | ||
| """ | ||
| Check if the heap property is satisfied. | ||
| """ | ||
| op=operator.leifheap_kind==HeapKind.MINelseoperator.ge | ||
| # position 0 has no parent | ||
| forposinrange(1,len(heap)): | ||
| parent_pos= (pos-1)>>1 | ||
| ifnotop(heap[parent_pos],heap[pos]): | ||
| returnFalse | ||
| returnTrue | ||
| @staticmethod | ||
| defis_sorted_ascending(lst:list[object])->bool: | ||
| """ | ||
| Check if the list is sorted in ascending order (non-decreasing). | ||
| """ | ||
| returnall(lst[i-1]<=lst[i]foriinrange(1,len(lst))) | ||
| @staticmethod | ||
| defis_sorted_descending(lst:list[object])->bool: | ||
| """ | ||
| Check if the list is sorted in descending order (non-increasing). | ||
| """ | ||
| returnall(lst[i-1]>=lst[i]foriinrange(1,len(lst))) |
StanFromIrelandJun 4, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
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.
| defis_min_heap_property_satisfied(self,heap:list[object])->bool: | |
| """ | |
| Thevalueofaparentnodeshouldbelessthanorequaltothe | |
| valuesofitschildren. | |
| """ | |
| returnself.is_heap_property_satisfied(heap,HeapKind.MIN) | |
| defis_max_heap_property_satisfied(self,heap:list[object])->bool: | |
| """ | |
| Thevalueofaparentnodeshouldbegreaterthanorequaltothe | |
| valuesofitschildren. | |
| """ | |
| returnself.is_heap_property_satisfied(heap,HeapKind.MAX) | |
| @staticmethod | |
| defis_heap_property_satisfied( | |
| heap:list[object],heap_kind:HeapKind | |
| )->bool: | |
| """ | |
| Checkiftheheappropertyissatisfied. | |
| """ | |
| op=operator.leifheap_kind==HeapKind.MINelseoperator.ge | |
| # position 0 has no parent | |
| forposinrange(1,len(heap)): | |
| parent_pos= (pos-1)>>1 | |
| ifnotop(heap[parent_pos],heap[pos]): | |
| returnFalse | |
| returnTrue | |
| @staticmethod | |
| defis_sorted_ascending(lst:list[object])->bool: | |
| """ | |
| Checkifthelistissortedinascendingorder (non-decreasing). | |
| """ | |
| returnall(lst[i-1]<=lst[i]foriinrange(1,len(lst))) | |
| @staticmethod | |
| defis_sorted_descending(lst:list[object])->bool: | |
| """ | |
| Checkifthelistissortedindescendingorder (non-increasing). | |
| """ | |
| returnall(lst[i-1]>=lst[i]foriinrange(1,len(lst))) | |
| defcheck_invariant(self,heap): | |
| # Check the heap invariant. | |
| forpos,iteminenumerate(heap): | |
| ifpos:# pos 0 has no parent | |
| parentpos= (pos-1)>>1 | |
| self.assertTrue(heap[parentpos]<=item) | |
| defcheck_max_invariant(self,heap): | |
| forpos,iteminenumerate(heap[1:],start=1): | |
| parentpos= (pos-1)>>1 | |
| self.assertGreaterEqual(heap[parentpos],item) |
Reuse our existing checks for tests:https://github.com/python/cpython/blob/main/Lib/test/test_heapq.py ?
I don't see a need for the sorted methods too, we can just check the invariant which will simplify this quite a bit? Using the enum for two options also seems over the top, why not just'min'/'max'?
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.
Using the enum for two options also seems over the top, why not just
'min'/'max'
I believe it might be possible to replace all enum usages with strings, and this could be fine in the test. However, I'm not quite sure that removing just 3 lines of enum definition would improve the code. Personally, I would prefer to keep the enum.
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 with two tiny complaints
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
| if (PyList_Append(heap,item)) | ||
| // In a free-threaded build, the heap is locked at this point. | ||
| // Therefore, calling _PyList_AppendTakeRef() is safe and no overhead. | ||
| if (_PyList_AppendTakeRef((PyListObject*)heap,Py_XNewRef(item))) |
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.
Wait, why is this nowXNewRef?item can never beNULL.
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.
I wasn't sure about "item can never beNULL" and in the previous version,PyList_Append() had aNULL check. That's why I thought this would be safe. However,_PyList_AppendTakeRef() expects anon-NULL value foritem so it doesn't really make it safer.
Can I assume that "item can never beNULL" because_heapq_heappush_impl() is called from clinic-generated code?
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.
I think it might be possible foritem to be NULL if you vectorcall this from a C extension? If we want to mirror the previous implementation we should add a check thatitem is notNULL:
if (newitem==NULL) {PyErr_BadInternalCall();returnNULL}
| barrier=Barrier(nthreads) | ||
| defwrapper_func(*args): | ||
| # Wait for all threadss to reach this point before proceeding. |
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.
| # Wait for allthreadss to reach this point before proceeding. | |
| # Wait for allthreads to reach this point before proceeding. |
| if (PyList_Append(heap,item)) | ||
| // In a free-threaded build, the heap is locked at this point. | ||
| // Therefore, calling _PyList_AppendTakeRef() is safe and no overhead. | ||
| if (_PyList_AppendTakeRef((PyListObject*)heap,Py_XNewRef(item))) |
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.
I think it might be possible foritem to be NULL if you vectorcall this from a C extension? If we want to mirror the previous implementation we should add a check thatitem is notNULL:
if (newitem==NULL) {PyErr_BadInternalCall();returnNULL}
| if (PyList_Append(heap,item)) { | ||
| // In a free-threaded build, the heap is locked at this point. | ||
| // Therefore, calling _PyList_AppendTakeRef() is safe and no overhead. | ||
| if (_PyList_AppendTakeRef((PyListObject*)heap,Py_XNewRef(item))) { |
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.
Same comment aboutPy_XNewRef applies here too.
Uh oh!
There was an error while loading.Please reload this page.
This uses critical sections to make heapq methods that update the heap thread-safe when the GIL is disabled. This is accomplished by using the @critical_section clinic directive.
cc:@mpage@colesbury