The Weird Concept of Branchless Programming
sanixdk.xyz
The Weird Concept of Branchless Programming
1–10 of 92 posts
Re: The Weird Concept of Branchless Programming
#2I 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 changed that conclusion.
Re: The Weird Concept of Branchless Programming
#3This great video [0] demonstrates how CPU performance has only increased 1.5-2x over the past 15(!) years when executing extremely branchy code. Really shows you just how deep modern CPU pipelines have become.
The video also showcases a much more impressive branchless speedup: computing CRC checksums. Doing this naïvely with an if-statement for each bit is ~10x slower than doing it branchless with a single bitwise operation for each bit. The author of the article should consider showcasing this too, since it's a lot more impressive than the measly 1.2x speedup highlighted in the article. I assume the minimal/nonexistent speedups in the article are due to modern CPU branch prediction being quite good. But branch predictors inherently fail miserably at CRC because the conditional is on whether the input bit is 1 or 0, which is essentially random.
Re: The Weird Concept of Branchless Programming
#4Great 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
Re: The Weird Concept of Branchless Programming
#5Article doesn’t mention this, but I’d consider neural networks a form of branchless programming. It’s all a bunch of multiply and threshold operations.
Re: The Weird Concept of Branchless Programming
#6Article doesn’t mention this, but I’d consider neural networks a form of branchless programming. It’s all a bunch of multiply and threshold operations.
Thresholding requires branching no?
Re: The Weird Concept of Branchless Programming
#7The article is easy to follow but I think the author missed the e point: branchless programming (a subset of the more known constant time programming) is almost exclusively used in cryptography only nowadays. As shown by the benchmarks in the article, modern branch predictors can easily achieve over 95% if not 99% precision since like a decade ago
Re: The Weird Concept of Branchless Programming
#8This same blog posted yesterday and got flagged with “How I accidently created the fastest CSV parser ever made”
Re: The Weird Concept of Branchless Programming
#9Article doesn’t mention this, but I’d consider neural networks a form of branchless programming. It’s all a bunch of multiply and threshold operations.
Thresholding requires branching no?
No, you can do that without branching. See https://en.algorithmica.org/hpc/pipelining/branchless/#predi... for example.