Only a few of these are actual programming tricks. The problem with sharing them is that they'll typically seem obvious to you, since you know them. It's difficult to know what is actually unknown to other people, and if you share stuff everybody knows you risk coming off as arrogant.
Here's one that I think more people should know: avoid branches. If I can do the same thing without an if statement and even a logical expression, the code typically both becomes easier to understand for people and easier to run for the CPU.
I'm struggling to comprehend how branches can be avoided (or why one would want to, as they are the cornerstone of programming). I can only think how to obfuscate them, which is rarely useful.
What people refer to when they say "branchless code" is something very particular, and it refers to not triggering the CPU's branch prediction. That is, don't make the CPU have to guess which fork in the code you're going to take. This is usually accomplished in one of two ways: either bit twiddling hacks or specialized instructions that do not affect the CPU's branch prediction, such as the 'cmov' family in x86. If you search for `examples of branchless code using conditional moves` using your search engine of choice, you'll find numerous examples.
A trivial example is actually written with a branch in C/C++, but relies on compiler optimizations to kick in. If you compile a ternary operator in C/C++ (and probably rust, C# and other languages) such as in:
int min_branchless(int a, int b) {
return a < b ? a : b; // Often emits cmov with -O2
}
With gcc/clang a -O2, one would expect the compiler to emit the following assembly:
cmp edi, esi
cmovle eax, edi ; select a if a <= b
ret
There's numerical tricks for other operations/comparisons, and compilers know a lot of them. But, I just suggest compiling your code and configuring your compiler to emit the generated assembly with references to the code it was generated from (you should be able to get it to emit source line references in the assembly). You'll likely be surprised at the optimizations applied at -02, and utterly confused by what you find at -03.
edit: Also, it doesn't mean to never branch, but to minimize branching, especially in tight loops. Branch outside loops, not inside, for instance.
e.g. don't do:
for (...) {
if (condition independent of loop variable) {
...
} else {
...
}
}
do:
if (condition independent of loop variable) {
for (...) {
...
}
} else {
for (...) {
...
}
}
The latter example, sounds like something trivially done by the compiler. I mean I would sometimes, adhere to it, but only if the loops afterwards become substantially different. If I would just repeat most of the loop body, I would prefer the former.
> The latter example, sounds like something trivially done by the compiler.
Taken by itself? Absolutely. In the middle of 50-deep templatized call stack? Maybe not. Compilers have their limitations (memory, runtime, other cost budgeting algorithms), and the more complex the code, the hard the optimizer has to work. But, yeah. Most of the gains from branchless code is going to come from this like numerical tools, vectorization and loop unrolling, things of that nature. It was an admittedly contrived example.
winternewt · · focus · HN ↗
Here's one that I think more people should know: avoid branches. If I can do the same thing without an if statement and even a logical expression, the code typically both becomes easier to understand for people and easier to run for the CPU.
cachvico · · focus · HN ↗
hermitdev · · focus · HN ↗
A trivial example is actually written with a branch in C/C++, but relies on compiler optimizations to kick in. If you compile a ternary operator in C/C++ (and probably rust, C# and other languages) such as in:
With gcc/clang a -O2, one would expect the compiler to emit the following assembly: There's numerical tricks for other operations/comparisons, and compilers know a lot of them. But, I just suggest compiling your code and configuring your compiler to emit the generated assembly with references to the code it was generated from (you should be able to get it to emit source line references in the assembly). You'll likely be surprised at the optimizations applied at -02, and utterly confused by what you find at -03.edit: Also, it doesn't mean to never branch, but to minimize branching, especially in tight loops. Branch outside loops, not inside, for instance.
e.g. don't do:
do:1718627440 · · focus · HN ↗
hermitdev · · focus · HN ↗
Taken by itself? Absolutely. In the middle of 50-deep templatized call stack? Maybe not. Compilers have their limitations (memory, runtime, other cost budgeting algorithms), and the more complex the code, the hard the optimizer has to work. But, yeah. Most of the gains from branchless code is going to come from this like numerical tools, vectorization and loop unrolling, things of that nature. It was an admittedly contrived example.
1718627440 · · focus · HN ↗
That is also not going to be done by a developer, so it's not a counter argument against deferring such work to the compiler.