[HN Gopher] Is This a Branch? (2021)
___________________________________________________________________
Is This a Branch? (2021)
Author : segfaultbuserr
Score : 28 points
Date : 2023-07-29 18:08 UTC (1 days ago)
(HTM) web link (bartwronski.com)
(TXT) w3m dump (bartwronski.com)
| MrYellowP wrote:
| 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 wrote:
| 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 wrote:
| >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.
| mattnewport wrote:
| 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 wrote:
| Its a shame that few modern languages make using clamp,
| saturate etc as simple as "normal" arithmetic.
| mmphosis wrote:
| 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 wrote:
| Discussed at the time:
|
| _Is This a Branch?_ -
| https://news.ycombinator.com/item?id=26141047 - Feb 2021 (74
| comments)
___________________________________________________________________
(page generated 2023-07-30 23:01 UTC)