GH-116554: Relax list.sort()'s notion of "descending" runs #116578
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
tim-one
added
DO-NOT-MERGE
interpreter-core
`sortslice_reverse()`. The current
sortslice_advance(&slice, n - neq);
reverse_sortslice(&slice, neq);
pair of lines is an affront to the soul ;-) Putting
the compound name io
<OBJECT TYPE NAME>_<METHOD NAME>
order feels significantly more natural.
with few distinct elements. It's in the nature of the beast that this will catch nearly all plausible "off by 1" coding errors in this context.
Switching to what I guess are some tool's different spelling of GH's single backticks.
|
This looks good to go to me. I wasn't able to provoke any errors in the code, and didn't find any significant timing surprises (compared to the current Reviews always appreciated, but if a few days pass without one, I'll just commit it anyway. |
comments in binarysort(), and deleted a redundant computation. Sue me ;-)
eendebakpt
reviewed
Mar 11, 2024
Misc/NEWS.d/next/Core and Builtins/2024-03-11-00-45-39.gh-issue-116554.gYumG5.rst
Outdated
Show resolved
Hide resolved
AlexWaygood
reviewed
Mar 11, 2024
Co-authored-by: Alex Waygood <Alex.Waygood@Gmail.com>
…e-116554.gYumG5.rst Co-authored-by: Pieter Eendebak <pieter.eendebak@gmail.com>
I kept `lo` mostly to reduce fiddly typing needed for IFLT arguments. But IFLT calls were tedious and error-prone too. So introduced two tiny macros to capture the gibberish needed to spell "is the next element smaller/larger?" once and for all. There was no real use left for `lo` then, so got rid of it. Although a vrbl named `lo` still exists. But with a different meaning. It's a const capturing slo->keys, viewed as an array for `n` to index. A modern optimizing compiler shouldn't need my help to realize that marching through an array one at a time can be strength-reduced to pointer increments (which is what the old `lo` did).
thing we should be oprimizi9ng for ;-) Seriously, they'll return very early anyway, as a matter of course, after the first loop terminates without doing anything, and then the `n == nremaining` test will pass.
vstinner
pushed a commit
to vstinner/cpython
that referenced
this pull request
Mar 20, 2024
…hon#116578) * pythonGH-116554: Relax list.sort()'s notion of "descending" run Rewrote `count_run()` so that sub-runs of equal elements no longer end a descending run. Both ascending and descending runs can have arbitrarily many sub-runs of arbitrarily many equal elements now. This is tricky, because we only use ``<`` comparisons, so checking for equality doesn't come "for free". Surprisingly, it turned out there's a very cheap (one comparison) way to determine whether an ascending run consisted of all-equal elements. That sealed the deal. In addition, after a descending run is reversed in-place, we now go on to see whether it can be extended by an ascending run that just happens to be adjacent. This succeeds in finding at least one additional element to append about half the time, and so appears to more than repay its cost (the savings come from getting to skip a binary search, when a short run is artificially forced to length MIINRUN later, for each new element `count_run()` can add to the initial run). While these have been in the back of my mind for years, a question on StackOverflow pushed it to action: https://stackoverflow.com/questions/78108792/ They were wondering why it took about 4x longer to sort a list like: [999_999, 999_999, ..., 2, 2, 1, 1, 0, 0] than "similar" lists. Of course that runs very much faster after this patch. Co-authored-by: Alex Waygood <Alex.Waygood@Gmail.com> Co-authored-by: Pieter Eendebak <pieter.eendebak@gmail.com>
adorilson
pushed a commit
to adorilson/cpython
that referenced
this pull request
Mar 25, 2024
…hon#116578) * pythonGH-116554: Relax list.sort()'s notion of "descending" run Rewrote `count_run()` so that sub-runs of equal elements no longer end a descending run. Both ascending and descending runs can have arbitrarily many sub-runs of arbitrarily many equal elements now. This is tricky, because we only use ``<`` comparisons, so checking for equality doesn't come "for free". Surprisingly, it turned out there's a very cheap (one comparison) way to determine whether an ascending run consisted of all-equal elements. That sealed the deal. In addition, after a descending run is reversed in-place, we now go on to see whether it can be extended by an ascending run that just happens to be adjacent. This succeeds in finding at least one additional element to append about half the time, and so appears to more than repay its cost (the savings come from getting to skip a binary search, when a short run is artificially forced to length MIINRUN later, for each new element `count_run()` can add to the initial run). While these have been in the back of my mind for years, a question on StackOverflow pushed it to action: https://stackoverflow.com/questions/78108792/ They were wondering why it took about 4x longer to sort a list like: [999_999, 999_999, ..., 2, 2, 1, 1, 0, 0] than "similar" lists. Of course that runs very much faster after this patch. Co-authored-by: Alex Waygood <Alex.Waygood@Gmail.com> Co-authored-by: Pieter Eendebak <pieter.eendebak@gmail.com>
diegorusso
pushed a commit
to diegorusso/cpython
that referenced
this pull request
Apr 17, 2024
…hon#116578) * pythonGH-116554: Relax list.sort()'s notion of "descending" run Rewrote `count_run()` so that sub-runs of equal elements no longer end a descending run. Both ascending and descending runs can have arbitrarily many sub-runs of arbitrarily many equal elements now. This is tricky, because we only use ``<`` comparisons, so checking for equality doesn't come "for free". Surprisingly, it turned out there's a very cheap (one comparison) way to determine whether an ascending run consisted of all-equal elements. That sealed the deal. In addition, after a descending run is reversed in-place, we now go on to see whether it can be extended by an ascending run that just happens to be adjacent. This succeeds in finding at least one additional element to append about half the time, and so appears to more than repay its cost (the savings come from getting to skip a binary search, when a short run is artificially forced to length MIINRUN later, for each new element `count_run()` can add to the initial run). While these have been in the back of my mind for years, a question on StackOverflow pushed it to action: https://stackoverflow.com/questions/78108792/ They were wondering why it took about 4x longer to sort a list like: [999_999, 999_999, ..., 2, 2, 1, 1, 0, 0] than "similar" lists. Of course that runs very much faster after this patch. Co-authored-by: Alex Waygood <Alex.Waygood@Gmail.com> Co-authored-by: Pieter Eendebak <pieter.eendebak@gmail.com>
|
This seems to be resulting in sorting changes between 3.12 and 3.13. Is the sort still Timsort after this? The descending criteria seems to now conflict with https://en.m.wikipedia.org/wiki/Timsort |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
4 participants
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.
Not yet done, but good enough for timing.