Slow memcmp for aligned strings on Pentium 3
Kevin Atkinson
kevina@gnu.org
Fri Apr 4 19:27:00 GMT 2003
On Fri, 4 Apr 2003, Marcel Cox wrote:
> There is still a flaw in that you assume that the difference of 2 unsigned
> integers will return the correct signed result. This will not work if for
> instance in your "return xx - yy" statement, xx for instance is 0xf0000000
> and yy is 0x100000. In that case, xx is clearly greater than yy, but the
> difference is 0xe0000000 which cast to signed integer will be a negative
> number and will indicate that xx is smaller than yy which is clearly wrong.
Your right. I relized that after I posted the code. Here is a better
version which also faster when size % 4 != 0:
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;
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;
}
}
Test results (I removed the integer as byte strings functions):
Memory compare 15 bytes:
4120000
1370000
Speed up: 3.007299
Memory compare 16 bytes:
4140000
1460000
Speed up: 2.835616
Memory compare 64 bytes:
11220000
3920000
Speed up: 2.862245
Memory compare 256 bytes:
38550000
12410000
Speed up: 3.106366
Code attached.
--
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 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;
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
.align 2
.p2align 4,,15
.globl cmpa
.type cmpa,@function
cmpa:
cld
subl $8, %esp
movl 20(%esp), %ecx
movl %esi, (%esp)
movl 12(%esp), %esi
cmpl %ecx, %ecx
movl %edi, 4(%esp)
movl 16(%esp), %edi
repz
cmpsb
movl 4(%esp), %edi
movl (%esp), %esi
seta %dl
setb %cl
addl $8, %esp
subb %cl, %dl
movsbl %dl,%eax
ret
.Lfe1:
.size cmpa,.Lfe1-cmpa
.align 2
.p2align 4,,15
.globl cmpa2
.type cmpa2,@function
cmpa2:
pushl %edi
xorl %edx, %edx
pushl %esi
pushl %ebx
movl 24(%esp), %esi
movl 16(%esp), %ebx
movl 20(%esp), %edi
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
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
.align 2
.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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $15, 8(%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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $15, 8(%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)
movl $.LC2, (%esp)
pushl %edi
xorl %edi, %edi
fildl (%esp)
addl $4, %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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $16, 8(%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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $16, 8(%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)
movl $.LC2, (%esp)
pushl %edi
xorl %edi, %edi
fildl (%esp)
addl $4, %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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $64, 8(%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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $64, 8(%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)
movl $.LC2, (%esp)
pushl %edi
xorl %edi, %edi
fildl (%esp)
addl $4, %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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $256, 8(%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 %esi, (%esp)
incl %edi
movl %ebx, 4(%esp)
movl $256, 8(%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)
movl $.LC2, (%esp)
pushl %ebx
fildl (%esp)
addl $4, %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 20020903 (Red Hat Linux 8.0 3.2-7)"
More information about the Gcc
mailing list