Hacker News Reader

Comment by xlii | Hacker News Reader

Is 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.

View on HN

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.

Look at the source, Luke!

It's just rand() in test.c

Therefore it is srand(1).

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!

Both versions use the same input data. I also tried different random initial values and got essentially the same result. I didn't test hundreds of inputs, since that would have been mostly a waste of time in this case. The algorithm and the data distribution remain practically the same. What I'm measuring is the machine code that Clang generates for the hot loop.

The Big-O for sorting algorithms is typically on the number of comparisons. The problem with that is that a comparison takes 1 cycle and you can do 4 per cycle in scalar code or much more in SIMD. Obviously comparisons of doubles are going to be a bit more expensive. Memory reads, on the other hand, take 4 cycles from L1, 10 from L2, and it goes up from there. If you have a predictable memory access pattern, the CPU can preload everything into cache for you, and if you have a deep enough pipeline you can cover up memory reads. Memory access is often completely ignored when analyzing sorting algorithms.

Heapsort has the minimum number of comparisons. Search up "An optimal algorithm for deleting the root of a heap" by Svante Carlsson. Notice how Heapsort is commonly used only as a fallback sort? That's because minimizing comparisons isn't the most important.

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 ran 10k test locally on 2e5 and I'm seeing 4 orders of magnitude instability, but very high local stability (i.e. runs within specific second are very stable, showing almost no deviation, runs couple second later are the same, but results are within 1 OoM of the prior results (smaller batches, 500 tests).

I'm not saying that optimization isn't valid, what I'm saying is that Quicksort shouldn't be optimized over randomized per run data set.

You don't happen to be running `srand(time(0))`?

> I'm not saying that optimization isn't valid, what I'm saying is that Quicksort shouldn't be optimized over randomized per run data set.

But yeah, this is correct. When optimizing, we want to pin every variable other than the change, as much as possible.

Then you run the risk of overfitting to whatever seed you picked. I think fixing a seed is probably a good idea most of the time but it’s worth considering

It's a good rule of thumb that can be quite useful without additional analysis. It's not always the right way to do performance tuning, but I can't count the number of times I've changed an O(n^3) to an O(n) and seen massive performance gains as a result.

Yeah it helps make awful code decent, and some algorithms are better than others, but in terms of high performance code, locality, vectorization, and branching often matter much more big O.

That depends on what end ends. For a small N, very bad algorithms can still be plenty fast. Sometimes it can even be faster. Some of your lower O algorithms can have very terrible constant factors, which means they're terrible when N is small, but as N gets large.

Big and small N different for different algorithms and hardware both.

Totally agree, but I'm in Java land and cursed to have about the worst case scenario for those things :D

Oh yeah I'm also mostly in Java land. These concerns are also concerns in Java, plus whatever C2 gets up to.

Valhalla can't come soon enough.

I've definitely had to change things into SOA in order to eke out performance. My coworkers aren't thrilled seeing `double[] x; double[] y;` but that really is about the only way to get the JVM to play nice.

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 don't need randomized pivoting for this, there are deterministic ones like median of median that will also result in a O(nlogn) worst case.

Also note that with a randomized pivoting you _might_ hit a O(n^2) worst case, it's just that it's incredibly rare and cannot be forced by an attacker controlling your input, so for most practical purposes can be ignored.

median of median does give you guarenteed n*log(n) but it doubles your memory reads per pass making it pretty poor. single random is almost guarenteed to take fewer passes (and median of 3-7 random values can make the number of extra passes over the minimum to be very low)

You don't have to use median of medians for every pass, you can use it only when you detect that each pass is not making enough progress, i.e. when you hit the worst case.

Reply on news.ycombinator.com