5 ms·

gcc and clang see the use of ternaries as a hint that they should use cmov, but it's obviously not guaranteed.

dragontamer 5y ago
I'm trying to grok the performance improvement here. The diff points to: + /* tmp = rc.code < rc_bound ? rc.range = rc_bound, ~0 : 0; */ \ + __asm__ ( \ + "cmpl %3, %2\n\t" \ + "cmovbl %3, %1\n\t" \ + "sbbl %0, %0" \ + : "=&r"(tmp), "+&r"(rc.range) \ + : "r"(rc.code), "r"(rc_bound) \ + ); \ This is the only use of assembly in this entire diff. That "tmp = rc.code < rc_bound ?..." statement looks like it'd probably be a cmov, at least I'd expect it to compile to cmov without much issue. However, this is some advanced "carry-flag manipulation" stuff going on here. I'm not sure if its the "cmov" per se that was advanced, as much as the sbbl statement (subtract borrow, the subtraction-analog to adc). sub %0, %0 is obviously "zero", but sbbl %0, %0 is "0xFFFFFFFF" if carry is 1. Its certainly a very well thought out bit of manual assembly language. The sbb is probably more important than the cmov (in that the compiler probably emits the cmov, but may not see the sbb????) ---------- The original code seems to be: https://github.com/COMBINE-lab/xz/blob/master/src/liblzma/rangecoder/range_decoder.h https://github.com/COMBINE-lab/xz/blob/master/src/liblzma/ra... #define rc_direct(dest, seq) \ do { \ rc_normalize(seq); \ rc.range >>= 1; \ rc.code -= rc.range; \ rc_bound = UINT32_C(0) - (rc.code >> 31); \ rc.code += rc.range & rc_bound; \ dest = (dest << 1) + (rc_bound + 1); \ } while (0) I don't know what its doing, but the cmov stuff is very, very different entirely. There doesn't seem to be a branch involved at all in this "rc_direct" inner-loop. Its not very clear to me how they saw this sequence of C, and the decided upon a cmov / sbb approach to do this equivalent work. Its clearly some kind of advanced thinking that no compiler would have gotten.
- brigade 5y ago
  It's replacing rc_bit not rc_direct (rc_direct is a fixed .5 probability), which just uses rc_bit_last, so original code is: #define rc_bit_last(prob, action0, action1, seq) \ do { \ rc_if_0(prob, seq) { \ rc_update_0(prob); \ action0; \ } else { \ rc_update_1(prob); \ action1; \ } \ } while (0) So it's merging the two sides of rc_update and cmov/sbb handle the difference. action0/action1 are generally blank, but rc_bit_matched makes the common action branchless as well.
  - dragontamer 5y ago
    Thanks for the info. Realizing that the two sides of the "if" statement are effectively stored as a 1-bit of information, and then using instructions to store that 1-bit into the carry flag, and then using cmovcc / sbbl instructions to manipulate that 1-bit of information is pretty advanced. I could imagine a compiler making use of all that information, but only maybe with some programmer assistance (IE: code in the right format for easier optimizing). Or you know... an assembly programmer who just outright explicitly writes that kind of assembly language.
    - brigade 5y ago
      Yeah, this sort of conversion is pretty common for the core of arithmetic/range decoders, and I definitely don't expect a compiler to be capable of the sort of transformations needed to convert the branchy form to branchless. Though I'd expect compilers to be at least 90% as good with the ternary equivalent to the asm, e.g.: tmp = code < bound ? ~0 : 0; range = code < bound ? bound : range; compiles tmp to xor -> setl -> neg (clang) or setge -> movzx -> sub (gcc) instead of sbb, but on arm64 they use just one csetm (clang) or csinv (gcc) which is basically optimal, and in all cases the comparison is reused for the cmov. https://godbolt.org/z/jPbo3qc1Y https://godbolt.org/z/jPbo3qc1Y

I'm trying to grok the performance improvement here. The diff points to: + /* tmp = rc.code < rc_bound ? rc.range = rc_bound, ~0 : 0; */ \ + __asm__ ( \ + "cmpl %3, %2\n\t" \ + "cmovbl %3, %1\n\t" \ + "sbbl %0, %0" \ + : "=&r"(tmp), "+&r"(rc.range) \ + : "r"(rc.code), "r"(rc_bound) \ + ); \ This is the only use of assembly in this entire diff. That "tmp = rc.code < rc_bound ?..." statement looks like it'd probably be a cmov, at least I'd expect it to compile to cmov without much issue. However, this is some advanced "carry-flag manipulation" stuff going on here. I'm not sure if its the "cmov" per se that was advanced, as much as the sbbl statement (subtract borrow, the subtraction-analog to adc). sub %0, %0 is obviously "zero", but sbbl %0, %0 is "0xFFFFFFFF" if carry is 1. Its certainly a very well thought out bit of manual assembly language. The sbb is probably more important than the cmov (in that the compiler probably emits the cmov, but may not see the sbb????) ---------- The original code seems to be: https://github.com/COMBINE-lab/xz/blob/master/src/liblzma/rangecoder/range_decoder.h https://github.com/COMBINE-lab/xz/blob/master/src/liblzma/ra... #define rc_direct(dest, seq) \ do { \ rc_normalize(seq); \ rc.range >>= 1; \ rc.code -= rc.range; \ rc_bound = UINT32_C(0) - (rc.code >> 31); \ rc.code += rc.range & rc_bound; \ dest = (dest << 1) + (rc_bound + 1); \ } while (0) I don't know what its doing, but the cmov stuff is very, very different entirely. There doesn't seem to be a branch involved at all in this "rc_direct" inner-loop. Its not very clear to me how they saw this sequence of C, and the decided upon a cmov / sbb approach to do this equivalent work. Its clearly some kind of advanced thinking that no compiler would have gotten.

brigade 5y ago
It's replacing rc_bit not rc_direct (rc_direct is a fixed .5 probability), which just uses rc_bit_last, so original code is: #define rc_bit_last(prob, action0, action1, seq) \ do { \ rc_if_0(prob, seq) { \ rc_update_0(prob); \ action0; \ } else { \ rc_update_1(prob); \ action1; \ } \ } while (0) So it's merging the two sides of rc_update and cmov/sbb handle the difference. action0/action1 are generally blank, but rc_bit_matched makes the common action branchless as well.
- dragontamer 5y ago
  Thanks for the info. Realizing that the two sides of the "if" statement are effectively stored as a 1-bit of information, and then using instructions to store that 1-bit into the carry flag, and then using cmovcc / sbbl instructions to manipulate that 1-bit of information is pretty advanced. I could imagine a compiler making use of all that information, but only maybe with some programmer assistance (IE: code in the right format for easier optimizing). Or you know... an assembly programmer who just outright explicitly writes that kind of assembly language.
  - brigade 5y ago
    Yeah, this sort of conversion is pretty common for the core of arithmetic/range decoders, and I definitely don't expect a compiler to be capable of the sort of transformations needed to convert the branchy form to branchless. Though I'd expect compilers to be at least 90% as good with the ternary equivalent to the asm, e.g.: tmp = code < bound ? ~0 : 0; range = code < bound ? bound : range; compiles tmp to xor -> setl -> neg (clang) or setge -> movzx -> sub (gcc) instead of sbb, but on arm64 they use just one csetm (clang) or csinv (gcc) which is basically optimal, and in all cases the comparison is reused for the cmov. https://godbolt.org/z/jPbo3qc1Y https://godbolt.org/z/jPbo3qc1Y