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

71–80 of 90 posts

Re: Your code is fast if you're lucky

#71

Post by misev »

tredre3 wrote: post #67
xyzsparetimexyz wrote: post #58

What if you wrote this in a branchless way? bool v = BLQS_CMP(x, piv); int* ptr = v ? lwr : rwr; *ptr = x; ptr += int(v) * 2 - 1;

The ternary isn't guaranteed to be branchless. In your case it should almost always be on a modern compiler, but it really shouldn't be present in what one would call branchless code.

You could rewrite it to

    int* ptr = ((v != 0) * lwr) + ((v == 0) * rwr);
I doubt it would be faster than the ternary though.

Re: Your code is fast if you're lucky

#73

Post by karussell »

jdw64 wrote: post #2

I really envy programmers who are so skilled at this kind of low-level optimization. The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent... I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level…

First important step is the need to make your application faster.

Second step is to actually make it faster.

And I would say 99% of the time you can make applications faster without going down so deep on this low-level (which is still not easy) but sometimes you can only get faster via low-level optimizations.

Re: Your code is fast if you're lucky

#75

Post by bluGill »

marginalia_nu wrote: post #26
cogman10 wrote: post #24

Earlier quoted context omitted.

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.

Re: Your code is fast if you're lucky

#76

Post by fsmv »

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 if it tracks that it was post increment and misses some optimizations because it's trying to garuntee post increment semantics.

Although it's true compilers can be very sensitive to exact phrasing triggering specific optimization passes. So it still might not give the branchless version by changing it to pre increment (which is the same as a normal +=1).

The only way to really know is to dig into what optimization passes clang took in both cases and analyze the difference.

Re: Your code is fast if you're lucky

#77

Post by jdw64 »

karussell wrote: post #73
jdw64 wrote: post #2

I really envy programmers who are so skilled at this kind of low-level optimization. The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent... I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level…

First important step is the need to make your application faster. Second step is to actually make it faster. And I would say 99% of the time you can make applications faster without going down so deep on this low-level (which is still not easy) but sometimes you can only get faster via low-level optimizations.

thanks!

Re: Your code is fast if you're lucky

#78

Post by xyzsparetimexyz »

tredre3 wrote: post #67
xyzsparetimexyz wrote: post #58

What if you wrote this in a branchless way? bool v = BLQS_CMP(x, piv); int* ptr = v ? lwr : rwr; *ptr = x; ptr += int(v) * 2 - 1;

The ternary isn't guaranteed to be branchless. In your case it should almost always be on a modern compiler, but it really shouldn't be present in what one would call branchless code.

Does any standard library have a glsl-like select(condition, true_val, false_val) that is more or less guaranteed to correspond to a csel?

Re: Your code is fast if you're lucky

#79

Post by wat10000 »

rokob wrote: post #46
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…

The compiler doesn’t have to consider how other threads will see this. If you don’t use atomics, the compiler is free to reorder things however it wishes as long as the single threaded behavior is the same in the end.

Re: Your code is fast if you're lucky

#80

Post by pixelesque »

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…

Note: in some cases (not completely sure if it applies in this situation as I haven't looked into the details of this code enough), using pre-increment AND when the value is used is a dependency on that operation, so "+= 1" is actually faster for out of order execution.

So yeah, as you say, compilers can be very sensitive to this, and in the past (although more than 10 years ago now, so might not be relevant now), ICC often used to generate better (faster executing) code when using "val += 1" vs "++val".

Post reply on HN