Slow memcmp for aligned strings on Pentium 3

[Jerry Quinn]

Kevin Atkinson writes:
 > On Sat, 5 Apr 2003, Jerry Quinn wrote:
 > 
 > > Kevin Atkinson writes:
 > >  > On Fri, 4 Apr 2003, Jerry Quinn wrote:
 > >  > 
 > >  > > I just tried the same benchmark on a Pentium 4 out of curiosity.  Slightly
 > >  > > different results:
 > >  > > 
 > >  > > Memory compare int:
 > >  > >   10000
 > >  > >   130000
 > >  > >   Speed up: 0.076923
 > >  > > Memory compare 15 bytes:
 > >  > >   10000
 > >  > >   370000
 > >  > >   Speed up: 0.027027
 > >  > > Memory compare 16 bytes:
 > >  > >   20000
 > >  > >   330000
 > >  > >   Speed up: 0.060606
 > >  > > Memory compare 64 bytes:
 > >  > >   10000
 > >  > >   1040000
 > >  > >   Speed up: 0.009615
 > >  > > Memory compare 256 bytes:
 > >  > >   20000
 > >  > >   2300000
 > >  > >   Speed up: 0.008696
 > >  > > 
 > >  > > Perhaps this is to be expected since the routine uses shifts.
 > >  > 
 > >  > The shift are only used in the case size is not divisible by 4.  It seams 
 > >  > that on the Pentium 4 cmps is the way to go.  You might also want to 
 > >  > increase the number of loop iterations to get more meaning full results 
 > >  > due the limited precision of clock().
 > > 
 > > Adding iterations didn't change the relative scores significantly.  It
 > > still loses big on P4.  It also loses big on Athlon.  Here are Athlon
 > > results using the later version you posted with 10x iterations:
 > > 
 > > jlquinn@smaug:~/gcc/test$ gcc3.3 -O3 -fomit-frame-pointer -march=athlon cmps.c 
 > > jlquinn@smaug:~/gcc/test$ ./a.out 
 > > Memory compare 15 bytes:
 > >   310000
 > >   5810000
 > >   Speed up: 0.053356
 > > Memory compare 16 bytes:
 > >   300000
 > >   5290000
 > >   Speed up: 0.056711
 > > Memory compare 64 bytes:
 > >   460000
 > >   13770000
 > >   Speed up: 0.033406
 > > Memory compare 256 bytes:
 > >   470000
 > 
 > This is extremely interesting.  Does anyone have any documentation on cmps 
 > behavior on P4 and Athlon?  It could be that the processor is somehow 
 > "caching" the results of cmps.  Maybe it has to do with the fact that the 
 > strings are all 0 except for the end or because the strings do not change.  
 > Or maybe cmps is just extremely fast, but how?  Or it could be that the 
 > loop needs unrolling for better pipeline performance.  I don't have a P4 
 > or Athlon so if someone could play around with my code by testing by 
 > testing some of my theories I would appreciate it.
 > 
 > I just ran the test on a Pentium MMX and i got similar results as I did 
 > for my P3.  So at very least it seams that something similar to my code is 
 > the way to go for Pentiums up to P3.

Unrolling makes things even worse for Athlon - or rather MUCH better
for the builtin function:

jlquinn@smaug:~/gcc/test$ gcc3.3 -O3 -fomit-frame-pointer -funroll-loops -mcpu=athlon cmps.c 
jlquinn@smaug:~/gcc/test$ ./a.out 
Memory compare 15 bytes:
  40000
  5440000
  Speed up: 0.007353
Memory compare 16 bytes:
  60000
  5070000
  Speed up: 0.011834
Memory compare 64 bytes:
  60000
  13660000
  Speed up: 0.004392
Memory compare 256 bytes:
  60000
  39300000
  Speed up: 0.001527

If I assign both arrays to the same set of random bytes, the results
tilt a bit more towards your routine :-)

jlquinn@smaug:~/gcc/test$ gcc3.3 -O3 -fomit-frame-pointer -mcpu=athlon cmps.c 
jlquinn@smaug:~/gcc/test$ ./a.out 
Memory compare 15 bytes:
  460000
  5640000
  Speed up: 0.081560
Memory compare 16 bytes:
  450000
  5390000
  Speed up: 0.083488
Memory compare 64 bytes:
  300000
  5250000
  Speed up: 0.057143
Memory compare 256 bytes:
  310000
  5090000
  Speed up: 0.060904

Making the two arrays randomly generated and different from each other
provides yet more improvement:

jlquinn@smaug:~/gcc/test$ gcc3.3 -O3 -fomit-frame-pointer -mcpu=athlon cmps.c 
jlquinn@smaug:~/gcc/test$ ./a.out 
Memory compare 15 bytes:
  310000
  3660000
  Speed up: 0.084699
Memory compare 16 bytes:
  310000
  3510000
  Speed up: 0.088319
Memory compare 64 bytes:
  460000
  3510000
  Speed up: 0.131054
Memory compare 256 bytes:
  460000
  3500000


Still not even close.  I just scanned the Athlon optimization guide
and there is a comment about being sure to align the inputs for
repeated string ops.  That makes it sound like work was done to make
aligned cmpsb efficient.

I also tried commenting out the final int cleanup so that cmpa2 looks
like:

__attribute__((noinline))
int cmpa2(const unsigned int * x, const unsigned int * y, size_t size)
{
  int i = 0;
  size_t s = size / 4;
  while (i < s && x[i] == y[i]) ++i;
  size -= i * 4;
  if (size == 0) return 0;
  return 1;
/*   unsigned int xx = x[i], yy = y[i]; */
/*   asm("bswap %0" : "+r"(xx)); */
/*   asm("bswap %0" : "+r"(yy)); */
/*   if (size >= 4) { */
/*     return xx < yy ? -1 : 1; */
/*   } else { */
/*     unsigned int dis = 8*(4-size); */
/*     xx >>= dis; */
/*     yy >>= dis; */
/*     return xx - yy; */
/*   } */
}


I wanted to see if the compiler could make the simple integer compare
fast.  This is an (expected) improvement, but doesn't come close to
narrowing the gap:

jlquinn@smaug:~/gcc/test$ gcc3.3 cmps.c -O3 -fomit-frame-pointer -mcpu=athlon  
jlquinn@smaug:~/gcc/test$ ./a.out 
Memory compare 15 bytes:
  300000
  2740000
  Speed up: 0.109489
Memory compare 16 bytes:
  310000
  2520000
  Speed up: 0.123016
Memory compare 64 bytes:
  480000
  2590000
  Speed up: 0.185328
Memory compare 256 bytes:
  460000
  2680000
  Speed up: 0.171642

It seems the conclusion is that rep cmpsb is very fast on Athlon.
Also probably for P4, but I haven't tried the same tests beyond the
first one.

Jerry Quinn