3 ms·

...It’s easy to see that the above loop can be implemented without conditional branches. The conditional swapping can be implemented by conditional moves and th

...It’s easy to see that the above loop can be implemented without conditional branches. The conditional swapping can be implemented by conditional moves and the conditional pointer increase could be implemented as a unconditional p += (*it < pivot) Does that really guarantee that it is branchless? Surely a compiler is free to turn that into a comparison and jump? Or, to put it another way, the compiler was also free to turn the original 'if/then' structure into branchless code using conditional instructions. My point is, surely neither version guarantees that the generated code is branchless, it's all still up to the compiler.

haberman 5y ago
> 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;
masklinn 5y ago
And IIRC compilers have been somewhat chilly about cmov because (iirc) it can’t be speculatively executed.
- ncmncm 5y ago
  It seems possible that Rust could make better progress than C++ on incorporating this optimization into its standard library because it does not allow programmed move constructors, so "knows" more about its types. This is not assured, because it needs other declarative features that might not be in the core language yet, and might not be on the road map. But running industrially important generic algorithms twice as fast as C++, automatically and without heroics, would be a Feather in Rust's Cap, and a Black Eye for C++. ("!!!!", as it were.) Or vice versa. Best would be if both got it, of course. At present, both languages need heroics. I don't know of any other language where there is a reasonable prospect of getting such an optimization implemented generically, but that doesn't mean there aren't any.
- tialaramex 5y ago
  CMOV is a win if the speculation won't work. HN regular Nathan Myers (ncmncm) wrote a proposal for C++ saying the compilers should offer a way to, in effect, signal that yeah, you really can't guess this one (thus, try CMOV).
  - gerbenst 5y ago
    The key point of this article (I'm the author) is that even if cmov would be like 50 cycle latency instruction and the penalty of a mispredicted branch is 0 (ie. after the cpu sees a branch is mispredicted it would immediately start executing the instructions from the correct branch), than cmov would still be faster on modern CPU's. Because in branchless quicksort, no matter how long it takes to figure out where the element has to go relative to the pivot it doesn't obstruct the CPU's ability in this algorithm to start working on the next element the next cycle.
  - masklinn 5y ago
    > Many vulnerabilities stem from accessing/modifying memory that should not be accessed/modified. So a complement to the likely/unlikely annotations?
userbinator 5y ago
It doesn't, but is intended to provide a strong hint to the compiler. A pre-386 one would probably turn the "comparison result in non-branching context" into a cmp/sbb/inc; 386+ could do that or use cmp/setcc depending on surrounding context, and in general a compiler could fold it even further. E.g. if pivot was in eax, it in ecx, and p in edi, that line might generate only two instructions: cmp [ecx], eax adc edi, 0 (Figuring out how the above works is left as an exercise for the reader.)
pdpi 5y ago
There’s two things at play here: what should the actual machine code do, and how do you get your program to compile to that machine code. This article is about algorithms, not compilers, and cares only about what the actual instructions are, so it’s better to treat it as if you have a compiler that will just do what you mean instead of trying to be clever (because in this instance that “compiler” is the reader). You still need to get your actual compiler to generate the right code, but that’s something to worry about later.

haberman 5y ago

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

masklinn 5y ago

And IIRC compilers have been somewhat chilly about cmov because (iirc) it can’t be speculatively executed.

ncmncm 5y ago
It seems possible that Rust could make better progress than C++ on incorporating this optimization into its standard library because it does not allow programmed move constructors, so "knows" more about its types. This is not assured, because it needs other declarative features that might not be in the core language yet, and might not be on the road map. But running industrially important generic algorithms twice as fast as C++, automatically and without heroics, would be a Feather in Rust's Cap, and a Black Eye for C++. ("!!!!", as it were.) Or vice versa. Best would be if both got it, of course. At present, both languages need heroics. I don't know of any other language where there is a reasonable prospect of getting such an optimization implemented generically, but that doesn't mean there aren't any.
tialaramex 5y ago
CMOV is a win if the speculation won't work. HN regular Nathan Myers (ncmncm) wrote a proposal for C++ saying the compilers should offer a way to, in effect, signal that yeah, you really can't guess this one (thus, try CMOV).
- gerbenst 5y ago
  The key point of this article (I'm the author) is that even if cmov would be like 50 cycle latency instruction and the penalty of a mispredicted branch is 0 (ie. after the cpu sees a branch is mispredicted it would immediately start executing the instructions from the correct branch), than cmov would still be faster on modern CPU's. Because in branchless quicksort, no matter how long it takes to figure out where the element has to go relative to the pivot it doesn't obstruct the CPU's ability in this algorithm to start working on the next element the next cycle.
- masklinn 5y ago
  > Many vulnerabilities stem from accessing/modifying memory that should not be accessed/modified. So a complement to the likely/unlikely annotations?

userbinator 5y ago

It doesn't, but is intended to provide a strong hint to the compiler. A pre-386 one would probably turn the "comparison result in non-branching context" into a cmp/sbb/inc; 386+ could do that or use cmp/setcc depending on surrounding context, and in general a compiler could fold it even further. E.g. if pivot was in eax, it in ecx, and p in edi, that line might generate only two instructions: cmp [ecx], eax adc edi, 0 (Figuring out how the above works is left as an exercise for the reader.)

pdpi 5y ago

There’s two things at play here: what should the actual machine code do, and how do you get your program to compile to that machine code. This article is about algorithms, not compilers, and cares only about what the actual instructions are, so it’s better to treat it as if you have a compiler that will just do what you mean instead of trying to be clever (because in this instance that “compiler” is the reader). You still need to get your actual compiler to generate the right code, but that’s something to worry about later.