8 ms·

Is This a Branch?

136 points by wheresvic4 6y ago

bombcar 6y ago
Another good example why premature optimization is usually counterproductive. I really like the use of the assembly comparisons to check and prove assumptions.
- mhh__ 6y ago
  The disassembly can lie, however, i.e. the CPU can do a lot of work in the time a cache miss takes (or some other dependency induced stall, or misprediction) - you have to measure it, in the situation where the code is actually being used (i.e. contrived benchmarks will again often lie as they usually don't fill the cache, and are easy to predict)
  - guerrilla 6y ago
    Yeah, I was actually wondering if maybe gcc did that second one with floats on purpose because of profiling data that they have.
lmm 6y ago
Ifs are generally bad for readability though, because they force the reader to understand your control flow. Replacing an if with a ternary makes it more readable, not because the generated code is any different, but because a reader immediately knows that they don't need to scan through the two sides for control flow constructs (because the two sides of the ternary are guaranteed to be expressions rather than blocks). An if might occasionally be clearer than some convoluted algebra, but not often.
- cortesoft 6y ago
  Some languages allow blocks in a ternary... ruby, for example
- caturopath 6y ago
  Do you know if there's any evidence that ternaries beat ifs for people understanding code in practice or in people's self-assessments? Would not have been my guess at all.
  - ZephyrBlu 6y ago
    An anecdotal data point: I prefer ternaries unless the if statement is for control flow. They're terser and don't stick out as much in the code.
  - memco 6y ago
    If Hillel Wayne’s talk on empirical software design is any good measure then either method is fine[0] so long as you and the team you work with can agree about it’s utility in code review. If it’s just you on the project then do whatever is most comfortable. [0] https://m.youtube.com/watch?v=WELBnE33dpY https://m.youtube.com/watch?v=WELBnE33dpY
- nopeYouAreWrong 6y ago
  I have been reading HN for a long time but your comment is the first time I violently felt the need to create an account and respond. I want you to consider how significant that is. Ternaries are NEVER easier to read.
  - xvedejas 6y ago
    Maybe ternaries aren't easier to read, but they make the surrounding code easier to read because they duck out of the way? Devoting several lines to what is a very quick if/else expression could be distracting I suppose. Playing devil's advocate.
    - Buttons840 6y ago
      It's important to note that ternaries are expressions, they evaluate to a value. When I see a ternary I know that a boolean is being mapped to a value. This is true both technically and almost always in practice. If-statements are the wild west. Who knows what an if statement will do? An if-statement may be as simple as a ternary, or it might be a branch point and the resulting logic streams will never meet again.
      - microtherion 6y ago
        We're talking C. As soon as a ternary calls a function, all bets are off what could be happening in addition to the value being computed. And thanks to the preprocessor, any identifier could potentially be calling a function.
        boulos 6y ago
        Hmm? Which part implies “all bets are off”? There’s the condition (evaluated first), the true case and the false case. Only one of the cases is evaluated. I’m assuming you were alluding to some sort of “x++ = x++ * *x++” style situation, but the ternary expression isn’t a statement and there are sequence points in between. As a bonus, the first result for “ternary operator evaluation order” gave me someone who linked to the standard [1]. Quoting from the standard that they quoted: > The first operand is evaluated; there is a sequence point between its evaluation and the evaluation of the second or third operand (whichever is evaluated). The second operand is evaluated only if the first compares unequal to 0; the third operand is evaluated only if the first compares equal to 0; the result is the value of the second or third operand(whichever is evaluated), converted to the type described below. [1] https://stackoverflow.com/questions/65109494/order-of-evaluation-for-ternary-operator-in-c https://stackoverflow.com/questions/65109494/order-of-evalua...
- sk5t 6y ago
  The ternary and unary increment/decrement operators are things I thought I’d miss, but in fact absolutely do not miss. May they forever perish. If-as-expression always!
- solipsism 6y ago
  Firstly, you can't compare if statements to ternary expressions. To compare apples to apples, you need to compare: 1) if statements with single assignment statements in both branches, assigning to the same variable, and 2) assignments with ternary expressions on the right side. In that apples-to-apples comparison, it's really a toss up which is more readable. Looking at the if statement, anyone who has been reading code for any amount of time is going to immediately recognize the pattern. There's no "scanning two sides".
- stitched2gethr 6y ago
  Sorry, perhaps I don't understand how ternary operators are any different than if; then; else. In fact for readability I very much prefer guard statements that don't include an else at all.
  - lmm 6y ago
    if/else can contain arbitrary control flow (return, break, throw, goto) in the bodies, so you have to read the whole body to know what's going on. Ternaries are just expressions so however complex the body is, you know it's always just going to evaluate to a value.
- knuthsat 6y ago
  Early return ifs are great. I usually just transform functions with 2+ if statements into functions without `if` statements by extracting `if` statements into other smaller functions where I can write it with an early return. Looks great.
- progval 6y ago
  > because the two sides of the ternary are guaranteed to be expressions rather than blocks But expressions can contain blocks. Therefore, this is valid: int main(void) { while (1) { 1 ? ({ break; }) : ({ break; }); } } The right way to easily spot control flow construct is syntax highlighting.
ridiculous_fish 6y ago
Lots of code has apparent branches which compilers effectively optimize. An easy example is integer signbit: int isignbit(int x) { return x < 0 ? 1 : 0; } which is reliably optimized to logical right shift. Are there any code patterns where the compiler emits branches that are not apparent in the code? Notwithstanding overflow checks, etc.
- oddity 6y ago
  Some targets don't support integer division/remainder or some floating point ops in hardware and automatic vectorization can add/remove branches in places that won't be easily predictable.
- moonchild 6y ago
  That's a good point, but a bad example since 'x < 0 ? 1 : 0' is just the same as 'x < 0', which is also be implemented (on x86) as a CMP followed by SETcc.
nixpulvis 6y ago
Not to mention branches and branch prediction can be a cause of understudied (and possibly) vulnerable interactions like Spectre/Meltdown. It's also worth mentioning that branching is a critical part of any recursive function, or else it would not know when to terminate. In some cases the function call could be linearized, but it again becomes a compiler runtime cost analysis.
boulos 6y ago
I’d say the behavior is mostly historical. Early GPU “compilers” [1] and their corresponding architectures really meant that “an if statement means go slow”. Also, IIRC, the original mask depth on Fermi was ... 32 branches, and afterwards you’d spill. So it was an adaptation to “don’t make the compiler work harder when you can fold the branch for it”. I always found this to be worse for autovectorization with icc. Every once in a while, it would impress you by calculating masks and then blending. Usually it would not. [1] Many of these “compilers” were really just blindly emitting code with no optimizations. The point was it ran correctly, and was effectively autovectorized. If you cared, you could make it faster.
yakubin 6y ago
As usual, the programmer should look at the generated assembly, when reasoning about performance. Sometimes compilers are smart, optimizing away things people wouldn't imagine they can, and sometimes they are really dumb, pessimizing code in unimaginable ways (to the extent that just deleting code from the output, which doesn't naturally correspond to anything in the source code, makes the output better). Relying on the compiler to perform magic without verifying the results is an antirational stance. Personally, I'd prefer if optimizations were applied based on what's visible in the source code, instead of the wild-west that we have now. E.g. inline function calls based on annotations left by the programmer, not because you (the compiler) feel like it. The Rust compiler can be very good at optimizing iterator pipelines, however a while ago I wrote a function which didn't have any branches whatsoever in it, but the generated assembly was ridden with them. What could have been 5 instructions consisting of simple bit operations (everything done in registers, not loading anything from memory), ended up as 12 (? IIRC) ridden with conditional jumps. No matter how I changed the source code, which operations I used, the output was the same. Getting to the desired result shouldn't be stifled by the compiler having a mind of its own, making its own decisions. A sane default could be set, but some annotations to have a greater control over the result would be appreciated. Optimizing compilers also make debugging harder. Making the the output and the source code closer together would help making sense of a debugging session.
- _ph_ 6y ago
  This is one things I like so much about SBCL, it not only compiles the Lisp code directly to native code, with the disassemble function you can print out the generated code for each function to see how much the compiler was able to optimize a function. This is especially important in the context of dynamic languages to see where generic operators have to be called and where the type inferencer was able to compile it into an assembly instruction like integer multiplication.
  - lispm 6y ago
    Many Lisp compilers do that. What makes SBCL special is a) using type information as compile-time assertions and b) the level of diagnostic output during compilation. The compiler explains in detail when operations can't be optimized further, for example because of lack of type information.
