4 ms·
It's useful in the compiler. For instance one optimization I haven't seen but would like to is going from if( value1 < 0 || value2 < 0 || value3 < 0 ) { to
by monocasa 7y ago
It's useful in the compiler. For instance one optimization I haven't seen but would like to is going from
if( value1 < 0 || value2 < 0 || value3 < 0 ) {
to
temp = value1 | value2 | value3;
if( temp < 0 ) {
Taking a sort of hardware, Boolean logic view makes this possible, as VHDL generally does this when synthesed.
- thaumasiotes 7y agoThat optimization fudges the difference between boolean or (comparing truth values) and bitwise or. It happens to work under the safe assumption that value1, value2, and value3 use sign bits (as all two's-complement integers do), but logically it's a disaster.
- Thorrez 7y agomonocasa isn't saying this should be in source code, but rather the compiler should create machine code that does this. Compilers know the types, so they will know whether they're signed (if they're not signed, then < 0 can be optimized out as impossible). Compilers have no goal of creating assembly that would look good in source code.
- adrian17 7y agoIt seems like Clang is capable of doing this optimization: > https://godbolt.org/z/oCQNbq https://godbolt.org/z/oCQNbq
- monocasa 7y agoNeat! It didn't a few years ago. This is most of the inner loop of a barycentric coordinate rasterizer, so I was pretty concerned about micro-optimizations when I was checking.
- ospr3y 7y agoAs a compiler writer I can tell you that this is a complex optimisation with very limited use. N.B. the || (logical or) operator is an "early out" operator whereas the | (binary or) operator is NOT The compiler would need to look for special cases of value1, value2 and value3... such as: are any of them volatile, perhaps one refers to a memory mapped I/O device, perhaps one if actually a function call, or array dereference, or pointer dereference, what about value1 being a "char" which needs to be promoted before it can be or'd, what about any of the "values" being a constant < 0 which would short circuit the "if" statement and remove the need for any tests. As I said, this is not as simple as it first appears.
- FullyFunctional 7y agoNote, if the three comparisons are sufficiently predicable, then your transformation would be _less_ efficient than the simple branches. A predicable branch is almost free in a modern processor.
- ncmncm 7y agoThree comparison/branch pairs are not free. Clang will optimize bool swap_if(bool c, int& a, int& b) { int ta = a, tb = b; a = (-c & tb)|((c-1) & ta); b = (-c & ta)|((c-1) & tb); return c; } into cmov instructions. Used in a quicksort partition loop as l += swap_if( *r <= pv, *l, *r); It makes quicksort fully 2x as fast as the usual branch.
- FullyFunctional 7y agoQuicksort comparisons are obviously not predictable