4 ms·

Is This a Branch? (2021)

dang 3y ago
Discussed at the time: Is This a Branch? - https://news.ycombinator.com/item?id=26141047 https://news.ycombinator.com/item?id=26141047 - Feb 2021 (74 comments)
MrYellowP 3y ago
One of my favourite things in programming is getting rid of the conditional branches. They're great to keep the brain fresh, because sometimes you have to dig ten layers outward to rewrite your code just to get rid of that fucking condition that slows down the code. Or a good one I recall, was my 2D-box-check. I've made the mistake believing that not writing the output to RAM, when the result yields "not in box" would be better. So naturally I checked for every output if the respective bit was 1 or 0 and a 0 restarted the loop early. Nope. It was faster to just always write to memory, but linking the result to a multiplication which increments the pointer based on the above mentioned bit. "Not in box" increased the pointer by 0 (n * 0 = 0). Boom, one billion 2d-box-checks per second on an i5 7500HQ on a single core without using SIMD. Good enough. I ... guess I should stop now. (PS: this was used for a sprite engine for a super-high resolution text mode, which compiled sprites into the code that wrote them to the screen. That's a LOT faster than checking if a character/pixel needs not-to-be-written AND it allowed for potentially eight pixels/characters to be drawn at once, too, using pop! ... I really should stop now. ^_^)
- segfaultbuserr 3y ago
  Getting rid of conditional branches is also a major brain-teaser when you're writing safe constant-time cryptography code. In assembly code, a common trick is exploiting the side-effect of the carry/borrow flag. You write the code in such a way that the condition will set the carry flag. Perhaps it's an overflow during an addition, or perhaps it comes from a bitwise shift. The carry flag can then be expanded into an integer by subtracting a register from itself via "subtract with borrow". If the carry flag was not set, the register becomes 0x00000000, if it was set, the register underflows to 0xFFFFFFFF. Then one can use it as a "yes/no" bitmask in some bitwise expressions.
  - charcircuit 3y ago
    >Getting rid of conditional branches is also a major brain-teaser when you're writing safe constant-time cryptography code. It is not possible to write constant time code on a modern machine and OS. The important thing is that the time taken should not depend on any of the inputs.
    - segfaultbuserr 3y ago
      It's absolutely possible (though not necessarily easy) to write constant-time code on a modern machine and OS. In cryptography, "constant-time" does not mean the code literally takes the same amount of time, it's a technically term which a clear technical definition, "code that does not leak secret information through timing analysis." I didn't invent the terms, argue with cryptographers instead. Furthermore, many cryptography applications run on simple embedded hardware. In these cases, it can literally be "constant-time" code, which is likely where the term originated from. But it's no longer the definition.
    - zogrodea 3y ago
      Was it possible on older machines and operating systems? I'm afraid I don't know enough about low-level performance but I always enjoy learning more.
      - charcircuit 3y ago
        Yes. The main problems are dynamic frequency scaling, because it changes the rate instructions are processed, preemptive multitasking, which can potentially destroy various caches in the middle of your code, and hyperthreading, where the processor can switch between executing two different things.
        zogrodea 3y ago
        Oh, I see. Thanks for the information. That's good to know. Appreciate it!
mattnewport 3y ago
Code that uses min, max, clip, clamp, saturate, etc. when that is straightforwardly what operation is needed is clearer, more explicit, more concise and potentially faster. When used this way they are just straightforwardly better than equivalent if then statements. Occasionally you see code that uses combinations of these in less obvious ways to do some more complex operation and I can see how one could argue that in rare cases that ends up less clear than if then statements but I've never really encountered that in many years of reading shader code. There are other reasons to prefer functions over if then in shader code not discussed here as well, like replacing step with smoothstep for antialiasing.
- gumby 3y ago
  Its a shame that few modern languages make using clamp, saturate etc as simple as “normal” arithmetic.
mmphosis 3y ago
I like the readable version better than my bit twiddling: int is_this_a_branch(int v, int w) { int t; t = !(v < 10); return (v + ((w ^ -t) + t)) << t; } cc -O3 -c branch.c objdump -drwC -Mintel -S branch.o

dang 3y ago

Discussed at the time: Is This a Branch? - https://news.ycombinator.com/item?id=26141047 https://news.ycombinator.com/item?id=26141047 - Feb 2021 (74 comments)

MrYellowP 3y ago

One of my favourite things in programming is getting rid of the conditional branches. They're great to keep the brain fresh, because sometimes you have to dig ten layers outward to rewrite your code just to get rid of that fucking condition that slows down the code. Or a good one I recall, was my 2D-box-check. I've made the mistake believing that not writing the output to RAM, when the result yields "not in box" would be better. So naturally I checked for every output if the respective bit was 1 or 0 and a 0 restarted the loop early. Nope. It was faster to just always write to memory, but linking the result to a multiplication which increments the pointer based on the above mentioned bit. "Not in box" increased the pointer by 0 (n * 0 = 0). Boom, one billion 2d-box-checks per second on an i5 7500HQ on a single core without using SIMD. Good enough. I ... guess I should stop now. (PS: this was used for a sprite engine for a super-high resolution text mode, which compiled sprites into the code that wrote them to the screen. That's a LOT faster than checking if a character/pixel needs not-to-be-written AND it allowed for potentially eight pixels/characters to be drawn at once, too, using pop! ... I really should stop now. ^_^)

segfaultbuserr 3y ago
Getting rid of conditional branches is also a major brain-teaser when you're writing safe constant-time cryptography code. In assembly code, a common trick is exploiting the side-effect of the carry/borrow flag. You write the code in such a way that the condition will set the carry flag. Perhaps it's an overflow during an addition, or perhaps it comes from a bitwise shift. The carry flag can then be expanded into an integer by subtracting a register from itself via "subtract with borrow". If the carry flag was not set, the register becomes 0x00000000, if it was set, the register underflows to 0xFFFFFFFF. Then one can use it as a "yes/no" bitmask in some bitwise expressions.
- charcircuit 3y ago
  >Getting rid of conditional branches is also a major brain-teaser when you're writing safe constant-time cryptography code. It is not possible to write constant time code on a modern machine and OS. The important thing is that the time taken should not depend on any of the inputs.
  - segfaultbuserr 3y ago
    It's absolutely possible (though not necessarily easy) to write constant-time code on a modern machine and OS. In cryptography, "constant-time" does not mean the code literally takes the same amount of time, it's a technically term which a clear technical definition, "code that does not leak secret information through timing analysis." I didn't invent the terms, argue with cryptographers instead. Furthermore, many cryptography applications run on simple embedded hardware. In these cases, it can literally be "constant-time" code, which is likely where the term originated from. But it's no longer the definition.
  - zogrodea 3y ago
    Was it possible on older machines and operating systems? I'm afraid I don't know enough about low-level performance but I always enjoy learning more.
    - charcircuit 3y ago
      Yes. The main problems are dynamic frequency scaling, because it changes the rate instructions are processed, preemptive multitasking, which can potentially destroy various caches in the middle of your code, and hyperthreading, where the processor can switch between executing two different things.
      - zogrodea 3y ago
        Oh, I see. Thanks for the information. That's good to know. Appreciate it!

mattnewport 3y ago

Code that uses min, max, clip, clamp, saturate, etc. when that is straightforwardly what operation is needed is clearer, more explicit, more concise and potentially faster. When used this way they are just straightforwardly better than equivalent if then statements. Occasionally you see code that uses combinations of these in less obvious ways to do some more complex operation and I can see how one could argue that in rare cases that ends up less clear than if then statements but I've never really encountered that in many years of reading shader code. There are other reasons to prefer functions over if then in shader code not discussed here as well, like replacing step with smoothstep for antialiasing.

gumby 3y ago
Its a shame that few modern languages make using clamp, saturate etc as simple as “normal” arithmetic.

mmphosis 3y ago

I like the readable version better than my bit twiddling: int is_this_a_branch(int v, int w) { int t; t = !(v < 10); return (v + ((w ^ -t) + t)) << t; } cc -O3 -c branch.c objdump -drwC -Mintel -S branch.o