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

81–90 of 90 posts

Re: Your code is fast if you're lucky

#81

Post by chnoblouch »

fsmv wrote: post #76

But it's not exactly a cosmetic change. x++ is semantically different from x; x++; I wonder if clang would make it branchless if you instead write if (BLQS_CMP(x, piv)) { *lwr = x; ++lwr; } else { *rwr = x; --rwr; } The difference is post-increment has strange semantics. While the compiler should be able to understand that the value wasn't used and post increment and pre increment are the same I wouldn't be surprised…

Looking at the optimization pipeline in Compiler Explorer (https://godbolt.org/z/rd3qber3b) after the code is converted to SSA (SROAPass), it seems that the fast version computes the pointer increment (`lwr++`) before storing `x` (`*lwr = x`), whereas the slow version does it the other way around. This happens because Clang chooses a different instruction order when generating a single statement compared to two statements.

The computation is the same, but apparently, this tiny change prevents SimplifyCFGPass from turning the code into the branchless version later on. I'm not sure why this happens, perhaps because it messes something up in the pattern recognition of the pass?

Re: Your code is fast if you're lucky

#82

Post by IshKebab »

adgjlsfhk1 wrote: post #21
IshKebab wrote: post #6

Wow that is quite surprising. Almost seems like it could be a compiler bug tbh. Very fragile optimisation if not!

it's arguably more of a cpu bug than a computer bug. The problem is that predictable data determined whether a cmov or a branch is faster. cmov is only faster than if when the branch is unpredictable. Summer the compiler doesn't know what values your program will be called with, it can only pick and hope. To fix this, cpus could have an instruction like cmov but that learns whether speculation would be profitable and…

There's no reason CPUs can't do prediction and speculative execution on conditional moves just like they do with conditional branches. But with conditional moves the cost of a misprediction is going to be much lower because you don't have to wait for an instruction fetch.

Re: Your code is fast if you're lucky

#83

Post by adrian_b »

14113 wrote: post #61
wiml wrote: post #59

Earlier quoted context omitted.

*foo++ (and --) is an extremely common C idiom. I'd argue it's clearer than the separated version.

As I experienced while trying to write out an AST for this pattern, the operator precedence makes it harder to read. I would at least prefer that it's written as *(foo++).

There are some badly chosen operator priorities in the C programming language that can make expressions without parentheses harder to read (e.g. for the bitwise operators), but the fact that postfix operators are executed before prefix operators is a very simple rule that is hard to forget, so for me adding such superfluous parentheses makes the expression harder to read, not easier to read.

Re: Your code is fast if you're lucky

#84

Post by sylware »

tredre3 wrote: post #69
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?

Yes you can do the same on Windows. https://www.grc.com/inspectre.htm

You have to recompile the kernel to remove some mitigations about "indirect branching", namely you must have alternative windows kernels.

Do you have those windows kernels?

Re: Your code is fast if you're lucky

#85

Post by khuey »

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…

In the one statement case, clang emits LLVM IR where the last operation in each branch is the store. In the two statement case, clang emits LLVM IR where the last operation in each branch is the [pointer math](https://llvm.org/docs/GetElementPtr.html).

The SimplifyCFG pass in LLVM pulls the identical-in-all-but-one-operand store IR instructions into a successor block with a [select instruction](https://llvm.org/docs/LangRef.html#select-instruction) that will ultimately become a conditional move. But the pointer math differs by two operands (because there are two different pointers and one is being decremented and one is being incremented) so SimplifyCFG stops immediately and never reaches the stores.

This sort of brittle behavior where semantically identical code produces different optimization results is common in optimizing compilers unfortunately.

Re: Your code is fast if you're lucky

#86

Post by 14113 »

adrian_b wrote: post #83
14113 wrote: post #61

Earlier quoted context omitted.

As I experienced while trying to write out an AST for this pattern, the operator precedence makes it harder to read. I would at least prefer that it's written as *(foo++).

There are some badly chosen operator priorities in the C programming language that can make expressions without parentheses harder to read (e.g. for the bitwise operators), but the fact that postfix operators are executed before prefix operators is a very simple rule that is hard to forget, so for me adding such superfluous parentheses makes the expression harder to read, not easier to read.

To me, the parentheses make it significantly easier to read. They make it clear which operator directly acts on the variable, and create a mental meta-object to which the next operator acts.

I accept that if you're extremely used to writing this style of C code, it might be something that you're used to, and understand implicitly. As a C++ engineer that infrequently comes across this precise pattern, having the precedence made explicit makes it much easier to understand.

Re: Your code is fast if you're lucky

#87

Post by khuey »

karussell wrote: post #70

Coincidentally a few days ago, also for a sorting algorithm, I stumbled over a situation where replacing the branchless cmov with branching instructions actually made the code 30% faster: https://github.com/graphhopper/graphhopper/pull/3380 Or at least the AI explained it this way to me, but I'm unsure if this is correct.

[dead]

Re: Your code is fast if you're lucky

#88

Post by sylware »

xyzsparetimexyz wrote: post #53
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?

Only really on CPUs with the vulnerability

mitigations do slow all CPUs, even those without the vulns.

You need alternative linux kernels with their modules.

Re: Your code is fast if you're lucky

#89

Post by Validark »

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

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.

Re: Your code is fast if you're lucky

#90

Post by SkiFire13 »

adgjlsfhk1 wrote: post #66
SkiFire13 wrote: post #23

Earlier quoted context omitted.

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.
Post reply on HN