Re: Slow memcmp for aligned strings on Pentium 3

[Kevin Atkinson <kevina at gnu dot org>]

On Thu, 3 Apr 2003, Roger Sayle wrote:

> I suspect it should be possible to fix your code to handle these
> termination conditions correctly, and a comparison of your
> routine's performance with these fixes vs. __builtin_memcmp
> would be of interest.

Here you go.  Still assume the memory is alligned:

This is what I did:

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;
  // hopefully if this is inline expanded when size is known
  // the compiler can eliminate many of these conditionals
  else if (size >= 4) { // if original size % 4 == 0 this should
                        // always be the case
    unsigned int xx = x[i], yy = y[i];
    asm("bswap %0" : "+r"(xx));
    asm("bswap %0" : "+r"(yy));
    return xx - yy;
  } else {
    const unsigned char * xb = (const unsigned char *)(x + i);
    const unsigned char * yb = (const unsigned char *)(y + i);
    // if size is known at compile time then the compiler should be
    // able to select the correct choice at compile time
    switch (size) {
    case 1:
      return *xb - *yb;
    case 2:
      return ((xb[0] - yb[0]) <<  8) + (xb[1] - yb[1]);
    case 3:
      return ((xb[0] - yb[0]) << 16) + ((xb[1] - yb[1]) << 8)
        + xb[2] - yb[2];}
  }
}

compiled with gcc -fomit-frame-pointer -O3 -march=pentium3 cmps.c

Memory compare int:
  2160000
  360000
  Speed up: 6.000000
Memory compare 15 bytes:
  4120000
  1550000
  Speed up: 2.658065
Memory compare 16 bytes:
  4150000
  1310000
  Speed up: 3.167939
Memory compare 64 bytes:
  11240000
  3470000
  Speed up: 3.239193
Memory compare 256 bytes:
  37930000
  10050000
  Speed up: 3.774129

Code and assembly output attached.

-- 
http://kevin.atkinson.dhs.org

Attachment: cmps.c
Description: Text document

Attachment: cmps.s
Description: Text document