[Elliot Gorokhovsky]
Warning: the contents of this message may be dangerous for readers with heart conditions.
It appears some people are offended by your exuberance. Ignore them ;-)
... And it turns out that if you do that, PyFloat_RichCompare becomes ONE LINE (after we set op=Py_LT)!!! Just
Right. And this is why floats will likely be the best case for your approach: all the overheads of finding "the right" bottom-level comparison are weighed against what's basically a single machine instruction to do the actual work of comparing two floats.
return (PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w)) == 0 ? Py_False : Py_True;
In real life, this is better written as: return (PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w)) ? Py_True : Py_False; That is, the comparison to 0 was an artificial complication left over from simplifying the code. However, that code is buggy, in a way that may not show up for a long time. Keeping track of reference counts is crucial. It needs to be more like: PyObject *res: res = (PyFloat_AS_DOUBLE(v) < PyFloat_AS_DOUBLE(w)) ? Py_True : Py_False; Py_INCREF(res); return res;
So I thought, wow, this will give some nice numbers! But I underestimated the power of this optimization. You have no idea. It's crazy.
It's in the ballpark of what I expected :-)
Since we're dealing with floats, I used Tim Peter's benchmark: Lib/test/sortperf.py, just modifying one function:
It's actually Guido's file, although I probably changed it much more recently than he did. As I explained in a different msg, it's _not_ a good benchmark. It's good at distinguishing among "really really good", "not a huge change", and "really really bad", but that's all. At the start, such gross distinctions are all anyone should care about. One thing I'd like to see: do exactly the same, but comment out your float specialization. It's important to see whether sortperf.py says "not a huge change" then (which I expect, but it needs confirmation). That is, it's not enough if some cases get 4x faster if it's also that other cases get much slower.
... #My function: def doit(L): F = FastList(L) f0 = time.perf_counter() F.fastsort() f1 = time.perf_counter() F = FastList(L) t0 = time.perf_counter() F.sort() t1 = time.perf_counter() print("%6.2f%%" % (100*(1-(f1-f0)/(t1-t0))), end=' ') flush()
Numbers in benchmarks always need to be explained, because they're only clear to the person who wrote the code. From your code, you're essentially computing (old_time - new_time) / old_time * 100.0 but in an obfuscated way. So long as the new way is at least as fast, the only possible values are between 0% and 100%. That's important to note. Other people, e.g., measure these things by putting "new_time" in the denominator. Or just compute a ratio, like old_time / new_time. They way you're doing it, e.g., "75%" means the new way took only a quarter of the time of the old way - it means new_time is 75% smaller than old_time. I'm comfortable with that, but it's not the _clearest_ way to display timing differences so dramatic; old_time / new_time would be 4.0 in this case, which is easier to grasp at a glance.
So the benchmarking here is valid.
No, it sucks ;-) But it's perfectly adequate for what I wanted to see from it :-)
I didn't write it. All I did was modify it to print percent improvement instead of sort time. The numbers below are percent improvement of my sort vs default sort (just clone my repo and run python sortperf.py to verify):
i 2**i *sort \sort /sort 3sort +sort %sort ~sort =sort !sort 15 32768 44.11% 54.69% 47.41% 57.61% 50.17% 75.24% 68.03% 65.16% 82.16% 16 65536 14.14% 75.38% 63.44% 56.56% 67.99% 66.19% 50.72% 61.55% 61.87% 17 131072 73.54% 60.52% 60.97% 61.63% 52.55% 49.84% 68.68% 84.12% 65.90% 18 262144 54.19% 55.34% 54.67% 54.13% 55.62% 52.88% 69.30% 74.86% 72.66% 19 524288 55.12% 53.32% 53.77% 54.27% 52.97% 53.53% 67.55% 76.60% 78.56% 20 1048576 55.05% 51.09% 60.05% 50.69% 62.98% 50.20% 66.24% 71.47% 61.40%
If it _didn't_ suck, all the numbers in a column would be about the same :-) A meta-note: when Guido first wrote sortperf.py, machines - and Python! - were much slower. Now sorting 2**15 elements goes so fast that this gross timing approach is especially only good for making the grossest distinctions. On my box today, even the slowest case (*sort on 2**20 elements) takes under half a second. That's "why" the numbers in each column are much more stable across the last 3 rows than across the first 3 rows - the cases in the first 3 rows take so little time that any timing glitch can skew them badly. Note that you can pass arguments to sortperf.py to check any range of power-of-2 values you like, but if you're aware of the pitfalls the output as-is is fine for me.
This is just insane. This is crazy.
Yet nevertheless wholly expected ;-)
... This is so cool.
It is! Congratulations :-)