Skip to contentSkip to conversation

optimize ia32 memmove

PATCH Jeff Garzik 8 participants 12 messages Dec 30, 2003 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 10 lines · Linux Kernel Mailing List

ChangeSet 1.1496.22.32, 2003/12/29 21:45:30-08:00, [email protected]

[PATCH] optimize ia32 memmove

From: Manfred Spraul <[email protected]>

The memmove implementation of i386 is not optimized: it uses movsb, which is far slower than movsd. The optimization is trivial: if dest is less than source, then call memcpy(). markw tried it on a 4xXeon with dbt2, it saved around 300 million cpu ticks in cache_flusharray():

[...]

Quoted 11 lines

diff -Nru a/include/asm-i386/string.h b/include/asm-i386/string.h

include/asm-i386/string.h +0 -4
@@ -299,14 +299,9 @@
 static inline void * memmove(void * dest,const void * src, size_t n)
 {
 int d0, d1, d2;
-if (dest<src)
-__asm__ __volatile__(
-	"rep\n\t"
-	"movsb"

include/asm-i386/string.h line 307

Quoted 10 lines
include/asm-i386/string.h +3 -4
-	: "=&c" (d0), "=&S" (d1), "=&D" (d2)
-	:"0" (n),"1" (src),"2" (dest)
-	: "memory");
-else
+if (dest<src) {
+	memcpy(dest,src,n);
+} else
 __asm__ __volatile__(
 	"std\n\t"
 	"rep\n\t"

Dumb question, though... what about the overlap case, when dest<src ?
It seems to me this change is ignoring that.

Jeff

#2 lore raw
Quoted 29 lines · Jeff Garzik
Quoted 10 lines · Linux Kernel Mailing List

ChangeSet 1.1496.22.32, 2003/12/29 21:45:30-08:00, [email protected]

[PATCH] optimize ia32 memmove

From: Manfred Spraul <[email protected]>

The memmove implementation of i386 is not optimized: it uses movsb, which is far slower than movsd. The optimization is trivial: if dest is less than source, then call memcpy(). markw tried it on a 4xXeon with dbt2, it saved around 300 million cpu ticks in cache_flusharray():

[...]

Quoted 16 lines

diff -Nru a/include/asm-i386/string.h b/include/asm-i386/string.h

include/asm-i386/string.h +1 -8
@@ -299,14 +299,9 @@
 static inline void * memmove(void * dest,const void * src, size_t n)
 {
 int d0, d1, d2;
-if (dest<src)
-__asm__ __volatile__(
-	"rep\n\t"
-	"movsb"
-	: "=&c" (d0), "=&S" (d1), "=&D" (d2)
-	:"0" (n),"1" (src),"2" (dest)
-	: "memory");
-else
+if (dest<src) {
Quoted 9 lines

include/asm-i386/string.h line 307

Quoted 5 lines
include/asm-i386/string.h +2 -0
+	memcpy(dest,src,n);
+} else
 __asm__ __volatile__(
 	"std\n\t"
 	"rep\n\t"

Dumb question, though... what about the overlap case, when dest<src ?
It seems to me this change is ignoring that.

"if dest is less that source, then call memcpy". If the move is to a higher address we do it the old way.

#3 lore raw
Quoted 44 lines · Andrew Morton
Quoted 31 lines · Jeff Garzik
Quoted 10 lines · Linux Kernel Mailing List

ChangeSet 1.1496.22.32, 2003/12/29 21:45:30-08:00, [email protected]

[PATCH] optimize ia32 memmove

From: Manfred Spraul <[email protected]>

The memmove implementation of i386 is not optimized: it uses movsb, which is far slower than movsd. The optimization is trivial: if dest is less than source, then call memcpy(). markw tried it on a 4xXeon with dbt2, it saved around 300 million cpu ticks in cache_flusharray():

[...]

Quoted 16 lines

diff -Nru a/include/asm-i386/string.h b/include/asm-i386/string.h

include/asm-i386/string.h +1 -8
@@ -299,14 +299,9 @@
 static inline void * memmove(void * dest,const void * src, size_t n)
 {
 int d0, d1, d2;
-if (dest<src)
-__asm__ __volatile__(
-	"rep\n\t"
-	"movsb"
-	: "=&c" (d0), "=&S" (d1), "=&D" (d2)
-	:"0" (n),"1" (src),"2" (dest)
-	: "memory");
-else
+if (dest<src) {
Quoted 9 lines
Quoted 5 lines
include/asm-i386/string.h +2 -0
+	memcpy(dest,src,n);
+} else

__asm__ __volatile__(

	"std\n\t"
	"rep\n\t"

Dumb question, though... what about the overlap case, when dest<src ?
It seems to me this change is ignoring that.

Quoted 2 lines

"if dest is less that source, then call memcpy". If the move is to a higher address we do it the old way.

I'm confused... that doesn't say anything to me about overlap.

They can still overlap: Consider if dest is 1 byte less than src, and n==128...

Jeff

#4 lore raw
Quoted 7 lines · Jeff Garzik
Quoted 3 lines

"if dest is less that source, then call memcpy". If the move is to a higher address we do it the old way.

I'm confused... that doesn't say anything to me about overlap.

Overlap is OK if dest<src, because memcpy starts with the lowest address and works upwards.

#5 lore raw
In reply to Jeff Garzik
Quoted 45 lines · Jeff Garzik
Quoted 44 lines · Andrew Morton
Quoted 40 lines · Jeff Garzik
Quoted 10 lines · Linux Kernel Mailing List

ChangeSet 1.1496.22.32, 2003/12/29 21:45:30-08:00, [email protected]

[PATCH] optimize ia32 memmove

From: Manfred Spraul <[email protected]>

The memmove implementation of i386 is not optimized: it uses movsb, which is far slower than movsd. The optimization is trivial: if dest is less than source, then call memcpy(). markw tried it on a 4xXeon with dbt2, it saved around 300 million cpu ticks in cache_flusharray():

[...]

Quoted 19 lines

diff -Nru a/include/asm-i386/string.h b/include/asm-i386/string.h

include/asm-i386/string.h +3 -8
@@ -299,14 +299,9 @@
 static inline void * memmove(void * dest,const void * src, size_t n)
 {
 int d0, d1, d2;
-if (dest<src)
-__asm__ __volatile__(
-	"rep\n\t"
-	"movsb"
-	: "=&c" (d0), "=&S" (d1), "=&D" (d2)
-	:"0" (n),"1" (src),"2" (dest)
-	: "memory");
-else
+if (dest<src) {
+	memcpy(dest,src,n);
+} else

__asm__ __volatile__(

Quoted 2 lines
	"std\n\t"
	"rep\n\t"

Dumb question, though... what about the overlap case, when dest<src ?
It seems to me this change is ignoring that.

Quoted 8 lines
Quoted 2 lines

"if dest is less that source, then call memcpy". If the move is to a higher address we do it the old way.

I'm confused... that doesn't say anything to me about overlap.

They can still overlap: Consider if dest is 1 byte less than src, and n==128...

The non-overlapping cases are probably very common and worth optimizing for:

	if (dest + n < src || src + n < dest) {
		memcpy(dest, src, n);
	} else {
		"old way"
	}

People generally call memmove() if they _think_ the areas might overlap, but if memcpy() can be so much faster it is probably worth catching the cases where the two areas don't actually overlap. The above assumes that "dest + n" and "src + n" don't wrap, but that is probably a broken case in the current code so not worth adding extra checks in for.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

#6 lore raw
Quoted 2 lines · Andreas Dilger

The non-overlapping cases are probably very common and worth optimizing for:

No, almost all non-overlapping users already just use "memcpy()".

So most of the kernel uses of "memmove()" are likely overlapping - and just optimizing the non-overlap case probably doesn't help a lot.

That's why you optimize the overlapping case in one direction. We really should do the other case right too.

Linus

#7 lore raw
In reply to Jeff Garzik
Quoted 5 lines · Jeff Garzik

I'm confused... that doesn't say anything to me about overlap.

They can still overlap: Consider if dest is 1 byte less than src, and n==128...

But then anything that does the loads in ascending order is still ok, so it shouldn't matter - by the time "dest" has been overwritten, the source data has already been read. And all the "memcpy()" implementations had better do that anyway, in order to get nice memory access patterns. "rep movsl" certainly does.

So assuming we have an ascending "memcpy()", the only case we need to care about is "overlap && dest > src".

Now, if we have a non-ascending memcpy(), we have trouble.

Linus

#8 lore raw
Quoted 5 lines · Linus Torvalds

But then anything that does the loads in ascending order is still ok, so it shouldn't matter - by the time "dest" has been overwritten, the source data has already been read. And all the "memcpy()" implementations had better do that anyway, in order to get nice memory access patterns. "rep movsl" certainly does.

A PPC memcpy may end up clearing the destination before reading the source (using the cache-line zeroing instruction, to prevent the destination from being spuriously read to populate the cache line).

J

#9 lore raw
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 5 lines · Linus Torvalds

But then anything that does the loads in ascending order is still ok, so it shouldn't matter - by the time "dest" has been overwritten, the source data has already been read. And all the "memcpy()" implementations had better do that anyway, in order to get nice memory access patterns. "rep movsl" certainly does.

AMD recommends to perform bulk copies backwards: That defeats the hw prefecher, and results in even better access patterns. Doesn't matter in this case, memmove is never used for bulk copies.

Quoted 4 lines

A PPC memcpy may end up clearing the destination before reading the source (using the cache-line zeroing instruction, to prevent the destination from being spuriously read to populate the cache line).

The change is i386 only, no effect on other archs.
I found the unoptimized memmove in oprofiles of dbt2 testruns: slab contains a few memmoves to keep it's recently used arrays in strict LIFO order. Typically perhaps 100 bytes.

--
Manfred

#10 lore raw
Followup to:  <[email protected]>
By author:    Manfred Spraul <[email protected]>
In newsgroup: linux.dev.kernel
Quoted 5 lines

AMD recommends to perform bulk copies backwards: That defeats the hw prefecher, and results in even better access patterns. Doesn't matter in this case, memmove is never used for bulk copies.

That's also a microoptimization for one particular microarchitecture *bug*. Hardware prefetchers are going omnidirectional going forward. Additionally, nearly all bulk copies are performed forward (DF=0) in existing codebases.

-hpa

Signature · 4 lines
<[email protected]> at work, <[email protected]> in private!
If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64
#11 lore raw
In reply to Jeff Garzik

Is this the entire patch? When was the original post since I cant find the message going back over a month ago in the archives or any current posts.

Quoted 30 lines · Jeff Garzik
Quoted 27 lines · Linux Kernel Mailing List

ChangeSet 1.1496.22.32, 2003/12/29 21:45:30-08:00, [email protected]

[PATCH] optimize ia32 memmove

From: Manfred Spraul <[email protected]>

diff -Nru a/include/asm-i386/string.h b/include/asm-i386/string.h

include/asm-i386/string.h Mon Dec 29 23:13:20 2003 +3 -8
@@ -299,14 +299,9 @@
 static inline void * memmove(void * dest,const void * src, size_t n)
 {
 int d0, d1, d2;
-if (dest<src)
-__asm__ __volatile__(
-    "rep\n\t"
-    "movsb"
-    : "=&c" (d0), "=&S" (d1), "=&D" (d2)
-    :"0" (n),"1" (src),"2" (dest)
-    : "memory");
-else
+if (dest<src) {
+    memcpy(dest,src,n);
+} else
 __asm__ __volatile__(
     "std\n\t"
     "rep\n\t"
#12 lore raw
Quoted 5 lines · Ed Sweetman

Is this the entire patch? When was the original post since I cant find the message going back over a month ago in the archives or any current posts.

The original patch is on the 2.5/2.6 commits mailing list, [email protected]. That list sets [email protected] as the From: address, so replies come here.