antoineMoPa 6y ago
Testing with only one if statement is not convincing at all. I'm pretty sure that once you have a couple of mixes and steps etc., the branch prediction becomes exponentially harder and you are better off with the one line mixes, step, clamps etc. In general, from experience writing a lot of shaders, I want to avoid if statements, function calls and most importantly loops. Now maybe if statements are efficient in some conditions, but if you want to add new details to the same shader some months later, you can't be sure the generated instructions and branch prediction will be as efficient. There is also coding style: Id rather stick to a bunch of mixes, steps and clamps than a salad of mixes, steps and clamps with some multiline if statements in between.
deleted 6y ago
[deleted]

136 points by wheresvic4 6y ago

Another good example why premature optimization is usually counterproductive. I really like the use of the assembly comparisons to check and prove assumptions.

mhh__ 6y ago
The disassembly can lie, however, i.e. the CPU can do a lot of work in the time a cache miss takes (or some other dependency induced stall, or misprediction) - you have to measure it, in the situation where the code is actually being used (i.e. contrived benchmarks will again often lie as they usually don't fill the cache, and are easy to predict)
- guerrilla 6y ago
  Yeah, I was actually wondering if maybe gcc did that second one with floats on purpose because of profiling data that they have.

lmm 6y ago

Ifs are generally bad for readability though, because they force the reader to understand your control flow. Replacing an if with a ternary makes it more readable, not because the generated code is any different, but because a reader immediately knows that they don't need to scan through the two sides for control flow constructs (because the two sides of the ternary are guaranteed to be expressions rather than blocks). An if might occasionally be clearer than some convoluted algebra, but not often.

cortesoft 6y ago
Some languages allow blocks in a ternary... ruby, for example
caturopath 6y ago
Do you know if there's any evidence that ternaries beat ifs for people understanding code in practice or in people's self-assessments? Would not have been my guess at all.
- ZephyrBlu 6y ago
  An anecdotal data point: I prefer ternaries unless the if statement is for control flow. They're terser and don't stick out as much in the code.
- memco 6y ago
  If Hillel Wayne’s talk on empirical software design is any good measure then either method is fine[0] so long as you and the team you work with can agree about it’s utility in code review. If it’s just you on the project then do whatever is most comfortable. [0] https://m.youtube.com/watch?v=WELBnE33dpY https://m.youtube.com/watch?v=WELBnE33dpY
nopeYouAreWrong 6y ago
I have been reading HN for a long time but your comment is the first time I violently felt the need to create an account and respond. I want you to consider how significant that is. Ternaries are NEVER easier to read.
- xvedejas 6y ago
  Maybe ternaries aren't easier to read, but they make the surrounding code easier to read because they duck out of the way? Devoting several lines to what is a very quick if/else expression could be distracting I suppose. Playing devil's advocate.
  - Buttons840 6y ago
    It's important to note that ternaries are expressions, they evaluate to a value. When I see a ternary I know that a boolean is being mapped to a value. This is true both technically and almost always in practice. If-statements are the wild west. Who knows what an if statement will do? An if-statement may be as simple as a ternary, or it might be a branch point and the resulting logic streams will never meet again.
    - microtherion 6y ago
      We're talking C. As soon as a ternary calls a function, all bets are off what could be happening in addition to the value being computed. And thanks to the preprocessor, any identifier could potentially be calling a function.
      - boulos 6y ago
        Hmm? Which part implies “all bets are off”? There’s the condition (evaluated first), the true case and the false case. Only one of the cases is evaluated. I’m assuming you were alluding to some sort of “x++ = x++ * *x++” style situation, but the ternary expression isn’t a statement and there are sequence points in between. As a bonus, the first result for “ternary operator evaluation order” gave me someone who linked to the standard [1]. Quoting from the standard that they quoted: > The first operand is evaluated; there is a sequence point between its evaluation and the evaluation of the second or third operand (whichever is evaluated). The second operand is evaluated only if the first compares unequal to 0; the third operand is evaluated only if the first compares equal to 0; the result is the value of the second or third operand(whichever is evaluated), converted to the type described below. [1] https://stackoverflow.com/questions/65109494/order-of-evaluation-for-ternary-operator-in-c https://stackoverflow.com/questions/65109494/order-of-evalua...
sk5t 6y ago
The ternary and unary increment/decrement operators are things I thought I’d miss, but in fact absolutely do not miss. May they forever perish. If-as-expression always!
solipsism 6y ago
Firstly, you can't compare if statements to ternary expressions. To compare apples to apples, you need to compare: 1) if statements with single assignment statements in both branches, assigning to the same variable, and 2) assignments with ternary expressions on the right side. In that apples-to-apples comparison, it's really a toss up which is more readable. Looking at the if statement, anyone who has been reading code for any amount of time is going to immediately recognize the pattern. There's no "scanning two sides".
stitched2gethr 6y ago
Sorry, perhaps I don't understand how ternary operators are any different than if; then; else. In fact for readability I very much prefer guard statements that don't include an else at all.
- lmm 6y ago
  if/else can contain arbitrary control flow (return, break, throw, goto) in the bodies, so you have to read the whole body to know what's going on. Ternaries are just expressions so however complex the body is, you know it's always just going to evaluate to a value.
knuthsat 6y ago
Early return ifs are great. I usually just transform functions with 2+ if statements into functions without `if` statements by extracting `if` statements into other smaller functions where I can write it with an early return. Looks great.
progval 6y ago
> because the two sides of the ternary are guaranteed to be expressions rather than blocks But expressions can contain blocks. Therefore, this is valid: int main(void) { while (1) { 1 ? ({ break; }) : ({ break; }); } } The right way to easily spot control flow construct is syntax highlighting.

ridiculous_fish 6y ago

Lots of code has apparent branches which compilers effectively optimize. An easy example is integer signbit: int isignbit(int x) { return x < 0 ? 1 : 0; } which is reliably optimized to logical right shift. Are there any code patterns where the compiler emits branches that are not apparent in the code? Notwithstanding overflow checks, etc.

oddity 6y ago
Some targets don't support integer division/remainder or some floating point ops in hardware and automatic vectorization can add/remove branches in places that won't be easily predictable.
moonchild 6y ago
That's a good point, but a bad example since 'x < 0 ? 1 : 0' is just the same as 'x < 0', which is also be implemented (on x86) as a CMP followed by SETcc.

nixpulvis 6y ago

Not to mention branches and branch prediction can be a cause of understudied (and possibly) vulnerable interactions like Spectre/Meltdown. It's also worth mentioning that branching is a critical part of any recursive function, or else it would not know when to terminate. In some cases the function call could be linearized, but it again becomes a compiler runtime cost analysis.

boulos 6y ago

I’d say the behavior is mostly historical. Early GPU “compilers” [1] and their corresponding architectures really meant that “an if statement means go slow”. Also, IIRC, the original mask depth on Fermi was ... 32 branches, and afterwards you’d spill. So it was an adaptation to “don’t make the compiler work harder when you can fold the branch for it”. I always found this to be worse for autovectorization with icc. Every once in a while, it would impress you by calculating masks and then blending. Usually it would not. [1] Many of these “compilers” were really just blindly emitting code with no optimizations. The point was it ran correctly, and was effectively autovectorized. If you cared, you could make it faster.

yakubin 6y ago

As usual, the programmer should look at the generated assembly, when reasoning about performance. Sometimes compilers are smart, optimizing away things people wouldn't imagine they can, and sometimes they are really dumb, pessimizing code in unimaginable ways (to the extent that just deleting code from the output, which doesn't naturally correspond to anything in the source code, makes the output better). Relying on the compiler to perform magic without verifying the results is an antirational stance. Personally, I'd prefer if optimizations were applied based on what's visible in the source code, instead of the wild-west that we have now. E.g. inline function calls based on annotations left by the programmer, not because you (the compiler) feel like it. The Rust compiler can be very good at optimizing iterator pipelines, however a while ago I wrote a function which didn't have any branches whatsoever in it, but the generated assembly was ridden with them. What could have been 5 instructions consisting of simple bit operations (everything done in registers, not loading anything from memory), ended up as 12 (? IIRC) ridden with conditional jumps. No matter how I changed the source code, which operations I used, the output was the same. Getting to the desired result shouldn't be stifled by the compiler having a mind of its own, making its own decisions. A sane default could be set, but some annotations to have a greater control over the result would be appreciated. Optimizing compilers also make debugging harder. Making the the output and the source code closer together would help making sense of a debugging session.

_ph_ 6y ago
This is one things I like so much about SBCL, it not only compiles the Lisp code directly to native code, with the disassemble function you can print out the generated code for each function to see how much the compiler was able to optimize a function. This is especially important in the context of dynamic languages to see where generic operators have to be called and where the type inferencer was able to compile it into an assembly instruction like integer multiplication.
- lispm 6y ago
  Many Lisp compilers do that. What makes SBCL special is a) using type information as compile-time assertions and b) the level of diagnostic output during compilation. The compiler explains in detail when operations can't be optimized further, for example because of lack of type information.

antoineMoPa 6y ago

Testing with only one if statement is not convincing at all. I'm pretty sure that once you have a couple of mixes and steps etc., the branch prediction becomes exponentially harder and you are better off with the one line mixes, step, clamps etc. In general, from experience writing a lot of shaders, I want to avoid if statements, function calls and most importantly loops. Now maybe if statements are efficient in some conditions, but if you want to add new details to the same shader some months later, you can't be sure the generated instructions and branch prediction will be as efficient. There is also coding style: Id rather stick to a bunch of mixes, steps and clamps than a salad of mixes, steps and clamps with some multiline if statements in between.

deleted 6y ago

[deleted]