3 ms·
A detailed exploration of this sort of optimization https://cantrip.org/sortfast.html https://cantrip.org/sortfast.html It seems like the code presented could
by ncmncm 5y ago
A detailed exploration of this sort of optimization
https://cantrip.org/sortfast.html https://cantrip.org/sortfast.html
It seems like the code presented could be improved further, something like:
while ((pos1 < size1) & (pos2 < size2)) {
v1 = input1[pos1];
v2 = input2[pos2];
bool less = v1 <= v2;
output_buffer[pos++] = less ? v1 : v2;
pos1 += less, pos2 += (1-less);
}
This is particularly likely in Gcc, which will not generate more than one CMOV instruction in a basic block.
(Note: I did not check this in Godbolt. It probably needs some changes, such as s/(1-less)/(!less)/.) Where the compiler refuses to generate CMOV, such as when building without -march=native, something like
output_buffer[pos++] = (-less & v1) | ((less-1) & v2);
can be better than nothing. Again, maybe s/(less-1)/-!less/.
Always benchmark! There are numerous surprises in this area.