4 ms·

It's interesting that you say conditional move here. I am confused by this behaviour, and although I definitely don't know what the answer is here; the non-lol

It's interesting that you say conditional move here. I am confused by this behaviour, and although I definitely don't know what the answer is here; the non-lol version does have a CSEL (https://developer.arm.com/documentation/dui0802/b/CSEL https://developer.arm.com/documentation/dui0802/b/CSEL) which is totally missing from the lol version. Non-lol https://godbolt.org/z/ds1raTYc9 https://godbolt.org/z/ds1raTYc9 lol https://godbolt.org/z/c3afrb6bG https://godbolt.org/z/c3afrb6bG

dataflow 3y ago
Ah there you go, that's the conditional move on ARM. Yeah, those are slow.
- fmstephe 3y ago
  Yeah, after reading the blog post I felt reasonably confident that this is a compiler bug (in terms of perf). Hopefully someone with a deeper understanding can verify or discredit this here. I'm curious to see the fix for this (I assume it will generate a fix).
  - dataflow 3y ago
    Confused, why do you think this is a compiler bug? You should definitely expect a predictable branch to be faster than a conditional move, and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it).
    - littlestymaar 3y ago
      > and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it). Would you mind expanding? If the conditional move isn't needed, and given that it's costly in terms of perfs, how is that “totally sensible” to have one here?
      - dataflow 3y ago
        The performance of branches is data-dependent. The performance of conditional moves is data-independent. In this case the branches are predictable, so they perform better here. In general, though, the compiler has no idea whether that's the case, so it makes sense to insert a conditional move to avoid branch misprediction penalties.
        fmstephe 3y ago
        This is a very good answer. Thanks.
        mcv 3y ago
        But still, why the difference? With or without the "lol", the data dependence is identical, the predictability is identical. Yet with the "lol" it optimises differently. My best guess is that it's because of the added cost to the other branch: printing is expensive, so the compiler really doesn't want to do that, and would prefer to incorrectly predict not-printing than to incorrectly predict printing. If that tradeoff is what causes the difference in behaviour here, then I understand. But I don't like it, because it's ridiculous and we shouldn't have to con the compiler into doing what's right. If we're going to have to do this, I'd rather have the language provide a way for us to make explicit what we expect here.
        anonymoushn 3y ago
        When compiling code like if a > b b = a continue else continue you can replace the entire if-else with a cmov. but if there is a function call in one of the prongs and not in the other, you cannot.
        mcv 3y ago
        Ah, so it's the function call (which could just as easily have been something other than print), that forces the compiler to use a normally-less-optimal branch rather than the normally-more-optimal cmov. Only in this particular use case, cmov is actually less optimal, but the compiler doesn't know that.
  - tylerhou 3y ago
    I don't know if I would classify it as a bug, but definitely a heuristic that could use tuning. At least (at a high level) in LLVM, branches and cmovs are represented with the exact same construct, and one of the codegen passes looks at the condition and the two sides and heuristically determines whether to emit a branch or a cmov. I don't know how Go codegen works, but I assume they do something similar.
- tylerhou 3y ago
  "Conditional move is slow" is not the right takeaway. (In fact, conditional move can be much /faster/ than a branch in certain circumstances (e.g. hard-to-predict branches, like binary search).) The reason why this code is slow is because the conditional move is on the critical path for resolving a loop-carried data dependency. In other words, to execute the assignment `maxV = (v if (v > maxV) else maxV)`, the CPU has to test v > maxV. But in order to make this test, the CPU has to wait until the conditional move in the previous loop iteration finishes (to know what the new value of maxV is). So the overall execution time of the loop is worse, because each iteration depends on the previous iteration. (This is analogous to why traversing a linked list is slower than an array.) However, for the branch version, there is no data dependency on the previous loop, so the CPU really can (speculatively) execute multiple loop iterations in parallel. The the next loop iteration can start before the previous finishes. And with the large reorder buffers on modern CPUs, maybe up to 4-8 loop iterations can execute in parallel! On the other hand, conditional moves would be much faster for a loop like: bigs := make([]int, len(numsA)) for idx, v : range numsA { if numsA[idx] > numsB[idx] { bigs[idx] = numsA[idx] } else { bigs[idx] = numsB[idx] } } There is no loop-carried data dependency, so the conditional moves can resolve in parallel. The above code with a conditional move is likely to be much faster than code with an equivalent branch. (And even if branches are perfectly predicted, the conditional move version will only be slightly slower, not 2X slower.)
  - fmstephe 3y ago
    So would you say in the general case, i.e. the compiler obviously doesn't know how predictable a branch may be, using conditional move is a poor choice when writing to an address which is repeatedly written to inside the loop? What I am trying to get a feel for, is whether this represents a bad choice of assembly in general for this kind of loop.
    - tylerhou 3y ago
      Nit: If a variable/object is only being written, that’s fine. There is a data dependency here because there is a read after a write. I don’t have enough compiler knowledge to be able to definitively answer your question, but I think it would be a reasonable heuristic to favor emitting a branch over a cmov in cases where the cmov participates in a loop-carried data dependency. The other advantage of emitting a branch is that branch prediction can better adapt to runtime conditions. Branch prediction tends to struggle when data is perfectly random, but most data is not. So in general it’s also reasonable for compilers to default to emitting branches.

