Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Your code is fast if you're lucky

tiki.li

Post reply on HN
Print view View original

41–50 of 90 posts

Re: Your code is fast if you're lucky

#41

Post by Sardtok »

chrka wrote: post #39
xlii wrote: post #14

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

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…

Look at the source, Luke!

It's just rand() in test.c

Re: Your code is fast if you're lucky

#43

Post by chrka »

sashank_1509 wrote: post #17
xlii wrote: post #14

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

Re: Your code is fast if you're lucky

#44

Post by dyauspitr »

sylware wrote: post #42

Don't forget to disable all "spectre and friends" mitigations in your linux kernel, and some workloads will become much faster. Can you do the same on the windows kernel or apple kernels?

Interesting, did not know you could do that but it does make sense. Make sure it’s air gapped.

Re: Your code is fast if you're lucky

#45

Post by chrka »

Sardtok wrote: post #41
chrka wrote: post #39

Earlier quoted context omitted.

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…

Look at the source, Luke! It's just rand() in test.c

Therefore it is srand(1).

Re: Your code is fast if you're lucky

#46

Post by rokob »

jimaway123 wrote: post #37

Does anyone know exactly what is going on here to cause this difference? I am extremely puzzled that the "beginner friendly" code is not at some point in the compilation pipeline in EXACTLY the same representation as the non-"beginner friendly" code. I would imagine they'd be in the same form very early on, perhaps even at the point of generating an initial syntax tree. And once they take on the same form in the comp…

Have you considered what happens in the presence of multiple threads? I know aarch is weakly memory ordered but the assembly output by those two versions is quite different when multiple threads are involved. There must be a reason spreading the mutations across multiple lines causes the compiler to pessimize to the branch version.

Edit: not saying they are different just that it is harder for the compiler to see the safety of the transform when they are quite different.

Re: Your code is fast if you're lucky

#48

Post by akoboldfrying »

jimaway123 wrote: post #37

Does anyone know exactly what is going on here to cause this difference? I am extremely puzzled that the "beginner friendly" code is not at some point in the compilation pipeline in EXACTLY the same representation as the non-"beginner friendly" code. I would imagine they'd be in the same form very early on, perhaps even at the point of generating an initial syntax tree. And once they take on the same form in the comp…

Complete speculation, but it could be simply that clang only considers applying the branchless optimisation when the code inside the "if" block "looks like" a single instruction/statement -- and this "looks like" check might be done quite early, before "*x++ = y;" and "*x = y; x++;" are converted to the same thing.

Why restrict the optimisation unnecessarily like this? It's never the intention to artificially restrict optimisations, but they are difficult to test and debug as they can interact with other optimisations, and applying an optimisation too broadly leads to horrible correctness bugs. So if you cannot be certain that you understand all possible interactions now and in the future, it makes some sense to be conservative in applying them.

Post reply on HN