5 ms·

The most important bit of this is in the conclusion: Before we conclude anything, we should remind ourselves of its limitations. The tests run were on comple

by dgl 2y ago

The most important bit of this is in the conclusion: Before we conclude anything, we should remind ourselves of its limitations. The tests run were on completely random data. Truly random data seldom occurs in real life. Linus famously ranted about CMOV in https://yarchive.net/comp/linux/cmov.html https://yarchive.net/comp/linux/cmov.html (2007, so potentially more modern architectures are better at some of this) and he says: if you KNOW the branch is totally unpredictable, cmov is often good for performance. But a compiler almost never knows that. As usual with optimizations like this you have to benchmark and even then if your sample isn't representative it might not mean much.

tialaramex 2y ago
You can see how dramatically the actual data changes sort performance in e.g. this (summary of the current unstable sort in Rust, ipnsort) https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md#robust https://github.com/Voultapher/sort-research-rs/blob/main/wri... Notice how random_s95 is worse (not by much, but it's there) than fully random. random_s95 is 95% sorted data, but 5% unsorted, simulating a common "sort, do stuff, append, repeat" pattern we see in a lot of software. In contrast the sorted cases are almost instant, and random_d20 (only 20 distinct values, chosen at random, but as a result the sorted output needs much fewer comparions) is very fast.
jnordwick 2y ago
When Linus made that comment cmov was like a 6 cycle latency. For the last decade it has been 1 cycle, and I don't think there is any scenario where cmov is now slower than a branch.
- haberman 2y ago
  The problem is not the 1 cycle latency, but the data dependency on both values. A correctly-predicted branch cuts the dependency on the value that is not used. I've definitely measured scenarios where cmov/branchless is slower than a branch for a given algorithm. Especially if the branchless version is doing a bit more work to avoid the branch.
  - unnah 2y ago
    Good point. It makes me wonder if modern out-of-order processors can skip performing unused computations altogether, if their result registers are overwritten by other data later (in program order).
    - ants_a 2y ago
      No, and it feels unlikely that they will either.
    - gpderetta 2y ago
      CPUs could in theory speculate CMOV, reintroducing prediction when predictable. But after Spectre, IIRC Intel now guarantees that CMOV is never speculated.
  - gpderetta 2y ago
    It is both though. At 6+ cycles there are only a few places where CMOV is a win. At 1 cycle you can be more liberal with its use and the lack of dependency breaking is a tradeoff.
  - jnordwick 2y ago
    cmov turns a control dependency into a data dependency. It is still there just in a different way. (its like the Fourier Transform of instructions - lolol). I haven't seen cmov lose to a conditional in a few years (on very recent Intel hardware). Maybe there might be some circumstances where in creates a loop carried dependency that wrecks the optimizer, but I haven't seen one in a minute. To be fair - cmov versions often involve some extra compution to get things in a form where cmov can be used, and I often just opt for the well predicted conditional since those couple extra instructions to set up the value to move can be avoided.
- mgaunard 2y ago
  a cmov-based approach is necessarily slower than a branch-based approach that was correctly predicted, since cmov requires computing both branches then selecting the result at the end.
- clausecker 2y ago
  Are you sure? I recall cmov always having single cycle latency.
  - BoardsOfCanada 2y ago
    I know that it was decoded into 2 micro-ops and thus had to be decoded by the wide decoder, so perhaps 2 cycles?
    - clausecker 2y ago
      That could be. Agner's tables seem to confirm that.
      - jnordwick 2y ago
        Per Fog's tables, Ice Lake shows a reg-to-reg cmov decoding to 1 uop with a latency of 1 and throughput of 0.5. *mont all have latency 2. P4 had a latency of 6. AMD's K10 latency 4.
gpderetta 2y ago
Linus was specifically ranting about compilers inserting CMOV. These days it is actually a pain to get GCC or clang to generate a CMOV when you specifically want it. Also, CMOV did indeed get significantly better.

by dgl 2y ago

tialaramex 2y ago

You can see how dramatically the actual data changes sort performance in e.g. this (summary of the current unstable sort in Rust, ipnsort) https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md#robust https://github.com/Voultapher/sort-research-rs/blob/main/wri... Notice how random_s95 is worse (not by much, but it's there) than fully random. random_s95 is 95% sorted data, but 5% unsorted, simulating a common "sort, do stuff, append, repeat" pattern we see in a lot of software. In contrast the sorted cases are almost instant, and random_d20 (only 20 distinct values, chosen at random, but as a result the sorted output needs much fewer comparions) is very fast.

jnordwick 2y ago

When Linus made that comment cmov was like a 6 cycle latency. For the last decade it has been 1 cycle, and I don't think there is any scenario where cmov is now slower than a branch.

haberman 2y ago
The problem is not the 1 cycle latency, but the data dependency on both values. A correctly-predicted branch cuts the dependency on the value that is not used. I've definitely measured scenarios where cmov/branchless is slower than a branch for a given algorithm. Especially if the branchless version is doing a bit more work to avoid the branch.
- unnah 2y ago
  Good point. It makes me wonder if modern out-of-order processors can skip performing unused computations altogether, if their result registers are overwritten by other data later (in program order).
  - ants_a 2y ago
    No, and it feels unlikely that they will either.
  - gpderetta 2y ago
    CPUs could in theory speculate CMOV, reintroducing prediction when predictable. But after Spectre, IIRC Intel now guarantees that CMOV is never speculated.
- gpderetta 2y ago
  It is both though. At 6+ cycles there are only a few places where CMOV is a win. At 1 cycle you can be more liberal with its use and the lack of dependency breaking is a tradeoff.
- jnordwick 2y ago
  cmov turns a control dependency into a data dependency. It is still there just in a different way. (its like the Fourier Transform of instructions - lolol). I haven't seen cmov lose to a conditional in a few years (on very recent Intel hardware). Maybe there might be some circumstances where in creates a loop carried dependency that wrecks the optimizer, but I haven't seen one in a minute. To be fair - cmov versions often involve some extra compution to get things in a form where cmov can be used, and I often just opt for the well predicted conditional since those couple extra instructions to set up the value to move can be avoided.
mgaunard 2y ago
a cmov-based approach is necessarily slower than a branch-based approach that was correctly predicted, since cmov requires computing both branches then selecting the result at the end.
clausecker 2y ago
Are you sure? I recall cmov always having single cycle latency.
- BoardsOfCanada 2y ago
  I know that it was decoded into 2 micro-ops and thus had to be decoded by the wide decoder, so perhaps 2 cycles?
  - clausecker 2y ago
    That could be. Agner's tables seem to confirm that.
    - jnordwick 2y ago
      Per Fog's tables, Ice Lake shows a reg-to-reg cmov decoding to 1 uop with a latency of 1 and throughput of 0.5. *mont all have latency 2. P4 had a latency of 6. AMD's K10 latency 4.

gpderetta 2y ago

Linus was specifically ranting about compilers inserting CMOV. These days it is actually a pain to get GCC or clang to generate a CMOV when you specifically want it. Also, CMOV did indeed get significantly better.