Memcmp on i386 Final Recommendations
Kevin Atkinson
kevin@atkinson.dhs.org
Sat Apr 12 13:48:00 GMT 2003
When memcmp is used for aligned strings I strongly recommend a loop be
used instead of rep cmps on Intel Pentium up to P3. For the Athlon
(and possible P4) using cmps is best. I have verified that using a
loop on the Pentium MMX, Pentium II, and Pentium III is approximately 3
times faster than using a rep cmps. For the Athlon I have verified
that rep cmps is best. For the Athlon the timing for rep cmps is 16 +
(10/3)*c which will be pretty hard to beat on a loop using integer
operations.
For very short strings where the size is known I strongly recommend
using using bswap and compare. On any processor that I know about the
cmps instruction is not very efficient without the rep prefix and with
the rep prefix there is a fixed overhead which is significant when the
string is short. Furthermore it may very well be the case that the
value to compare is already loaded in a register as in the case of:
int x, y; ... memcmp(&x,&y,4) ...
I use such a compare in one of my project so this is not a
hypothetical case. I can post the code snippet that uses it if anyone
is interested.
For the general aligned case case it may faster to use the MMX or SSE
registers and instructions to perform the compare. I have not looked
into this at all. For all I know this may not even be possible.
The following code will perform memcmp in the aligned case via a loop
and a bswap at the end. It is assumed that it is okay to read off the
end of the string up to the nearest multiple of 4.
int cmps(const void * x0, const void * y0, size_t size)
{
const unsigned int * x = (const unsigned int *)x0;
const unsigned int * y = (const unsigned int *)y0;
int i = 0;
size_t s = size / 4;
while (i < s && x[i] == y[i]) ++i;
size -= i * 4;
if (size == 0) return 0;
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;
}
}
Here are the results when compared to __builtin_memcmp. The code is
attached. It was compiled with gcc 3.2.2 on Red Hat Linux 9 with -O3
-march=pentium3:
Memory compare 15 bytes:
4190000
1470000
Speed up: 2.850340
Memory compare 16 bytes:
4360000
1520000
Speed up: 2.868421
Memory compare 64 bytes:
11440000
4040000
Speed up: 2.831683
Memory compare 256 bytes:
38000000
12310000
Speed up: 3.086921
I do not know enough about gcc internals to submit a formal patch. An
memcmp implementation is the best I can offer. I hope someone will
take the initiative to create a formal patch out of my implementation
for Gcc 3.4.
Thanks.
--
http://kevin.atkinson.dhs.org
-------------- next part --------------
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
__attribute__((noinline))
int cmpa(const unsigned int * x, const unsigned int * y, size_t size)
{
return __builtin_memcmp(x,y,size);
}
__attribute__((noinline))
int cmpa2(const void * x0, const void * y0, size_t size)
{
const unsigned int * x = (const unsigned int *)x0;
const unsigned int * y = (const unsigned int *)y0;
int i = 0;
size_t s = size / 4;
while (i < s && x[i] == y[i]) ++i;
size -= i * 4;
if (size == 0) return 0;
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;
}
}
int main()
{
unsigned int x,y,i;
int xa[256] = {}, ya[256] = {};
int s,f;
clock_t t;
printf("Memory compare 15 bytes:\n");
xa[3] = 6;
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa(xa, ya, 15);
s = clock() - t;
printf(" %d\n", s);
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa2(xa, ya, 15);
f = clock() - t;
printf(" %d\n",f);
printf(" Speed up: %f\n", (double)s/f);
xa[3] = 0;
printf("Memory compare 16 bytes:\n");
xa[3] = 6;
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa(xa, ya, 16);
s = clock() - t;
printf(" %d\n", s);
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa2(xa, ya, 16);
f = clock() - t;
printf(" %d\n",f);
printf(" Speed up: %f\n", (double)s/f);
xa[3] = 0;
printf("Memory compare 64 bytes:\n");
xa[15] = 6;
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa(xa, ya, 64);
s = clock() - t;
printf(" %d\n", s);
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa2(xa, ya, 64);
f = clock() - t;
printf(" %d\n",f);
printf(" Speed up: %f\n", (double)s/f);
xa[15] = 0;
printf("Memory compare 256 bytes:\n");
xa[63] = 6;
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa(xa, ya, 256);
s = clock() - t;
printf(" %d\n", s);
t = clock();
for (i = 0; i != 0x1000000; ++i)
cmpa2(xa, ya, 256);
f = clock() - t;
printf(" %d\n",f);
printf(" Speed up: %f\n", (double)s/f);
}
-------------- next part --------------
.file "cmps.c"
.text
.p2align 4,,15
.globl cmpa
.type cmpa,@function
cmpa:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl %esi, (%esp)
movl 16(%ebp), %ecx
movl 8(%ebp), %esi
movl %edi, 4(%esp)
movl 12(%ebp), %edi
cmpl %ecx, %ecx
cld
repz
cmpsb
movl 4(%esp), %edi
movl (%esp), %esi
seta %dl
setb %cl
movl %ebp, %esp
popl %ebp
subb %cl, %dl
movsbl %dl,%eax
ret
.Lfe1:
.size cmpa,.Lfe1-cmpa
.p2align 4,,15
.globl cmpa2
.type cmpa2,@function
cmpa2:
pushl %ebp
movl %esp, %ebp
xorl %edx, %edx
pushl %edi
movl 12(%ebp), %edi
pushl %esi
movl 16(%ebp), %esi
pushl %ebx
movl 8(%ebp), %ebx
movl %esi, %ecx
shrl $2, %ecx
cmpl %ecx, %edx
jae .L4
movl (%edi), %eax
cmpl %eax, (%ebx)
je .L7
.L4:
leal 0(,%edx,4), %ecx
subl %ecx, %esi
jne .L8
xorl %edx, %edx
.L2:
popl %ebx
movl %edx, %eax
popl %esi
popl %edi
popl %ebp
ret
.p2align 4,,7
.L8:
movl (%ebx,%edx,4), %ebx
movl (%edi,%edx,4), %eax
#APP
bswap %ebx
bswap %eax
#NO_APP
cmpl $3, %esi
jbe .L9
cmpl %eax, %ebx
sbbl %edx, %edx
orl $1, %edx
jmp .L2
.p2align 4,,7
.L9:
movl $4, %ecx
subl %esi, %ecx
sall $3, %ecx
movl %ebx, %edx
shrl %cl, %edx
shrl %cl, %eax
subl %eax, %edx
jmp .L2
.p2align 4,,7
.L7:
incl %edx
cmpl %ecx, %edx
jae .L4
movl (%edi,%edx,4), %eax
cmpl %eax, (%ebx,%edx,4)
je .L7
jmp .L4
.Lfe2:
.size cmpa2,.Lfe2-cmpa2
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "Memory compare 15 bytes:"
.LC1:
.string " %d\n"
.LC2:
.string " Speed up: %f\n"
.LC3:
.string "Memory compare 16 bytes:"
.LC4:
.string "Memory compare 64 bytes:"
.LC5:
.string "Memory compare 256 bytes:"
.text
.p2align 4,,15
.globl main
.type main,@function
main:
pushl %ebp
xorl %eax, %eax
movl %esp, %ebp
pushl %edi
movl $256, %ecx
pushl %esi
leal -1048(%ebp), %esi
movl %esi, %edi
pushl %ebx
leal -2072(%ebp), %ebx
subl $2092, %esp
cld
andl $-16, %esp
rep
stosl
movl $256, %ecx
movl %ebx, %edi
rep
stosl
xorl %edi, %edi
movl $.LC0, (%esp)
call puts
movl $6, %eax
movl %eax, -1036(%ebp)
call clock
movl %eax, -2084(%ebp)
.p2align 4,,15
.L19:
movl $15, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa
cmpl $16777216, %edi
jne .L19
call clock
movl %eax, -2080(%ebp)
xorl %edi, %edi
movl -2084(%ebp), %eax
subl %eax, -2080(%ebp)
movl $.LC1, (%esp)
movl -2080(%ebp), %eax
movl %eax, 4(%esp)
call printf
call clock
movl %eax, -2084(%ebp)
.L24:
movl $15, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa2
cmpl $16777216, %edi
jne .L24
call clock
movl $.LC1, (%esp)
movl -2084(%ebp), %ecx
movl %eax, %edi
subl %ecx, %edi
movl %edi, 4(%esp)
call printf
fildl -2080(%ebp)
pushl %edi
xorl %edi, %edi
fildl (%esp)
addl $4, %esp
movl $.LC2, (%esp)
fdivrp %st, %st(1)
fstpl 4(%esp)
call printf
xorl %edx, %edx
movl %edx, -1036(%ebp)
movl $.LC3, (%esp)
call puts
movl $6, %eax
movl %eax, -1036(%ebp)
call clock
movl %eax, -2084(%ebp)
.L29:
movl $16, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa
cmpl $16777216, %edi
jne .L29
call clock
movl $.LC1, (%esp)
movl %eax, -2080(%ebp)
movl -2084(%ebp), %eax
subl %eax, -2080(%ebp)
movl -2080(%ebp), %edi
movl %edi, 4(%esp)
xorl %edi, %edi
call printf
call clock
movl %eax, -2084(%ebp)
.L34:
movl $16, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa2
cmpl $16777216, %edi
jne .L34
call clock
movl $.LC1, (%esp)
movl %eax, %edi
movl -2084(%ebp), %eax
subl %eax, %edi
movl %edi, 4(%esp)
call printf
fildl -2080(%ebp)
pushl %edi
xorl %edi, %edi
fildl (%esp)
addl $4, %esp
movl $.LC2, (%esp)
fdivrp %st, %st(1)
fstpl 4(%esp)
call printf
xorl %edx, %edx
movl %edx, -1036(%ebp)
movl $.LC4, (%esp)
call puts
movl $6, %eax
movl %eax, -988(%ebp)
call clock
movl %eax, -2084(%ebp)
.L39:
movl $64, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa
cmpl $16777216, %edi
jne .L39
call clock
movl %eax, -2080(%ebp)
xorl %edi, %edi
movl -2084(%ebp), %eax
subl %eax, -2080(%ebp)
movl $.LC1, (%esp)
movl -2080(%ebp), %eax
movl %eax, 4(%esp)
call printf
call clock
movl %eax, -2084(%ebp)
.L44:
movl $64, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa2
cmpl $16777216, %edi
jne .L44
call clock
movl $.LC1, (%esp)
movl %eax, %edi
movl -2084(%ebp), %eax
subl %eax, %edi
movl %edi, 4(%esp)
call printf
fildl -2080(%ebp)
pushl %edi
xorl %edi, %edi
fildl (%esp)
addl $4, %esp
movl $.LC2, (%esp)
fdivrp %st, %st(1)
fstpl 4(%esp)
call printf
movl %edi, -988(%ebp)
xorl %edi, %edi
movl $.LC5, (%esp)
call puts
movl $6, %ecx
movl %ecx, -796(%ebp)
call clock
movl %eax, -2084(%ebp)
.L49:
movl $256, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa
cmpl $16777216, %edi
jne .L49
call clock
movl %eax, -2080(%ebp)
xorl %edi, %edi
movl -2084(%ebp), %eax
subl %eax, -2080(%ebp)
movl $.LC1, (%esp)
movl -2080(%ebp), %edx
movl %edx, 4(%esp)
call printf
call clock
movl %eax, -2084(%ebp)
.L54:
movl $256, 8(%esp)
incl %edi
movl %ebx, 4(%esp)
movl %esi, (%esp)
call cmpa2
cmpl $16777216, %edi
jne .L54
call clock
movl $.LC1, (%esp)
movl %eax, %ebx
movl -2084(%ebp), %eax
subl %eax, %ebx
movl %ebx, 4(%esp)
call printf
fildl -2080(%ebp)
pushl %ebx
fildl (%esp)
addl $4, %esp
movl $.LC2, (%esp)
fdivrp %st, %st(1)
fstpl 4(%esp)
call printf
leal -12(%ebp), %esp
popl %ebx
popl %esi
popl %edi
popl %ebp
ret
.Lfe3:
.size main,.Lfe3-main
.ident "GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5)"
More information about the Gcc
mailing list