> surely neither version guarantees that the generated code is branchless, it's all still up to the compiler.
That is true, and the article mentions that GCC did not want to generate branchless code in this case, and thus performed much worse. Only Clang reliably generated the branchless code, and thus Clang was used for all of the benchmarking.
> the compiler was also free to turn the original 'if/then' structure into branchless code using conditional instructions
If we were just talking about:
if (*it < pivot) p++;
then I would agree with you. Optimizing this into the branchless version is a relatively trivial operation:
p += (*it < pivot);
However the actual code was:
if (*it < pivot) {
std::swap(*it, *p); // Could be a self-swap
p++;
}
This std::swap() line performs two memory reads and a memory write, but only if the condition is true. Eliminating the branch in this case will cause these memory operations to happen unconditionally, which means the optimizer will actually be introducing extra memory operations. This is the opposite of what you generally expect an optimizer to do: if anything you usually want an optimizer to
reduce the number of memory operations being performed! The compiler would need to be extremely confident that this will somehow speed up the program overall, and it will also need to guarantee that none of these new loads/stores can possibly introduce memory errors (out-of-bounds reads or writes).
For these reasons, I don't expect real compilers to ever translate the example above into the equivalent branchless code, as given in Andrei's article:
auto x = *read;
auto smaller = -int(x < pivot);
auto delta = smaller & (read - first);
first[delta] = *first;
read[-delta] = x;
first -= smaller;