FYI, I've been poking at this in the background. The ~sort regression is vastly reduced, via removing special-casing and adding more general adaptivity (if you read the timsort.txt file, the special case for run lengths within a factor of 2 of each other went away, replaced by a more intelligent mix of one-pair-at-a-time versus galloping modes). *sort lost about 1% as a result (one-pair-at-a-time is maximally effective for *sort, but in a random mix every now again the "switch to the less efficient (for it) galloping mode" heuristic triggers by blind luck). There's also a significant systematic regression in timsort's +sort case, although it remains faster (and much more general) than samplesort's special-casing of it; also a mix of small regressions and speedups in 3sort. These are because, to simplify experimenting, I threw out the "copy only the shorter run" gimmick, always copying the left run instead. That hurts +sort systematically, as instead of copying just the 10 oddball elements at the end, it copies the very long run of N-10 elements instead (and as many as N-1 temp pointers can be needed, up from N/2). That's all repairable, it's just a PITA to do it. C:\Code\python\PCbuild>python -O sortperf.py 15 20 1 samplesort i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.18 0.01 0.02 0.11 0.01 0.04 0.01 0.11 16 65536 0.24 0.02 0.02 0.25 0.02 0.08 0.02 0.24 17 131072 0.53 0.05 0.04 0.49 0.05 0.18 0.04 0.52 18 262144 1.16 0.09 0.09 1.06 0.12 0.37 0.09 1.14 19 524288 2.53 0.18 0.17 2.30 0.24 0.75 0.17 2.47 20 1048576 5.48 0.37 0.35 5.18 0.45 1.52 0.35 5.35 timsort i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort 15 32768 0.17 0.01 0.02 0.01 0.01 0.05 0.01 0.02 16 65536 0.24 0.02 0.02 0.02 0.02 0.09 0.02 0.04 17 131072 0.54 0.05 0.04 0.05 0.05 0.19 0.04 0.09 18 262144 1.17 0.09 0.09 0.10 0.10 0.38 0.09 0.18 19 524288 2.56 0.18 0.17 0.20 0.20 0.79 0.17 0.36 20 1048576 5.54 0.37 0.35 0.37 0.41 1.62 0.35 0.73 In short, there's no real "speed argument" against this anymore (as I said in the first msg of this thread, the ~sort regression was serious -- it's an important case; turns out galloping is very effective at speeding it too, provided that dumbass premature special-casing doesn't stop galloping from trying <wink>).
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4