Recent searches
Search options
CPU code optimization is always fun. Those statements are all true statements:
- Doing more isn't slower than doing less
- Simpler code isn't faster than complex code
- Executing only one logical branch in an if-else isn't faster than executing both branches and picking the right result later.
- Branching isn't slower than not branching at all.
Premature optimization includes also "obvious" things, because you'll be wrong if you don't benchmark it.
It always depends on the exact thing.
Picking the point "Branching isn't slower than not branching at all" in particular that confused my intuition and actual measurement and asm analysis proved me wrong.
The case study was my attempt to optimize a comparator function, where there are multiple criteria, cascaded results of -1/0/1 comparison. The hypothesis was that encoding the 3 state results of the comparisons into one int value would be faster than a series of ifs. How wrong I was. The ifs always won, even for an artificial worst case (all ifs wrong), vs a fixed sequence of bit encoding returning one int as "strcmp" result.
The analysis was based on llvm-mca (instruction-level analysis, really great tool providing insights to micro arch optimizations). It was fun to reinvent new bit tricks only to find them on https://graphics.stanford.edu/~seander/bithacks.html . I guess the branch prediction is working well even for hard to predict data like sorting arrays.
@kdave @karolherbst it is a bit difficult to me to talk to complete strangers about this, but drawing conclusions of how branchy code is going to compare to branchless from llvm-mca does not sound like a good idea
(and while at it, if you like llvm-mca, please let me point you to https://uica.uops.info, it has a great deal of research behind it (see link on top, including a dissertation), and is more accurate)