x86 performance quirks
Russ Cox
running on a Core 2 T5600 cpu in 64-bit mode.
The loop scans a 1 MB []byte it finds the end of a slice
or a byte >= 0x80.
One copy runs at 260 MB/s; the other runs at 600 MB/s.
The difference between the two is that the slow one
does this to test each element (rearranging code here
to show executed instructions):
01cf51 80fb80 | (9) CMPB BL,$128
01cf54 7205 | (9) JCS ,1cf5b
01cf5b ffc0 | (8) INCL ,AX
01cf5d ebdd | (8) JMP ,1cf3c
01cf3c 89cb | (8) MOVL CX,BX
01cf3e 39c1 | (8) CMPL CX,AX
01cf40 7e14 | (8) JLE ,1cf56
01cf42 4863e8 | (9) MOVLQSX AX,BP
and the fast one does:
01cf51 80fb80 | (8) CMPB BL,$128
01cf54 7308 | (8) JCC ,1cf5e
01cf56 ffc0 | (8) INCL ,AX
01cf58 89cb | (8) MOVL CX,BX
01cf5a 39c1 | (8) CMPL CX,AX
01cf5c 7fe4 | (8) JGT ,1cf42
01cf42 4863e8 | (9) MOVLQSX AX,BP
The only differences I see are the inverted tests
and the extra direct JMP executed in the first trace.
A priori I would not expect either to cause such a
huge difference in performance in something that
should be memory bound anyway.
The full disassembly of each version is below.
Can anyone explain why the fast version is so much
faster than the slow version?
Thanks.
Russ
slow (260 MB/s)
for i = 0; i < len(b); i++ {
if b[i] >= 0x80 {
break
}
}
01cf1e NonASCII | (7) TEXT NonASCII+0(SB),$137438953472
01cf1e 65488b0c25a0080000 | (7) MOVQ 2208(GS),CX
01cf27 483b21 | (7) CMPQ SP,(CX)
01cf2a 7705 | (7) JHI ,1cf31
01cf2c e85364feff | (7) CALL ,3384+runtime.morestack32
01cf31 488b542408 | (7) MOVQ b+8(SP),DX
01cf36 8b4c2410 | (7) MOVL b+16(SP),CX
01cf3a 31c0 | (8) MOVL $0,AX
01cf3c 89cb | (8) MOVL CX,BX
01cf3e 39c1 | (8) CMPL CX,AX
01cf40 7e14 | (8) JLE ,1cf56
01cf42 4863e8 | (9) MOVLQSX AX,BP
01cf45 39cd | (9) CMPL BP,CX
01cf47 7205 | (9) JCS ,1cf4e
01cf49 e8833fffff | (9) CALL ,10ed1+runtime.panicindex
01cf4e 8a1c2a | (9) MOVB (DX)(BP*1),BL
01cf51 80fb80 | (9) CMPB BL,$128
01cf54 7205 | (9) JCS ,1cf5b
01cf56 89442420 | (15) MOVL AX,.noname+32(SP)
01cf5a c3 | (15) RET ,
01cf5b ffc0 | (8) INCL ,AX
01cf5d ebdd | (8) JMP ,1cf3c
fast (600 MB/s)
for i = 0; i < len(b) && b[i] < 0x80; i++ {
}
01cf1e NonASCII | (7) TEXT NonASCII+0(SB),$137438953472
01cf1e 65488b0c25a0080000 | (7) MOVQ 2208(GS),CX
01cf27 483b21 | (7) CMPQ SP,(CX)
01cf2a 7705 | (7) JHI ,1cf31
01cf2c e85364feff | (7) CALL ,3384+runtime.morestack32
01cf31 488b542408 | (7) MOVQ b+8(SP),DX
01cf36 8b4c2410 | (7) MOVL b+16(SP),CX
01cf3a 31c0 | (8) MOVL $0,AX
01cf3c 89cb | (8) MOVL CX,BX
01cf3e 39c1 | (8) CMPL CX,AX
01cf40 7e1c | (8) JLE ,1cf5e
01cf42 4863e8 | (8) MOVLQSX AX,BP
01cf45 39cd | (8) CMPL BP,CX
01cf47 7205 | (8) JCS ,1cf4e
01cf49 e8833fffff | (8) CALL ,10ed1+runtime.panicindex
01cf4e 8a1c2a | (8) MOVB (DX)(BP*1),BL
01cf51 80fb80 | (8) CMPB BL,$128
01cf54 7308 | (8) JCC ,1cf5e
01cf56 ffc0 | (8) INCL ,AX
01cf58 89cb | (8) MOVL CX,BX
01cf5a 39c1 | (8) CMPL CX,AX
01cf5c 7fe4 | (8) JGT ,1cf42
01cf5e 89442420 | (12) MOVL AX,.noname+32(SP)
01cf62 c3 | (12) RET ,
Paul Borman
ron minnich
the fast one < 32 bytes in the inner loop. But cache lines on this
machine are 64 bytes (I just checked).
But were you worried about the size of the loop there's an easy way to
check it; shrink the inner loop:
01cf51 80fb80 | (9) CMPB BL,$128
01cf54 7205 | (9) JCS ,1cf5b
01cf56 89442420 | (15) MOVL AX,.noname+32(SP)
01cf5a c3 | (15) RET ,
01cf5b ffc0 | (8) INCL ,AX
01cf5d ebdd | (8) JMP ,1cf3c
An assembly guy might write this differently:
INCL AX
01cf51 80fb80 | (9) CMPB BL,$128
01cf54 7205 | (9) JCS ,1cf3c
01cf56 89442420 | (15) MOVL AX,.noname+32(SP)
01cf5a c3 | (15) RET ,
yes, an unnecessary INCL on the last time in the loop but it shrinks
the inner loop a bit -- and removes a JMP which may be more costly
than that last unnecessary INCL-- only assuming the size matters (and
assuming I didn't screw this up ...). I doubt that's it however.
If you really want to crack this one you might try AMD's excellent
SIMNow tool, which I've used in the past to try to figure out this
sort of thing. Or ask those excellent CLANG experts at Google :-)
ron
Aaron Durbin
> Well, the slow one has:
> 01cf5d JMP ,1cf3c
> while the fast one has
> 01cf5c JGT ,1cf42
> So the slow one is potentially hitting more cache lines for instructions in
> the loop. I don't know what the cache lines are these days and if jumping
> across a 64 byte boundary would make much a difference (I assume the machine
> was lightly loaded so using an extra cache line shouldn't make a difference.
I agree w/ Paul on that cacheline analysis. However, the first loop
has 4 branches through each loop that doesn't pass the condition
checks while the 2nd loop only has only 3. I think the number of
branches are what is ailing the first implementation.
ron minnich
> I agree w/ Paul on that cacheline analysis.
On a machine like this with 64 byte cache lines, the loop sizes are:
5e - 3c = 34 bytes
5d - 42 = 25 bytes.
But, good point, the "slow" one crosses (I assume) a cache line
boundary, since the 64-byte cache lines ought to be 0x40 aligned. The
second does not.
> However, the first loop
> has 4 branches through each loop that doesn't pass the condition
> checks while the 2nd loop only has only 3. I think the number of
> branches are what is ailing the first implementation.
But harder to imagine that that's worth a factor of 3x in memory bandwidth.
The fast one has only relative jumps, the slow one has an absolute
jmp. In the old days we used certain types of abs. jumps to flush the
pipeline but that's a pretty ancient trick and I can't find references
to such things in newer CPU docs, except a few special cases when you
change CPU modes.
Would be interesting to change the "slow" one as I suggested earlier
and see if shrinking it and aligning it to fit one cache line helped.
I'm skeptical. But the one big difference, still, is that
unconditional backward jmp. Would also be interesting to see if that's
it.
Gotta love modern CPUs -- well, really you do, they're so fast --
until you hit this stuff ...
But it's extremely helpful to pass stuff like this through a good
simulator (I'm sure intel can point you at one) and see what it thinks
is going on.
ron
Paul Borman
package svar extra intfunc slow(b []byte) (i int) {// extra = i
for i = 0; i < len(b); i++ {if b[i] >= 0x80 {break}}
return}func fast(b []byte) (i int) {
for i = 0; i < len(b) && b[i] < 0x80; i++ {}
return}
Paul Borman
-Paul
ron minnich
> Cache lines play part of it.
>
> package s
> var extra int
>
> func slow(b []byte) (i int) {
> // extra = i
> for i = 0; i < len(b); i++ {
> if b[i] >= 0x80 {
> break
> }
> }
> return
> }
> func fast(b []byte) (i int) {
> for i = 0; i < len(b) && b[i] < 0x80; i++ {
> }
> return
> }
>
I'd be pretty surprised if these turned into very different object
code. But I don't always have a good sense for what 6g will produce,
as opposed to the optimizing compilers I'm used to. OK, now I get to
be surprised :-) But note that you added an extra line of code (which
I doubt matters) but you also changed the sense of the test (which I
think matters more). But let's see the code.
Would be nice to see a 6.out dump.
ron
Paul Borman
Devon H. O'Dell
handy right now). Both should be able to give you a full disassembly.
--dho
2011/10/4 Paul Borman <bor...@google.com>:
Paul Borman
Paul Borman
Anthony Martin
> How do I dump a 6.out on a Mac?
Pass 6l the '-a' flag. You'll also
want to redirect stdout to a file.
Cheers,
Anthony
brainman
How do I dump a 6.out on a Mac? gdb isn't my friend. It is built with:
I think you want
6l -a ...
Alex
ron minnich
which very small changes lead to very large deltas in performance ...
the instructions you see are not necessarily strongly related to what
goes on. It's a common experience.
I sure hope you all figure it out and can tell me the answer :)
ron
Paul Borman
Paul Borman
Tarmigan
>
> package s
> var extra int
>
> func slow(b []byte) (i int) {
> // extra = i
> for i = 0; i < len(b); i++ {
> if b[i] >= 0x80 {
> break
> }
> }
> return
> }
> func fast(b []byte) (i int) {
> for i = 0; i < len(b) && b[i] < 0x80; i++ {
> }
> return
> }
>
> When I bench mark this I get:
> s.BenchmarkSlow 500 4634360 ns/op
> s.BenchmarkFast 1000 1992247 ns/op
> But when I uncomment the "extra" line I get:
> s.BenchmarkSlow 500 3974158 ns/op
> s.BenchmarkFast 1000 1996931 ns/op
> If I make a slow1 and slow2 in the same file (one with the extra line and
> one without) it lines things up different and both slow loops are nearly
> identical.
> So it is probably a combination of the extra check as well as the cache.
> I guess I should learn how to dump a 6.out
Do you have a complete example (including data)? I tried to recreate
from scratch (without "extra"), but got
s.BenchmarkFast 500 3194202 ns/op
s.BenchmarkSlow 500 3166650 ns/op
on an EC2 linux micro instance.
Thanks,
Tarmigan
Ian Lance Taylor
> One copy runs at 260 MB/s; the other runs at 600 MB/s.
> The difference between the two is that the slow one
> does this to test each element (rearranging code here
> to show executed instructions):
>
> 01cf51 80fb80 | (9) CMPB BL,$128
> 01cf54 7205 | (9) JCS ,1cf5b
> 01cf5b ffc0 | (8) INCL ,AX
> 01cf5d ebdd | (8) JMP ,1cf3c
> 01cf3c 89cb | (8) MOVL CX,BX
> 01cf3e 39c1 | (8) CMPL CX,AX
> 01cf40 7e14 | (8) JLE ,1cf56
> 01cf42 4863e8 | (9) MOVLQSX AX,BP
>
> and the fast one does:
> 01cf51 80fb80 | (8) CMPB BL,$128
> 01cf54 7308 | (8) JCC ,1cf5e
> 01cf56 ffc0 | (8) INCL ,AX
> 01cf58 89cb | (8) MOVL CX,BX
> 01cf5a 39c1 | (8) CMPL CX,AX
> 01cf5c 7fe4 | (8) JGT ,1cf42
> 01cf42 4863e8 | (9) MOVLQSX AX,BP
I note that in the slow case the default branch predictions are wrong
and in the fast case they are right. By default the processor predicts
a backward branch as taken and a forward branch as not taken. The slow
loop has a default branch misprediction leading to a mispredicted RET,
which is a particularly bad case. However, since this is in a loop it's
hard to believe it would make such a big difference.
I think that in the slow case the loop occupies two cache lines whereas
in the fast case the loop is entirely within one cache line. Again it's
hard to believe this would make such a big difference.
Why is the MOVL CX,BX instruction there?
Ian
⚛
likely related to branch prediction.
Try running "perf stat -- program" in Linux.
Dmitry Vyukov
Paulo Pinto
pure
assembly code might not bring the gains one might expect.
--
Paulo
> *The Loop Stream Detector was introduced in Intel® Core microarchitectures.
> The **LSD detects small loops that fit in the micro-op queue and locks them
> down. The loop*
> *streams from the micro-op queue, with no more fetching, decoding, or
> reading **micro-ops from any of the caches, until a branch miss-prediction
> inevitably ends it.*
> *The loops with the following attributes qualify for LSD/micro-op queue
> replay:*
> *- Up to eight chunk fetches of 32-instruction-bytes*
> *- Up to 28 micro-ops (~28 instructions)*
> *- All micro-ops are also resident in the Decoded ICache*
> *- Can contain no more than eight taken branches and none of them can be a
> CALL or RET*
> *- Cannot have mismatched stack operations. For example, more PUSH **than
> POP instructions.*
> *Many calculation-intensive loops, searches and software string moves match
> these **characteristics.*
> *Use the loop cache functionality opportunistically. For high performance
> code, loop **unrolling is generally preferable for performance even when it
> overflows the LSD **capability.*
Miki Tebeka
Russ Cox
> I suspect it has to do with ...
That's very interesting, but can you see why it would
fail to fit in one case but not the other? It looks to
me like maybe it's the mispredict, but you'd think
after an iteration or two it would re-enter the LSD with
the correct predictions. We're nowhere near the
32 instruction bytes or 28 micro-ops or 8 taken branches.
I'm going to invert the if branch anyway, so that if
nothing else we get the same code for
for y { }
and
for { if !y { break } }
but I don't fully understand what's going on.
I played with performance counters using Shark for
a while but there wasn't anything that seemed interesting.
It looks like the Core i7 added an LSD_UOPS counter
but the Core 2 didn't have it despite having an LSD.
Russ
Jan Mercl
On Tue, Oct 4, 2011 at 08:17, Dmitry Vyukov <dvy...@google.com> wrote:
> I suspect it has to do with ...That's very interesting, but can you see why it would
fail to fit in one case but not the other? It looks to
me like maybe it's the mispredict, but you'd think
after an iteration or two it would re-enter the LSD with
the correct predictions.
Dmitry Vyukov
On Tue, Oct 4, 2011 at 08:17, Dmitry Vyukov <dvy...@google.com> wrote:
> I suspect it has to do with ...
That's very interesting, but can you see why it would
fail to fit in one case but not the other? It looks to
me like maybe it's the mispredict, but you'd think
after an iteration or two it would re-enter the LSD with
the correct predictions. We're nowhere near the
32 instruction bytes or 28 micro-ops or 8 taken branches.
I'm going to invert the if branch anyway, so that if
nothing else we get the same code for
for y { }
and
for { if !y { break } }
but I don't fully understand what's going on.
Ian Lance Taylor
> IIRC, the branch prediction used to be fully static (like fwd:not taken,
> back:taken). Don't know if that changed in LSD, but when I try to imagine
> the HW requirements [within a multicore CPU with multiple level caches], I
> guess it's still the same old story today.
Most modern Intel processors have a branch prediction cache, because
branch mispredictions are so expensive.
That said, Russ: what processor are you using?
Also I noticed this:
which claims that loop alignment makes a measurable difference, although
I didn't see anything about that in the Intel optimization manual.
Ian
Paul Borman
which claims that loop alignment makes a measurable difference, although
I didn't see anything about that in the Intel optimization manual.
Dmitry Vyukov
Jan Mercl <jan....@nic.cz> writes:Most modern Intel processors have a branch prediction cache, because
> IIRC, the branch prediction used to be fully static (like fwd:not taken,
> back:taken). Don't know if that changed in LSD, but when I try to imagine
> the HW requirements [within a multicore CPU with multiple level caches], I
> guess it's still the same old story today.
branch mispredictions are so expensive.
Russ Cox
The Core 2 T5600 in my Mac Mini is the one that cares
quite a lot about this difference. The Core i7 L 640 in
my Thinkpad X201s is unaffected.
Russ