A clever branch free optimization

I'm the developer of memlz which is an extremely fast compression library.

We have `char* src, char* dst` for the source and destination buffers and `uint16_t flags` that we prepend bits to one at a time. The inner core looks something like this (pseudo code):

flags <<= 1;
uint64_t payload = ((uint64_t*)src)[i];
uint16_t hash_index = hash_function(payload);
if (hash_table[hash_index] == payload) {
flags |= 1;
*(uint16_t*)dst = (uint16_t)hash_index;
dst += sizeof(uint16_t);
}
else {
*(uint64_t*)dst = payload;
hash_table[hash_index] = payload;
dst += sizeof(uint64_t);
}

Depending on a hash comparison we need to output either 2 or 8 bytes, advance `dst` accordingly and prepend either a 1 or a 0 to `flags`.

Furthermore, at the end it's required that `hash_table[hash_index] == payload`, so we update `hash_table` in the false-case.

Let's benchmark it with 211 MB input so it's uncached:

memlz: 2744 MB/s

Now let's look at an amazing idea. The output to `*dst` can be rewritten with the ternary operator:

`*(uint64_t*)dst = hit ? hash_index : payload;`

That turns into a compare instruction (`cmp`) and a conditional move instruction (`cmove`) with no branching:

00007FF742A5A55B mov rax,r10
00007FF742A5A55E cmp rcx,r10
...
00007FF742A5A56D cmove rax,rdx
00007FF742A5A571 mov qword ptr [rdi],rax

The advancement of `dst` is also simple to make branchless, noting that `hit` will turn either 0 or 1:

uint64_t hit = (hash_table[hash_index] == payload);
dst += 8 - (hit * 6);

Now look at updating the `hash_table` where we update it to `payload` only if it differed from `payload`. What we can do is update it unconditionally at the end, and hope that the extra number of unnecessary writes to memory (where it just overwrites the same value) are not too expensive.

Final branch-free version:

uint64_t payload = ((uint64_t*)src)[i];
uint16_t hash_index = hash_function(payload);
flags <<= 1;
uint64_t hit = (hash_table[hash_index] == payload);
flags |= hit;
*(uint64_t*)dst = hit ? hash_index : payload;
hash_table[hash_index] = payload;
dst += 8 - (hit * 6);

Let's benchmark it:

memlz: 4269 MB/s

I had never believed such gains were possible because I had been micro-optimizing on this for weeks.

I later achieved 5070 MB/s. To put it in perspective, uncached memcpy runs at 14000 MB/s here and LZ4 - another popular fast compression library - at 718 MB/s.

https://redd.it/1wkuou2
@r_cpp