5 ms·

I read it and I still don't get it, can someone (re-)explain what the presence of the print() is doing that is helpful for branch prediction (or any other aspec

I read it and I still don't get it, can someone (re-)explain what the presence of the print() is doing that is helpful for branch prediction (or any other aspect of the CPU)? Update: It seems to be the conditional move, see https://news.ycombinator.com/item?id=37245325 https://news.ycombinator.com/item?id=37245325

trolan 3y ago
I'm in school, so this may be oversimplified, but if the processor/assembly code is predicting the next result, it gets the result faster. The processor only does this prediction with conditional branches. The extra if for printing or finding the min invoke the prediction with the accuracies stated.
- dataflow 3y ago
  > The processor only does this prediction with conditional branches This sounds... wrong? Unless ARM64 is designed in an absurd way? I'd love to see the full disassembly; something seems funny here. If it was x86 I would say it's a conditional move causing this, but I don't know what's going on on ARM.
  - fmstephe 3y ago
    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.
- tallanvor 3y ago
  No, this is not true. There is branch prediction around the length of loops. This is a case where the processor is not able to accurately predict how long it needs to stay in the loop. The BLT instruction changes the prediction model, causing the processor to be more likely to assume the loop will continue. Honestly, though, worrying about this level of optimization is generally silly. If you're looping through an array often enough that optimizing the code this way is worth your time, you should use a data structure that automatically maintains the max (and min) values for fast retrieval.
Calavar 3y ago
I read it three or four times. It's never explained. If the print("lol") version has a branch-less-than, what does the regular version have? It must either be a branch or a conditional move, but we aren't shown that part of the assembly. You can't reach any conclusions about why one version is faster if you don't know what you're comparing to.
EspressoGPT 3y ago
As to branch prediction, for anyone interested: https://stackoverflow.com/a/11227902 https://stackoverflow.com/a/11227902
kevincox 3y ago
The high-level view is that adding code that never gets executed causes the compiler to emit code that the CPU predicts better. IDK if this is the compiler assuming that the `print()` call is cold or the branch predictor getting luckier by chance but basically this tickles the CPU in the right way to get better performance. It seems that this is mostly luck in a strange situation. And of course if you ever hit the `print()` it will be way slower than not. You can probably do better by adding something like a `__builtin_expect(...)` intrinsic in the right place to be more explicit about what the goal is here.

trolan 3y ago

I'm in school, so this may be oversimplified, but if the processor/assembly code is predicting the next result, it gets the result faster. The processor only does this prediction with conditional branches. The extra if for printing or finding the min invoke the prediction with the accuracies stated.

dataflow 3y ago
> The processor only does this prediction with conditional branches This sounds... wrong? Unless ARM64 is designed in an absurd way? I'd love to see the full disassembly; something seems funny here. If it was x86 I would say it's a conditional move causing this, but I don't know what's going on on ARM.
- fmstephe 3y ago
  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.
tallanvor 3y ago
No, this is not true. There is branch prediction around the length of loops. This is a case where the processor is not able to accurately predict how long it needs to stay in the loop. The BLT instruction changes the prediction model, causing the processor to be more likely to assume the loop will continue. Honestly, though, worrying about this level of optimization is generally silly. If you're looping through an array often enough that optimizing the code this way is worth your time, you should use a data structure that automatically maintains the max (and min) values for fast retrieval.

Calavar 3y ago

I read it three or four times. It's never explained. If the print("lol") version has a branch-less-than, what does the regular version have? It must either be a branch or a conditional move, but we aren't shown that part of the assembly. You can't reach any conclusions about why one version is faster if you don't know what you're comparing to.

EspressoGPT 3y ago

As to branch prediction, for anyone interested: https://stackoverflow.com/a/11227902 https://stackoverflow.com/a/11227902

kevincox 3y ago

The high-level view is that adding code that never gets executed causes the compiler to emit code that the CPU predicts better. IDK if this is the compiler assuming that the `print()` call is cold or the branch predictor getting luckier by chance but basically this tickles the CPU in the right way to get better performance. It seems that this is mostly luck in a strange situation. And of course if you ever hit the `print()` it will be way slower than not. You can probably do better by adding something like a `__builtin_expect(...)` intrinsic in the right place to be more explicit about what the goal is here.