optimize ia32 memmove
A message that is not in the archive (sent off-list or not yet received): [email protected]
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 incache_flusharray():
[...]
Quoted 11 lines
diff -Nru
a/include/asm-i386/string.hb/include/asm-i386/string.hinclude/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
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 incache_flusharray():[...]
Quoted 16 lines
diff -Nru
a/include/asm-i386/string.hb/include/asm-i386/string.hinclude/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.
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 incache_flusharray():[...]
Quoted 16 lines
diff -Nru
a/include/asm-i386/string.hb/include/asm-i386/string.hinclude/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
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.
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 incache_flusharray():[...]
Quoted 19 lines
diff -Nru
a/include/asm-i386/string.hb/include/asm-i386/string.hinclude/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/
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
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
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
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
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
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.hb/include/asm-i386/string.hinclude/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"
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.