Is This a Branch?
bartwronski.com
bartwronski.com
The Rust compiler can be very good at optimizing iterator pipelines, however a while ago I wrote a function which didn't have any branches whatsoever in it, but the generated assembly was ridden with them. What could have been 5 instructions consisting of simple bit operations (everything done in registers, not loading anything from memory), ended up as 12 (? IIRC) ridden with conditional jumps. No matter how I changed the source code, which operations I used, the output was the same. Getting to the desired result shouldn't be stifled by the compiler having a mind of its own, making its own decisions. A sane default could be set, but some annotations to have a greater control over the result would be appreciated.
Optimizing compilers also make debugging harder. Making the the output and the source code closer together would help making sense of a debugging session.
What makes SBCL special is a) using type information as compile-time assertions and b) the level of diagnostic output during compilation. The compiler explains in detail when operations can't be optimized further, for example because of lack of type information.
If you have a desired assembly result, write it yourself in the first place.
The one concession to this I would like is a "constant time" marker for cryptography functions where it is an absolutely critical property that there be no data dependant branches.
(This is a little different on GPUs where branches are so unreasonably expensive, and it sounds like that would also benefit from "no branches here" markers. The downside of this is that it makes valid code un compilable if the compiler can't find a branchless way of doing it.)
It's very early days, but I hope to get something usable by 2025.
You can't "take this into account" because it requires state that isn't visible to you and also requires you to know the design of future hardware!
Yes, these tricks don't have forwards-compatible guarantees in the general case – but if the processor manufacturer makes guarantees about all members of a family, then you can optimise to those, and in any case having something that provably works in all supported processors (and can be ported to later processors if necessary, just by using an extra library (if the library is correct)) is still useful.
For mutating branch predictor state at will, you will need your compiler to write self modifying cache. This will pollute the icache and further mutate the state based on where the cache line lies, and the current state of the icache.
You could maybe restrict your target to open source hardware and come up with something.
No – but the compiler would presumably be told how the specific processor's cache works. If it's possible for a human to write cache-flushing code, it's possible to describe it to a computer. (And that was just an example.)
> For mutating branch predictor state at will, you will need your compiler to write self modifying code.
Only for arbitrary modifications. For specific modifications, it's fine to go with ordinary code – though self-modifying code isn't actually all that hard to model, if you generalise “state” to also encompass the state of the self-modifying section. (Compilers already have “all branches” type things.)
> You could maybe restrict your target to open source hardware
There's no need to make this restriction. You only need sufficiently-understood hardware; you underestimate the ability of reverse-engineers.
Another major question: a lot of x86 ops for manipulating things you want to manipulate are ring 0 instructions.
We haven’t even discussed the effect of somewhat non deterministic delays caused by contention from other processes. This can change the true execution order of instruction inside the pipes, even if you somehow manage to enforce in order issue.
int isignbit(int x) { return x < 0 ? 1 : 0; }
Are there any code patterns where the compiler emits branches that are not apparent in the code? Notwithstanding overflow checks, etc.
Early GPU “compilers” [1] and their corresponding architectures really meant that “an if statement means go slow”. Also, IIRC, the original mask depth on Fermi was ... 32 branches, and afterwards you’d spill. So it was an adaptation to “don’t make the compiler work harder when you can fold the branch for it”.
I always found this to be worse for autovectorization with icc. Every once in a while, it would impress you by calculating masks and then blending. Usually it would not.
[1] Many of these “compilers” were really just blindly emitting code with no optimizations. The point was it ran correctly, and was effectively autovectorized. If you cared, you could make it faster.
I really like the use of the assembly comparisons to check and prove assumptions.
I'm pretty sure that once you have a couple of mixes and steps etc., the branch prediction becomes exponentially harder and you are better off with the one line mixes, step, clamps etc. In general, from experience writing a lot of shaders, I want to avoid if statements, function calls and most importantly loops.
Now maybe if statements are efficient in some conditions, but if you want to add new details to the same shader some months later, you can't be sure the generated instructions and branch prediction will be as efficient.
There is also coding style: Id rather stick to a bunch of mixes, steps and clamps than a salad of mixes, steps and clamps with some multiline if statements in between.
It's also worth mentioning that branching is a critical part of any recursive function, or else it would not know when to terminate. In some cases the function call could be linearized, but it again becomes a compiler runtime cost analysis.
If-statements are the wild west. Who knows what an if statement will do? An if-statement may be as simple as a ternary, or it might be a branch point and the resulting logic streams will never meet again.
And thanks to the preprocessor, any identifier could potentially be calling a function.
There’s the condition (evaluated first), the true case and the false case. Only one of the cases is evaluated.
I’m assuming you were alluding to some sort of “x++ = x++ * *x++” style situation, but the ternary expression isn’t a statement and there are sequence points in between. As a bonus, the first result for “ternary operator evaluation order” gave me someone who linked to the standard [1]. Quoting from the standard that they quoted:
> The first operand is evaluated; there is a sequence point between its evaluation and the evaluation of the second or third operand (whichever is evaluated). The second operand is evaluated only if the first compares unequal to 0; the third operand is evaluated only if the first compares equal to 0; the result is the value of the second or third operand(whichever is evaluated), converted to the type described below.
[1] https://stackoverflow.com/questions/65109494/order-of-evalua...
My point was that since ternaries can call functions, and functions can have side effects on global state, the concept of an "if" being a "statement" vs a ternary being an "expression / value" is not nearly as meaningful as it's made out to be. A ternary can trade stocks, fire a 500W laser, unlock a velociraptor enclosure, etc, just as easily as an if can.
We can objectively say that ternaries are shorter and simpler however. (Simpler because they can do fewer things than an if-statement or if-expression.)
So, you can do (untested)
foo = bar ? ({a=1;b=2;}) : ({a=2;b=1;});
That’s widely supported in other compilers for compatibility reasons (https://stackoverflow.com/questions/6440021/compiler-support...)
You can also (mis)use the comma operator like this (again untested):
foo = bar ? f(),g() : g(),f();
In a more serious tone, ternaries in places where they should be used, i.e. as expressions, are in my opinion much clearer to read than replacing them with an if-else statement. In my mind, an if/else block is an imperative entity that describes two different actions that could happen. Even if in reality both branches are trivial, my mind will be unnecessarily occupied with the fact that it needs to reason about code here, not just data. A ternary, on the other hand, is a declarative entity, saying that this expression takes on this or that value, usually in such a way that each branch of it maintains some invariant with respect to what's in the conditional.
That's true in some languages. But in some languages if-else can also be used as in expression. e.g. in Rust I can write:
let foo = if condition { "FOO" } else { "BAR" }So many languages use clear words like "if" and "then" and "else" and parens and curly braces for conditional statements...
But then they go full Perl and mash their faces against the keyboard when developing syntax for conditional expressions.
It's bone-headed language-design that C did wrong and everybody else continues to do wrong because C.
myvar = condition_1 ? value_1
: condition_2 ? value_2
: condition_3 ? value_3
: value_fallback;Under what circumstances would that happen? I've never encountered a nested ternary that wouldn't be better replaced with readable code, so now I'm wondering what experiences I've been missing. :)
myvar = if(condition_1) {value_1}
else if(condition_2) {value_2}
else if(condition_3) {value_3}
else {value_fallback}; #define TERN(c, a, b) c ? a : b
#define TERN(c, a, b) ((c) ? (a) : (b))As Liquid_Fire points out, it's also probably incorrect.
Here's a concrete example:
const int min = x < y ? x : y;
int min;
if (x < y)
min = x;
else
min = y;
-- example:
var x;
if(this)
x = 10;
else
x = 11;
-- is uglier than:
var x = this ? 10 : 11;
int x = (cond)
? 5
: 1; int x = (cond) ?
5 :
1; printf(condition? "YES": "NO");
if (condition) {
printf("YES")
} else {
printf("NO")
}In that apples-to-apples comparison, it's really a toss up which is more readable. Looking at the if statement, anyone who has been reading code for any amount of time is going to immediately recognize the pattern. There's no "scanning two sides".
I usually just transform functions with 2+ if statements into functions without `if` statements by extracting `if` statements into other smaller functions where I can write it with an early return.
Looks great.
But expressions can contain blocks. Therefore, this is valid:
int main(void) {
while (1) {
1 ? ({ break; }) : ({ break; });
}
}