Tim Peters <t...@python.org> added the comment:
Yup, it can do some redundant comparisons; more on that here: https://mail.python.org/pipermail/python-dev/2018-August/155020.html I'm not inclined to make this already-difficult code even harder to understand for something that's quite likely not to matter - or even hurt. For example, if we're sorting a million randomly ordered objects, we can expect about 20 million comparisons. 9,800 is so close to zero compared to that it wouldn't be a measurable difference even if the new code came for free - which it doesn't. It adds whole new piles of tests/branches, which will almost certainly be mis-predicted on the first iteration of the outer loop because they always fail the "initial" part on iterations after the first. At best, they're cheap but pure do-nothing overhead on outer-loop iterations after the first. I also dislike that binarysort grows a pile of undocumented assumptions about the _context_ it's called in. As is, it can be used to sort any slice meeting the requirements spelled out in the comments. "Leaking" requirements across function boundaries is fragile. Note that this part: else IFLT(pivot, *p) { r = p; } else { l = p + 1; } doesn't work at all the way it "looks like" it works. It expands to: else if ((k = ISLT(pivot, *p)) < 0) goto fail; if (k) { r = p: } else { l = p + 1; } The r = p; and l = p + 1; lines you added above in your new code are useless, because this final "if (k)" block executes regardless of whether `initial` is true or false. Indeed, if you hadn't _also_ added new code to set `k` to 0 or 1, the code would be wrong. But that's impossible to see without expanding the macro. So if you pursue this, at least rewrite that block as: else { IFLT(pivot, *p) { r = p; else { l = p + 1; } } and remove the new "k = 1;" and "k = 0;" mystery lines. But unless there are real-world cases that show significant speedups, I'm - as I said in the message I linked to above - happy with the tradeoffs already in place. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue35369> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
