4 ms·

Would using compiler intrinsics instead of raw assembler have any benefits here, such as being applicable to more architectures?

dragontamer 5y ago
Well, ideally, compilers should be compiling into CMOV vs Branching decisions much better. I'm shocked, but not that shocked (https://tenor.com/view/shocked-gif-5787388 https://tenor.com/view/shocked-gif-5787388), that compilers today still are weaker than a dedicated raw-assembly programmer in these kinds of microarchitectural decisions. Even with what should be normal 64-bit code with compilers that have very good modeling of throughputs / latencies per instruction. --------- I'm now more curious as to which compilers can turn the raw C-code into a cmov and which compilers turn the code into the less efficient form (I assume branching??)
- CyberShadow 5y ago
  Using CMOV vs. branching seems like a strategic decision which does make sense to fall under the programmer's decision making, as there is a trade-off of always calculating a value which may be unused vs. the cost of the conditional branch.
  - danachow 5y ago
    > as there is a trade-off of always calculating a value which may be unused vs. the cost of the conditional branch. I don’t really understand the point you’re trying to make. Figuring out if a value is unused is most definitely the purview of an optimizer. Also, the “calculating a value” isn’t really the trade off being made between cmov and branching.
    - CyberShadow 5y ago
      > I don’t really understand the point you’re trying to make. Figuring out if a value is unused is most definitely the purview of an optimizer. If the conditional move doesn't happen, then the source (insofar as the move is concerned) is unused. Consider this pseudocode: int value = some_nontrivial_function_with_no_side_effects(); if (condition) *target = value; Note that the function can be as simple as a memory read. The compiler could compile this in two ways: 1. Observing that the function's result is used only if condition is true, move the function call inside the if block. 2. Always call the function, as in the source code, but compile the if block to a conditional move. In such situations, it would make sense to allow programmers to indicate the desired strategy to the compiler. I suppose CPUs might elide calculating the value even with a conditional move if they can predict the condition is [likely to be] false; I don't know how true that is in practice. > Also, the “calculating a value” isn’t really the trade off being made between cmov and branching. Depending on the situation and interpretation of terms, I also agree.
      - danachow 5y ago
        > In such situations, it would make sense to allow programmers to indicate the desired strategy to the compiler. If the function truly has no side effects then why would the programmer care which strategy was used other than cost? This is just an optimization that can be mechanistically applied. And if it does have side effects then the two constructs are not equivalent - one would just put the function call inside the conditional.
        adgjlsfhk1 5y ago
        the problem is that without pgo, the compiler can't know the odds that a condition will be true.
- brigade 5y ago
  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.
- ncmncm 5y ago
  Correctly-predicted branching is better; but if the branch would have been mis-predicted, cmov is better. The compiler has no idea which will happen at runtime. Gcc will never under any circumstances generate two cmov instructions in a basic block, even when you definitely want that. Clang will. [Edit: I am wrong. Gcc can do more than one cmov in a basic block. Just not when I was trying it!] In principle, profile-guided optimization could help, if the instrumented run is representative of production behavior. In my tests it did not affect the cmov/branch choice. Neither did the "% expected" intrinsic. Either of those could change in any release. The Zstd and Lz4 decoders make very effective use of cmov. They should be your model.
  - mmozeiko 5y ago
    Here are two cmov's with gcc: https://godbolt.org/z/j9bcv639c https://godbolt.org/z/j9bcv639c
    - tssva 5y ago
      I'm not a programmer by profession and barely one by hobby. I know nothing about compiler internals but looking at the definition of a basic block from Wikipedia, "In compiler construction, a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit." it seems that the ternary operators in "return (x ? a : b) + (y ? c : d);" although part of the same programming block would be distinct compiler basic blocks.
      - dragontamer 5y ago
        Basic blocks are how compilers "conceptualize" our code and start thinking about optimization. Frankly, my recommendation to you is to ignore that stuff. You need like 3 or 4 years of school to reach that level. You should have studied easier graph optimization problems (ex: Finite Automatia) first, before dealing with code-optimization. The school curriculum is typically Programming 101 -> Data Structures -> Algorithms -> Finite Automata (aka: Regex) -> Pushdown Automata (aka: context-free grammars) -> Turing Machines (aka: general purpose code) -> Compilers (which use Finite Automata, Pushdown Automata, and Turing Machines simultaneously). Basic Blocks are the graph structure that compilers use to think about code. Its a lot of graph-theory built up on a lot of language theory. ------ That being said: if you're actually interested in this stuff, then feel free to explore. But just beware, you've stumbled upon a very complex subject that is easily 4th year undergrad or even graduate-school level. With enough effort, you'll understand things. But this is no subject for beginners to go around exploring by themselves. ------- That being said, I want to encourage you to explore the subject anyway. Just explore the subject with awareness that there's a lot to understand here. If you want to skip the 3ish years of elementary data-structures / comp. sci theory... I suggest starting with Static Single Assignment and working forward from here. https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form

