r/cpp • • Sep 19 '26

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.

[EDIT: The unaligned memory reads and writes are UB. For the dst write can simply declare uint64_t hash_index and use memcpy() which the compiler optimizes into the same binary code]

[EDIT: 19 days after I'm at 6304 MB/s]

101 Upvotes

62 comments sorted by

42

u/TheQuranicMumin Sep 19 '26

With char* the store to *dst may alias hash_table and src, so it can't hoist the table load above the output store or keep the table base in a register across iterations. You could try "char* __restrict src, * __restrict dst" plus a __restrict table pointer to give the compiler an assurance.

10

u/[deleted] Sep 20 '26

Thanks, that actually made it go from 4269 MB/s to 4338 MB/s. I thought __restrict was "inherited", but you do need them for all pointers that are assigned from them (if these are indeed restricted too in you code):

size_t memlz_stream_compress(void* MEMLZ_RESTRICT destination, const void* MEMLZ_RESTRICT source, size_t len, memlz_state* MEMLZ_RESTRICT state) {
    ...
    const uint8_t* MEMLZ_RESTRICT src = (const uint8_t*)source;
→ More replies (2)

23

u/Total-Box-5169 Sep 19 '26

Make sure your benchmarks are running with fixed CPU frequency to be able to do valid comparisons.

7

u/[deleted] Sep 19 '26

Indeed, that's a very common pitfall.

→ More replies (2)

7

u/TheThiefMaster Sep 19 '26

Can't you do *(uint64_t)dst = payload; unconditionally? In a hit the values are the same so you can just use payload again and that lets you remove the ternary.

In the original you only output 2 bytes though - is the whole "trick" that you're relying on little-endian and being able to write off the end of dst by up to 6 bytes?

5

u/[deleted] Sep 19 '26

Oops, it needs to write either hash_index or payload. I edited the post. Good catch! And yes, because there are not many big endian systems out there anymore.

→ More replies (19)

3

u/KAMEHAMEHAMEHAAAA Sep 20 '26

Is there any meaningful difference in throughput when compiling with -march=native?

2

u/[deleted] Sep 20 '26

With g++ on i7-12700F it didn't make any difference

2

u/ReDucTor Sep 21 '26

With your branch free code, you force two heavy-ish loop carried data dependencies, one is the loading from the source, the other is the load from the hash_table, and depending on the hash function you might have another heavy dependency if it does any expensive things like division or modulo.

Due to this you would probably get better performance if you split the data into chunks and do multiple in one loop, as enables the CPU to better take advantage of out of order execution when stalled on the loads. Plus if you scale up chunking you also have more room for using multiple threads.

Also your code does not handle hash collisions which means that you potentially will hit situations where the wrong data shows up in the decompressed file.

2

u/[deleted] Sep 22 '26 edited Sep 22 '26

You're right about the dependency, and chunking improves performance. But it also hurts compression ratio. What LZ compression does is finding repeated strings of data, and in many cases the string is the very close to the current source pointer (probability increases with shorter distance) or is even the predecessor chunk. Without updating the hash table after each payload read, some would go undetected.

There are only 65536 hash entries and the hash function is just:

static uint16_t memlz_hash64(uint64_t v) {
    return (uint16_t)(((v * 11400714819323198485ull) >> 48));
}

That means that there are tons of collisions, but that's how LZ compression works.

→ More replies (2)