dataflow 3y ago

Ah there you go, that's the conditional move on ARM. Yeah, those are slow.

fmstephe 3y ago
Yeah, after reading the blog post I felt reasonably confident that this is a compiler bug (in terms of perf). Hopefully someone with a deeper understanding can verify or discredit this here. I'm curious to see the fix for this (I assume it will generate a fix).
- dataflow 3y ago
  Confused, why do you think this is a compiler bug? You should definitely expect a predictable branch to be faster than a conditional move, and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it).
  - littlestymaar 3y ago
    > and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it). Would you mind expanding? If the conditional move isn't needed, and given that it's costly in terms of perfs, how is that “totally sensible” to have one here?
    - dataflow 3y ago
      The performance of branches is data-dependent. The performance of conditional moves is data-independent. In this case the branches are predictable, so they perform better here. In general, though, the compiler has no idea whether that's the case, so it makes sense to insert a conditional move to avoid branch misprediction penalties.
      - fmstephe 3y ago
        This is a very good answer. Thanks.
      - mcv 3y ago
        But still, why the difference? With or without the "lol", the data dependence is identical, the predictability is identical. Yet with the "lol" it optimises differently. My best guess is that it's because of the added cost to the other branch: printing is expensive, so the compiler really doesn't want to do that, and would prefer to incorrectly predict not-printing than to incorrectly predict printing. If that tradeoff is what causes the difference in behaviour here, then I understand. But I don't like it, because it's ridiculous and we shouldn't have to con the compiler into doing what's right. If we're going to have to do this, I'd rather have the language provide a way for us to make explicit what we expect here.
        anonymoushn 3y ago
        When compiling code like if a > b b = a continue else continue you can replace the entire if-else with a cmov. but if there is a function call in one of the prongs and not in the other, you cannot.
        mcv 3y ago
        Ah, so it's the function call (which could just as easily have been something other than print), that forces the compiler to use a normally-less-optimal branch rather than the normally-more-optimal cmov. Only in this particular use case, cmov is actually less optimal, but the compiler doesn't know that.
- tylerhou 3y ago
  I don't know if I would classify it as a bug, but definitely a heuristic that could use tuning. At least (at a high level) in LLVM, branches and cmovs are represented with the exact same construct, and one of the codegen passes looks at the condition and the two sides and heuristically determines whether to emit a branch or a cmov. I don't know how Go codegen works, but I assume they do something similar.
tylerhou 3y ago
"Conditional move is slow" is not the right takeaway. (In fact, conditional move can be much /faster/ than a branch in certain circumstances (e.g. hard-to-predict branches, like binary search).) The reason why this code is slow is because the conditional move is on the critical path for resolving a loop-carried data dependency. In other words, to execute the assignment `maxV = (v if (v > maxV) else maxV)`, the CPU has to test v > maxV. But in order to make this test, the CPU has to wait until the conditional move in the previous loop iteration finishes (to know what the new value of maxV is). So the overall execution time of the loop is worse, because each iteration depends on the previous iteration. (This is analogous to why traversing a linked list is slower than an array.) However, for the branch version, there is no data dependency on the previous loop, so the CPU really can (speculatively) execute multiple loop iterations in parallel. The the next loop iteration can start before the previous finishes. And with the large reorder buffers on modern CPUs, maybe up to 4-8 loop iterations can execute in parallel! On the other hand, conditional moves would be much faster for a loop like: bigs := make([]int, len(numsA)) for idx, v : range numsA { if numsA[idx] > numsB[idx] { bigs[idx] = numsA[idx] } else { bigs[idx] = numsB[idx] } } There is no loop-carried data dependency, so the conditional moves can resolve in parallel. The above code with a conditional move is likely to be much faster than code with an equivalent branch. (And even if branches are perfectly predicted, the conditional move version will only be slightly slower, not 2X slower.)
- fmstephe 3y ago
  So would you say in the general case, i.e. the compiler obviously doesn't know how predictable a branch may be, using conditional move is a poor choice when writing to an address which is repeatedly written to inside the loop? What I am trying to get a feel for, is whether this represents a bad choice of assembly in general for this kind of loop.
  - tylerhou 3y ago
    Nit: If a variable/object is only being written, that’s fine. There is a data dependency here because there is a read after a write. I don’t have enough compiler knowledge to be able to definitively answer your question, but I think it would be a reasonable heuristic to favor emitting a branch over a cmov in cases where the cmov participates in a loop-carried data dependency. The other advantage of emitting a branch is that branch prediction can better adapt to runtime conditions. Branch prediction tends to struggle when data is perfectly random, but most data is not. So in general it’s also reasonable for compilers to default to emitting branches.