Seemingly Nasty Branch Mispredict in Match Finding Loop

Hey, so if you look at the main hashmap finding loop there is this code:

if ( ((tableType != byU16) || (LZ4_DISTANCE_MAX < LZ4_DISTANCE_ABSOLUTE_MAX))
                  && (matchIndex+LZ4_DISTANCE_MAX < current)) {
                    continue;
} /* too far */
if (LZ4_read32(match) == LZ4_read32(ip)) {
...

This looks quite fine at first, but if you think about the code that the compiler will generate it looks something like: if distance > 64KB, goto start_of_loop; (branch mispredict) elif match == good, break (branch mispredict) else continue (no branch mispredict)

From the CPU's perspective the distance check failing is a branch mispredict, finding a match is a branch mispredict, continuing to find matches is fine, no mispredict. The thing is you can refactor this code so that distance checks failing aren't actually branch mispredicts. If you do:

int is_outside_window = ((tableType != byU16) || (LZ4_DISTANCE_MAX < LZ4_DISTANCE_ABSOLUTE_MAX))
                  && (matchIndex+LZ4_DISTANCE_MAX < current);

if (!is_outside_window & LZ4_read32(match) == LZ4_read32(ip)) {
...

Then the assembly starts to look like: if distance <= 64KB and match == good, break (branch mispredict) else continue (no branch mispredict)

Now, there are no longer branch mispredicts for matches not being in the sliding window. This is not very intuitive to see, but the results are quite telling. This seems to boost encoding performance on my CPU by roughly ~3%, because from the CPU's perspective now every distance check failed is actually no longer a branch mispredict.

I hope you consider this refactor as well Yann :)