Lz4: Bitwise & instead of logical && in LZ4HC_FindLongerMatch

[YuryChaikou]

lib\lz4hc.c:1270
Should be && instead of &

if (favorDecSpeed) {
    if ((matchLength>18) & (matchLength<=36)) matchLength=18;   /* favor shortcut */
}

[felixhandte]

Hi @YuryChaikou, what makes you think it should be && instead of &?

[YuryChaikou]

It's a logical condition where we check if matchLength fits into (18;36] range which is true when both left AND right parts are true.

[felixhandte]

Yes. But since the left and right arguments are constrained to 0 or 1, & also performs exactly the same test, producing exactly the same result over all inputs. So it's not incorrect. And in fact, not only is it not incorrect, it's actually desirable.

The important difference is how they handle their arguments. && is lazy, which means it doesn't evaluate the second argument if the first evaluates to false. This potentially introduces an additional branch. In contrast, & always evaluates both arguments. You can see the difference in generated code in this example: https://godbolt.org/z/BTm6hi. The logical version has two branches, while the bitwise has one. Branch (mis)prediction is one of the leading enemies of performance, so every branch we can avoid is a significant speed win. (Of course, if you ask the compiler to optimize it, it generates the same instructions either way, since in this case it can prove evaluation of the second argument is side-effect free, and you actually end up with no branches at all--it uses a conditional move instead).

Nonetheless, hopefully that explains why this usage is intentional.

[hsiangkao]

Yeah, it seems already explain something similar before, yet I'm not sure whether e.g the following is an potential optimization...
if ((unsigned int)(matchLength - 19) <= 17) matchLength=18; /* favor shortcut */

(p.s. if it seems a common pattern, which could introduce some isbetween(x,y) marco for this, actually I used it in my own projects for years...)

Thanks,
Gao Xiang

[felixhandte]

Yeah. In fact, if you pass -O3 to the example I gave, that's exactly what the compiler emits.

[terrelln]

In this particular case, it is unlikely to matter if you use & or &&. Any differences are likely because of noise like alignment, or the compiler happens to pick a better implementation for one version than another.

When it matters more is when you do a memory access. Then condition && access cannot be optimized the same way as condition & access, because maybe the memory access is unsafe if the condition is false.