Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Weird Concept of Branchless Programming

sanixdk.xyz

Post reply on HN
Print view View original

81–90 of 92 posts

Re: The Weird Concept of Branchless Programming

#81

Post by ashdnazg »

okaleniuk wrote: post #80

Some safety critical real time systems have strict time predictability requirements. This means that the whole loop should pass in exactly X microsecond, not more not less. For this, all the programming should be pretty much branchless. For instance, all the sorting algorithm turn to, effectively, bubble sort since without branches, you always go with the worst case - and the sorting complexity is always the O(n^2).…

O(n^2) isn't required. One could do an in-place merge-sort, which is also always worst case, but with O(n*log(n)).

I suspect everyone turns to Bubblesort since the inputs are small enough that it doesn't matter (evident by the fact that it should fit within microseconds).

Re: The Weird Concept of Branchless Programming

#82

Post by rmnclmnt »

kccqzy wrote: post #52
rmnclmnt wrote: post #4

Great article, triggers some memories. When you get to think about branchless programming, especially for SIMD optimizations in the real world, you always learn a lot and it’s as if you get a +1 level on your algorithmic skills. The hardest part then is make sure the tricks are clearly laidout so that someone else can take it from here next time

It also triggered some memories for me too. A college professor wanted to teach all the bit manipulating stuff and gave an assignment where students had to transform branchy code into branchless code using shifts and bit operators. Had a lot of fun doing that.

Yeah this is the kind of thinking opening up new heights when you get it!

These type of exercises should be mandatory for all compute intensive related jobs, especially for all data science people (i know some of them know this stuff but that does not seem to be the majority)

Re: The Weird Concept of Branchless Programming

#83

Post by TuxSH »

Joker_vD wrote: post #34

Just so you know, the "return x abs_branch: mov eax, edi neg eax cmovs eax, edi ret on x64, and into abs_branch: srai a5,a0,31 xor a0,a5,a0 sub a0,a0,a5 ret on RISC-V if you use a C compiler with a half-decent codegen. And "branchy" clamp() translates into clamp: cmp edi, edx mov eax, esi cmovle edx, edi cmp edi, esi cmovge eax, edx ret Seriously, the automatic transformation between ?: and if-then-else (in both dire…

In fact, I have seen gcc optimize clever hacks that tried to use multiplication, into conditional moves (on aarch32).

There is this common misconception that conditional moves == branching. On actually relevant software architectures, they very much are not. Replacing a p=0.5 branch into a conditional move is in itself a significant optimization.

Re: The Weird Concept of Branchless Programming

#85

Post by toast0 »

userbinator wrote: post #75
toast0 wrote: post #72

Earlier quoted context omitted.

Do they? I put together two quick and dirty nonsense test programs this is option2: int main (void) { for (int i = 0; i option1 has the extraneous mov ecx, eax, and then add with ecx. I confirmed with objdump -d that the assembly hadn't been touched and that the loops were the same. On my otherwise mostly idle dual L5640 system and pinned to a single cpu (just in case), option1 consistently runs in 3.14 seconds and o…

Microbenchmarks don't usually tell the whole story. Once the bloat adds up the cache misses and macro-scale benchmarks will show a difference.

I'm sure the size penalty adds up in some cases.

But if you look at your program that must go faster, and you see unnecessary moves in the hot section(s), go ahead and remove them, but don't be surprised if it doesn't change much.

If you went and did your whole program by hand, the debloating might also not change much. That's why there's a rule of thumb.

If you have the skill to make a change to the compiler so it can output a better sequence of instructions, I suspect thsat's pretty difficult, but it may make enough of a difference over a large number of programs to be worthwhile.

Re: The Weird Concept of Branchless Programming

#86

Post by xigoi »

zeckalpha wrote: post #50
Joker_vD wrote: post #34

Just so you know, the "return x abs_branch: mov eax, edi neg eax cmovs eax, edi ret on x64, and into abs_branch: srai a5,a0,31 xor a0,a5,a0 sub a0,a0,a5 ret on RISC-V if you use a C compiler with a half-decent codegen. And "branchy" clamp() translates into clamp: cmp edi, edx mov eax, esi cmovle edx, edi cmp edi, esi cmovge eax, edx ret Seriously, the automatic transformation between ?: and if-then-else (in both dire…

The inverse problem is here too: > int partition_branchless(int* arr, int low, int high) {... for (int j = low; j That for loop is just a sugared while loop which is just a sugared cmp and jmp

The articleesays that it optimizes just the inside of the loop (the loop jump can be optimized via unrolling, which the compiler may do automatically).

Re: The Weird Concept of Branchless Programming

#87

Post by Someone »

gizmo686 wrote: post #30
sfilmeyer wrote: post #2

I enjoyed reading the article, but I'm pretty thrown by the benchmarks and conclusion. All of the times are reported to a single digit of precision, but then the summary is claiming that one function shows an improvement while the other two are described as negligible. When all the numbers presented are "~5ms" or "~6ms", it doesn't leave me confident that small changes to the benchmarking might have substantially cha…

Yeah. When your timing results are a single digit multiple of your timing precision, that is a good indication you either need a longer test, or a more precise clock. At a 5ms baseline with millisecond precision, the smallest improvement you can measure is 20%. And you cannot distinguish a 20% speedup with a 20% slowdown that happened to get luck with clock ticks. For what it is worth, I ran the provided test code on…

> I had to drop down to O0 to see branchless be faster in any case

Did you check whether your branchy code actually still was branchy after the compiler processed it at higher optimization levels?

Re: The Weird Concept of Branchless Programming

#88

Post by Someone »

adrianmonk wrote: post #14

I've always wondered if any CPUs have tried to reduce the branch penalty by speculatively executing both ways at once in parallel. You'd have two of everything (two pipelines, two ALUs, two sets of registers, etc.) and when you hit a conditional branch, instead of guessing which way to go, you'd essentially fork. Obviously that requires a lot of extra transistors and you are doing computation that will be thrown away…

> You'd have two of everything (two pipelines, two ALUs, two sets of registers, etc.)

As others said: yes, it has been tried and it works, but it costs a lot in hardware and power usage. A problem is that lots of code has a branch every 10 or so instructions. Fast high-end CPUs (the only realistic target for this feature) can dispatch multiple instructions per cycle. Combined that means you will hit a branch every two or three cycles. Because of that, you do not end up with two of everything but with way more.

So, you’re throwing away not 50% of your work but easily 80%.

Some code has fewer branches, but that often can easily be parallelized or vectorized.

Re: The Weird Concept of Branchless Programming

#89

Post by jasonwatkinspdx »

adastra22 wrote: post #74
jasonwatkinspdx wrote: post #28

Earlier quoted context omitted.

Yes, it's been looked at. If you wanna skim the research use "Eager Execution" and "Disjoint Eager Execution" as jumping off points. It doesn't require duplicating everything. You just need to add some additional bookkeeping of dependencies and what to retire vs kill at the end of the pipeline. In practice branch predictors are so good that speculating off the "spine" of most likely path just isn't worth it. In fact…

I think you’re missing the context: that good branch prediction is what causes these security holes. “Wasteful” multi path execution is a security feature.

No, security vulnerabilities are orthogonal. There's nothing about branch prediction that necessitates leaking information, as demonstrated by the fixes shipped in current processors.
Post reply on HN