bbhtt commented on issue #1988: URL: https://github.com/apache/buildstream/issues/1988#issuecomment-2624087031
I bisected this when I opened the issue, but looks like I forgot to post the result. Last good version is v3.13.0a5, first bad version is v3.13.0a6 ``` bf121d6a694bea4fe9864a19879fe0c70c4e0656 is the first bad commit commit bf121d6a694bea4fe9864a19879fe0c70c4e0656 Author: Tim Peters <[email protected]> Date: Tue Mar 12 19:59:42 2024 -0500 GH-116554: Relax list.sort()'s notion of "descending" runs (#116578) * GH-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 <[email protected]> Co-authored-by: Pieter Eendebak <[email protected]> Lib/test/test_sort.py | 21 +++ .../2024-03-11-00-45-39.gh-issue-116554.gYumG5.rst | 1 + Objects/listobject.c | 157 ++++++++++++++------- Objects/listsort.txt | 43 ++++-- 4 files changed, 156 insertions(+), 66 deletions(-) create mode 100644 Misc/NEWS.d/next/Core and Builtins/2024-03-11-00-45-39.gh-issue-116554.gYumG5.rst ``` -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
