3 ms·

I don't think the number of uops in the loop being a multiple of 4 is the factor there. To see this, replace `ADD RAX, 1` with `INC RAX`, which does the exact s

by pbsd 12y ago

I don't think the number of uops in the loop being a multiple of 4 is the factor there. To see this, replace `ADD RAX, 1` with `INC RAX`, which does the exact same thing but does not alter the carry flag. The number of uops remains the same, but the runtime difference vanishes. I can't verify this at the moment, but my guess is that the true effect of SBB is to partially serialize the loop, therefore avoiding numerous store-forwarding and other pesky memory subsystem stalls down the line.

nkurz 12y ago
I'd love for you to dive into this one and see where you get. I think this example has a number of confusing layers. My conclusion after staring at it a long time was that the difference between SBB and SUB is that SUB/JNE allows macro fusion and leaves the loop with 4 µops, whereas SBB JNE does not fuse, leaving the loop with 5 µops. Having 5 µops slows the loop down by a cycle, which as you guessed, saves us from a problem caused by issuing the load too soon after the store, although from measuring events, I'm pretty sure this isn't related to store-forwarding. The relevant sections in the Intel Optimization manual are 3.4.2.5 for the µop multiples of 4, and 3.6.5.2 for the load too quickly after store. I'd love to understand better what's actually happening during that delay. Measurements seem to say that it causes the load to be re-executed multiple times.
nkurz 12y ago
I've tried your switch, and yes, switching to a non-flag-setting 'INC RAX' causes both the SUB and SBB versions to run slowly. Since this is not explained by my theory, my explanation must be at least partly wrong. I suspect you are on the correct path, and the dependence on the carry flag is significant But I keep finding all sorts of other timing differences that I can't explain. For example, using the 'INC RAX' version but adding a stray 'XOR RDX, RAX' into the loop makes both SUB and SBB run fast rather than slow. Does this fit with your explanation?
- pbsd 12y ago
  Both fast examples create a dependence between loop iterations. The ADD+SBB case creates a dependence between the carry flag and the value loaded from memory; the INC + XOR creates a dependence on the value of RDX and the value loaded from memory. I don't know what exactly is the mechanism here, but the data dependencies seem to prevent memory loads to be speculated like crazy, presumably the source of the slowdown. Another data point: replace SUB RCX, 1 / JNZ by LOOP. LOOP is much slower, something like 7 uops, but it still results in a speedup. Here I cannot blame data dependencies. LOOP is microcoded, so perhaps its internal implementation has the same effect.

by pbsd 12y ago

nkurz 12y ago

I'd love for you to dive into this one and see where you get. I think this example has a number of confusing layers. My conclusion after staring at it a long time was that the difference between SBB and SUB is that SUB/JNE allows macro fusion and leaves the loop with 4 µops, whereas SBB JNE does not fuse, leaving the loop with 5 µops. Having 5 µops slows the loop down by a cycle, which as you guessed, saves us from a problem caused by issuing the load too soon after the store, although from measuring events, I'm pretty sure this isn't related to store-forwarding. The relevant sections in the Intel Optimization manual are 3.4.2.5 for the µop multiples of 4, and 3.6.5.2 for the load too quickly after store. I'd love to understand better what's actually happening during that delay. Measurements seem to say that it causes the load to be re-executed multiple times.

nkurz 12y ago

I've tried your switch, and yes, switching to a non-flag-setting 'INC RAX' causes both the SUB and SBB versions to run slowly. Since this is not explained by my theory, my explanation must be at least partly wrong. I suspect you are on the correct path, and the dependence on the carry flag is significant But I keep finding all sorts of other timing differences that I can't explain. For example, using the 'INC RAX' version but adding a stray 'XOR RDX, RAX' into the loop makes both SUB and SBB run fast rather than slow. Does this fit with your explanation?

pbsd 12y ago
Both fast examples create a dependence between loop iterations. The ADD+SBB case creates a dependence between the carry flag and the value loaded from memory; the INC + XOR creates a dependence on the value of RDX and the value loaded from memory. I don't know what exactly is the mechanism here, but the data dependencies seem to prevent memory loads to be speculated like crazy, presumably the source of the slowdown. Another data point: replace SUB RCX, 1 / JNZ by LOOP. LOOP is much slower, something like 7 uops, but it still results in a speedup. Here I cannot blame data dependencies. LOOP is microcoded, so perhaps its internal implementation has the same effect.