3 ms·
World's fastest compression library just doubled its speed
- rlasse 2mo agoI 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));