2 pointsby rlasse4 hours ago1 comment
  • rlasse4 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));