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));