dragontamer 5y ago

Well, ideally, compilers should be compiling into CMOV vs Branching decisions much better. I'm shocked, but not that shocked (https://tenor.com/view/shocked-gif-5787388 https://tenor.com/view/shocked-gif-5787388), that compilers today still are weaker than a dedicated raw-assembly programmer in these kinds of microarchitectural decisions. Even with what should be normal 64-bit code with compilers that have very good modeling of throughputs / latencies per instruction. --------- I'm now more curious as to which compilers can turn the raw C-code into a cmov and which compilers turn the code into the less efficient form (I assume branching??)

CyberShadow 5y ago
Using CMOV vs. branching seems like a strategic decision which does make sense to fall under the programmer's decision making, as there is a trade-off of always calculating a value which may be unused vs. the cost of the conditional branch.
- danachow 5y ago
  > as there is a trade-off of always calculating a value which may be unused vs. the cost of the conditional branch. I don’t really understand the point you’re trying to make. Figuring out if a value is unused is most definitely the purview of an optimizer. Also, the “calculating a value” isn’t really the trade off being made between cmov and branching.
  - CyberShadow 5y ago
    > I don’t really understand the point you’re trying to make. Figuring out if a value is unused is most definitely the purview of an optimizer. If the conditional move doesn't happen, then the source (insofar as the move is concerned) is unused. Consider this pseudocode: int value = some_nontrivial_function_with_no_side_effects(); if (condition) *target = value; Note that the function can be as simple as a memory read. The compiler could compile this in two ways: 1. Observing that the function's result is used only if condition is true, move the function call inside the if block. 2. Always call the function, as in the source code, but compile the if block to a conditional move. In such situations, it would make sense to allow programmers to indicate the desired strategy to the compiler. I suppose CPUs might elide calculating the value even with a conditional move if they can predict the condition is [likely to be] false; I don't know how true that is in practice. > Also, the “calculating a value” isn’t really the trade off being made between cmov and branching. Depending on the situation and interpretation of terms, I also agree.
    - danachow 5y ago
      > In such situations, it would make sense to allow programmers to indicate the desired strategy to the compiler. If the function truly has no side effects then why would the programmer care which strategy was used other than cost? This is just an optimization that can be mechanistically applied. And if it does have side effects then the two constructs are not equivalent - one would just put the function call inside the conditional.
      - adgjlsfhk1 5y ago
        the problem is that without pgo, the compiler can't know the odds that a condition will be true.
brigade 5y ago
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.
ncmncm 5y ago
Correctly-predicted branching is better; but if the branch would have been mis-predicted, cmov is better. The compiler has no idea which will happen at runtime. Gcc will never under any circumstances generate two cmov instructions in a basic block, even when you definitely want that. Clang will. [Edit: I am wrong. Gcc can do more than one cmov in a basic block. Just not when I was trying it!] In principle, profile-guided optimization could help, if the instrumented run is representative of production behavior. In my tests it did not affect the cmov/branch choice. Neither did the "% expected" intrinsic. Either of those could change in any release. The Zstd and Lz4 decoders make very effective use of cmov. They should be your model.
- mmozeiko 5y ago
  Here are two cmov's with gcc: https://godbolt.org/z/j9bcv639c https://godbolt.org/z/j9bcv639c
  - tssva 5y ago
    I'm not a programmer by profession and barely one by hobby. I know nothing about compiler internals but looking at the definition of a basic block from Wikipedia, "In compiler construction, a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit." it seems that the ternary operators in "return (x ? a : b) + (y ? c : d);" although part of the same programming block would be distinct compiler basic blocks.
    - dragontamer 5y ago
      Basic blocks are how compilers "conceptualize" our code and start thinking about optimization. Frankly, my recommendation to you is to ignore that stuff. You need like 3 or 4 years of school to reach that level. You should have studied easier graph optimization problems (ex: Finite Automatia) first, before dealing with code-optimization. The school curriculum is typically Programming 101 -> Data Structures -> Algorithms -> Finite Automata (aka: Regex) -> Pushdown Automata (aka: context-free grammars) -> Turing Machines (aka: general purpose code) -> Compilers (which use Finite Automata, Pushdown Automata, and Turing Machines simultaneously). Basic Blocks are the graph structure that compilers use to think about code. Its a lot of graph-theory built up on a lot of language theory. ------ That being said: if you're actually interested in this stuff, then feel free to explore. But just beware, you've stumbled upon a very complex subject that is easily 4th year undergrad or even graduate-school level. With enough effort, you'll understand things. But this is no subject for beginners to go around exploring by themselves. ------- That being said, I want to encourage you to explore the subject anyway. Just explore the subject with awareness that there's a lot to understand here. If you want to skip the 3ish years of elementary data-structures / comp. sci theory... I suggest starting with Static Single Assignment and working forward from here. https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form