World's fastest compression library just doubled its speed

1 comments

• rlasse 4 hours ago 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));