alt Hacker NewsIs it only me..?
Quicksort is supposed to be an algorithm that has O(n) to O(n²) performance and O(n log n) being only an average performance case. Test was made on random data coming from different archs (so I doubt it's characteristic would be remotely identical).
Given input size of 50M it means that performance could be between 50M (5e7) up to 2.5e15. That's like performance instability of 8 orders of magnitude.
I'm not sure here if we can't write instead that "Your code is fast if you picked fast case for it" especially since fix of 6 OOM is smaller than algorithm's performance range.
Replies
I’m assuming he measured time by averaging on 100s of instances, or he maintained the exact same input for both versions of code. Would be a big oversight if not!
Looking at big-O isn't very informative. We have plenty of statistical tools for telling whether there is an effect even with noisy data.
I hope the test data is the same when comparing the different runs. So the big o notation should be the same across different runs.
if you have decent (randomized) pivoting, you never hit the worst case or anything like it
You're talking about the complexity of the Quicksort algorithm, whereas the article is about code generation.
Both versions sort the same data using the same algorithm. Just a tiny change in the source code caused Clang to generate different machine code.
Using different seed values - (srand(1), srand(2), srand(time(NULL))) essentially leads to the same result. With a good choice of pivot, Quicksort is very close to O(n log n) in practice, so that’s not the key factor here.
The interesting thing is that the generated machine code changes significantly.