Hacker News Reader

Comment by dist1ll | Hacker News Reader

Could you explain what zero-folding is?

Others have covered it here, using masks, multiplies, or horizontal operations to avoid branching by running the logic for all of the branches is common in vectorized code (and shader operations for similar reasons), where raw compute outruns branch mis-prediction costs for deeply pipelined processors.

In older SSE architectures, memory alignment and register-to-register result latencies sometimes made it easier/better to stride operations on partially-masked registers rather than reorganize the data. With high architectural register counts and newer shuffling instructions, that need is lower.

Definitely avoid branching in tight compute code, though. Branching kills performance, sometimes in very data-dependent and annoying ways.

To add to your last point: look at the optimised assembly and see if your code actually does contain branches. The compiler can see through certain if statements and replace them with cmov instructions. Replacing that with a complex sequence of arithmetic to get rid of the 'if' might make performance worse rather than better.

No rule is strictly true in optimization, except the rule that no rule is strictly true in optimization...

It's quite often the case that branches are bad for performance in tight loops, so It's better to treat branches as likely sources of trouble than as no big deal.

I agree. I'm just saying, what is and is not a branch is not obvious.

“Avoid branches” isn’t strictly true in scalar code (and sometimes vector code) - zero folding leads to longer dependency chains, so if your branch is very predictable and doesn’t preclude other optimizations (I.e. vectorizing) the branch can be faster.

You mileage may vary, depending on how much reordering capacity the hardware has, how good the branch predictor is, how expensive a mispredict is, whether the extra dependency chains are impactful, etc.

Since OP didn't answer, it's probably multiplying terms by zero to mask them out.

You don't need to multiply by zero; there are comparison operations which will generate a mask value which can then be used to select the appropriate value (`vsel` for altivec, `_mm_blend_ps` for sse4, or a combination of `_mm_and_ps` / `_mm_andnot_ps` / `_mm_or_ps` for ssse3 and earlier)

At least on Xbox 360 / Cell, high performance number crunching code would often compute more than needed (ie: both the if-case and else-case) and then use a branchless select to pick the right result. It may seem like a waste but it was faster than the combination of branch misprediction as well as shuffling values from one register file to another to be able to do scalar comparisons.

Then they would have said "masking" instead of "folding"

Thanks for mentioning masking though, in case anyone thought we didn't already know about that. ;-)

> `_mm_blend_ps` for sse4

That instruction uses a mask provided at compile time; it encodes the mask as a part of the instruction. SSE 4 set has a similar one, `_mm_blendv_ps`, which does take the mask from another vector register.

Good catch! Thanks, I'll correct it.

(edit: oops, can't fix it, it's been too long since I first wrote the comment)

Reply on news.ycombinator.com