World's fastest compression library just doubled its speed

2 pointsposted 5 hours ago
by rlasse

1 Comments

rlasse

5 hours ago

I recently created the world's fastest compression library in C, and now I just almost doubled its speed by making it branchless.

The pseudocode shows how I advance the destination pointer with simple arithmetic, and how I select what to write there with a conditional move (that hopefully turns into a cmov instruction):

Before:

    if (hash == ((uint64_t*)src)[i]) {
     flags |= 1; \
     *(uint16_t*)dst = (uint16_t)hash;
     dst += 2;
    } else {
     hashtable[hash] = ((uint64_t*)src)[i];
     *(uint64_t*)dst = ((uint64_t*)src)[i];
     dst += sizeof(uint64_t);
    }
After:

    uint64_t val = *(uint64_t*)(src + idx * sizeof(uint64_t));
    uint64_t hit = (hash == val); // Turns 0 or 1
    flags |= (hit << shift);
    ...
    *(uint64_t*)dst = hit ? hash : val;
    hashtable[hash] = val;
    dst += sizeof(uint64_t) - (hit \* (sizeof(uint64_t) - 2));