uboot optimize memmove

PATCH New Andy Green 4 participants 9 messages Jul 26, 2013 – Jul 29, 2013

Subsystems (2)

Library code Generic string library

lore

Share & tools

lore

Andy Green

author

2013-07-26 06:53 UTC #0 lore raw

PATCH 1/1 uboot optimize memmove

While studying the reason why kernel copy from NOR was so slow on our platform, I realized U-Boot is pulling it from 32-bit NOR in 8-bit chunks needlessly.

bootm uses memmove() and that just takes the approach by default to move u8s around.

This optimization prefers memcpy() implementation (done mostly in 32-bit reads and writes) if there's no overlap in source and dest, resulting in a huge speedup on our platform (480ms copy from 32-bit NOR ---> 140ms)

Signed-off-by Andy Green <[email protected]>

---
 lib/string.c |   10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

lib/string.c +9 -1

index c3ad055..96d66e0 100644
@@ -542,13 +542,21 @@ void * memmove(void * dest,const void *src,size_t count)
 	if (src == dest)
 		return dest;
 
-	if (dest <= src) {
+	if (dest < src) {
+
+		if ((unsigned long)dest + count <= (unsigned long)src)
+			return memcpy(dest, src, count);
+
 		tmp = (char *) dest;
 		s = (char *) src;
 		while (count--)
 			*tmp++ = *s++;
 		}
 	else {
+
+		if ((unsigned long)src + count <= (unsigned long)dest)
+			return memcpy(dest, src, count);
+
 		tmp = (char *) dest + count;
 		s = (char *) src + count;
 		while (count--)

Wolfgang Denk

2013-07-26 12:58 UTC #1 lore raw

PATCH 1/1 uboot optimize memmove

Dear Andy Green,

Quoted 9 lines · In message <[email protected]> you wrote:

While studying the reason why kernel copy from NOR was so slow on our platform, I realized U-Boot is pulling it from 32-bit NOR in 8-bit chunks needlessly.
bootm uses memmove() and that just takes the approach by default to move u8s around.
This optimization prefers memcpy() implementation (done mostly in 32-bit reads and writes) if there's no overlap in source and dest, resulting in a huge speedup on our platform (480ms copy from 32-bit NOR ---> 140ms)

Sorry, but I dislike your patch.

Instead of making assumptions on the performance of memcpy() and adding the overhead of an additional function call (which can be expensive especially for short copy operations) it would make more sense to pull the "copy a word at a time" code from memcpy() into memmove(), too.

On the other hand - if you really care about performance, then why do you not make sure that you provide optimized implementations for such functions and consequently #define __HAVE_ARCH_MEMMOVE (and __HAVE_ARCH_MEMCPY) ?

Best regards,

Wolfgang Denk

Signature · 5 lines

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
It is dangerous to be sincere unless you are also stupid.
                                                - George Bernard Shaw

Andy Green

author

2013-07-26 13:42 UTC #2 lore raw

PATCH 1/1 uboot optimize memmove

Quoted 6 lines · Wolfgang Denk

Dear Andy Green,
Quoted 3 lines · In message <[email protected]> you wrote:
While studying the reason why kernel copy from NOR was so slow on our platform, I realized U-Boot is pulling it from 32-bit NOR in 8-bit chunks needlessly.

Quoted 8 lines

Quoted 6 lines
bootm uses memmove() and that just takes the approach by default to move u8s around.
This optimization prefers memcpy() implementation (done mostly in 32-bit reads and writes) if there's no overlap in source and dest, resulting in a huge speedup on our platform (480ms copy from 32-bit NOR ---> 140ms)
Sorry, but I dislike your patch.

I see.

Quoted 1 line

Instead of making assumptions on the performance of memcpy() and

As I wrote, I measured the performance and got a very big gain, it's > 3x faster on my setup to use memcpy() then default memmove().

By calling that an "assumption" you're saying that there exist platforms where 32-bit linear memmove() is slower than doing it with 8-bit actions?

Quoted 2 lines

adding the overhead of an additional function call (which can be expensive especially for short copy operations) it would make more

I am not sure U-Boot is really in the business of doing small memmoves, but okay...

Quoted 4 lines

sense to pull the "copy a word at a time" code from memcpy() into memmove(), too.
On the other hand - if you really care about performance, then why do

I spent several hours figuring out why our NOR boot performance was terrible.... it's because this default memmove code is gloriously inefficient for all cases.

If you like it like that, no worries.

Quoted 3 lines

you not make sure that you provide optimized implementations for such functions and consequently #define __HAVE_ARCH_MEMMOVE (and __HAVE_ARCH_MEMCPY) ?

Yes I found these afterwards... performance is slightly better than memcpy() thanks to Nicolas Pitre it seems. The U-Boot config for the platform we have didn't know about them, it's much better with them.

After I wrote this patch it was also pointed out by Will Newton at Linaro that we have Neon accelerated memcpy lying around with BSD license....

https://launchpad.net/cortex-strings

however for my purposes NOR boot is working good enough with the ARCH versions.

-Andy

Quoted 10 lines

Best regards,
Wolfgang Denk
--
DENX Software Engineering GmbH, MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de It is dangerous to be sincere unless you are also stupid.
- George Bernard Shaw

Wolfgang Denk

2013-07-26 19:06 UTC #3 lore raw

PATCH 1/1 uboot optimize memmove

Dear Andy Green,

Quoted 5 lines · In message <CAAfg0W7p6rvvaMqsKsC09yQnfPod08YDTbeh_MQrz6n+B4iyYA@mail.gmail.com>…

Quoted 2 lines
Instead of making assumptions on the performance of memcpy() and
As I wrote, I measured the performance and got a very big gain, it's 3x faster on my setup to use memcpy() then default memmove().

Yes, in your single test case of copying a Linux kernel image, i. e. a multi-megabyte file.

Quoted 3 lines

By calling that an "assumption" you're saying that there exist platforms where 32-bit linear memmove() is slower than doing it with 8-bit actions?

No. I said you should not assume that memcpy() is always faster than memmove(); a system may use optiomized versions of either.

Quoted 5 lines

Quoted 2 lines
adding the overhead of an additional function call (which can be expensive especially for short copy operations) it would make more
I am not sure U-Boot is really in the business of doing small memmoves, but okay...

It's easy to avoid this overhead, and also get rid of the restrictions you built into it (otimizong only the non-overlapping case), so if we touch that code, we should do it right.

Quoted 10 lines

Quoted 4 lines
sense to pull the "copy a word at a time" code from memcpy() into memmove(), too.
On the other hand - if you really care about performance, then why do
I spent several hours figuring out why our NOR boot performance was terrible.... it's because this default memmove code is gloriously inefficient for all cases.
If you like it like that, no worries.

Don't twist my words. I asked for a different, better implementation, that's all.

Best regards,

Wolfgang Denk

Signature · 5 lines

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
The only time the world beats a path to your door is when you are  in
the bathroom.

Andy Green

author

2013-07-28 23:39 UTC #4 lore raw

PATCH 1/1 uboot optimize memmove

Dear Wolfgang Denk,

Quoted 11 lines · Wolfgang Denk

Dear Andy Green,
Quoted 5 lines · In message <CAAfg0W7p6rvvaMqsKsC09yQnfPod08YDTbeh_MQrz6n+B4iyYA@mail.gmail.com>…
Quoted 2 lines
Instead of making assumptions on the performance of memcpy() and
As I wrote, I measured the performance and got a very big gain, it's 3x faster on my setup to use memcpy() then default memmove().
Yes, in your single test case of copying a Linux kernel image, i. e. a multi-megabyte file.

That "single test case" of copying a "multi-megabyte file" is the reason d'etre of a bootloader...if it doesn't perform well doing that then it's a problem.

However I agree the alternative arch-specific implementation for ARM is pretty good, so this is kind of moot.

Since I traced my problem to here I "fixed" it there, but that actual problem was were using the default implementations at all (the config was inherited)..

Quoted 6 lines

Quoted 3 lines
By calling that an "assumption" you're saying that there exist platforms where 32-bit linear memmove() is slower than doing it with 8-bit actions?
No. I said you should not assume that memcpy() is always faster than memmove(); a system may use optiomized versions of either.

I did not assume that, I looked at your code for both and saw, and proved, that using 32-bit operations for mass move actions is going to perform better than using 8-bit operations.

That's not something you can write off as an "assumption", it's a fact.

Quoted 9 lines

Quoted 5 lines
Quoted 2 lines
adding the overhead of an additional function call (which can be expensive especially for short copy operations) it would make more
I am not sure U-Boot is really in the business of doing small memmoves, but okay...
It's easy to avoid this overhead, and also get rid of the restrictions you built into it (otimizong only the non-overlapping case), so if we touch that code, we should do it right.

Given that code should perferably never be used, maybe it should print a warning like "Using default memory ops" and leave it like it is. The problem is not correctness just inefficiency.

Quoted 5 lines

Quoted 5 lines
Quoted 4 lines
sense to pull the "copy a word at a time" code from memcpy() into memmove(), too.
On the other hand - if you really care about performance, then why do

Quoted 8 lines

Quoted 5 lines
I spent several hours figuring out why our NOR boot performance was terrible.... it's because this default memmove code is gloriously inefficient for all cases.
If you like it like that, no worries.
Don't twist my words. I asked for a different, better implementation, that's all.

Unfortunately I'm only looking at it because it made trouble, and we now no longer use that code.

For the use-case I'm studying (very fast overall boot) it still may make sense to implement the NEON stuff in which case I'll offer a patch for that.

-Andy

Quoted 11 lines

Best regards,
Wolfgang Denk
--
DENX Software Engineering GmbH, MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de The only time the world beats a path to your door is when you are in the bathroom.

Wolfgang Denk

2013-07-29 08:03 UTC #5 lore raw

PATCH 1/1 uboot optimize memmove

Dear Andy Green,

Quoted 4 lines · In message <CAAfg0W4wXdRafRcHvrNVNnkCGd3EvJfNujuzUsjQXgW=WmCU+w@mail.gmail.com>…

Given that code should perferably never be used, maybe it should print a warning like "Using default memory ops" and leave it like it is. The problem is not correctness just inefficiency.

Agreed. You found a problem, and a way to improve it. All this is perfectly fine. I just didn't like your implementation, and rather suggest to copy the 32-bit-copy loop as used in the current memcpy() code and use it also in memmove().

I'm looking forward to seeing your patch v2 with such an improved implementation. Thanks in advance.

Best regards,

Wolfgang Denk

Signature · 5 lines

DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
The biggest difference between time and space is that you can't reuse
time.                                                 - Merrick Furst

Dirk Behme

2013-07-29 08:28 UTC #6 lore raw

PATCH 1/1 uboot optimize memmove

In reply to Andy Green

Quoted 1 line · Andy Green

On 26 July 2013 20:58, Wolfgang Denk <[email protected]> wrote:

...

Quoted 8 lines

Quoted 3 lines
you not make sure that you provide optimized implementations for such functions and consequently #define __HAVE_ARCH_MEMMOVE (and __HAVE_ARCH_MEMCPY) ?
Yes I found these afterwards... performance is slightly better than memcpy() thanks to Nicolas Pitre it seems. The U-Boot config for the platform we have didn't know about them, it's much better with them.

Quoted 7 lines

After I wrote this patch it was also pointed out by Will Newton at Linaro that we have Neon accelerated memcpy lying around with BSD license....
https://launchpad.net/cortex-strings
however for my purposes NOR boot is working good enough with the ARCH versions.

I've had a look to

https://launchpad.net/cortex-strings

and there downloaded

https://launchpad.net/cortex-strings/trunk/2013.01/+download/cortex-strings-1.0-2013.01.tar.bz2

(from the green download button on the right side).

The README mentions

src/neon contains NEON based routines for AArch32.

but the cortex-strings-1.0-2013.01.tar.bz2 seems to contain an empty src/neon directory. Is this intended?

Best regards

Dirk

Andy Green

author

2013-07-29 08:44 UTC #7 lore raw

PATCH 1/1 uboot optimize memmove

Looping Will...

Quoted 33 lines · Dirk Behme

Quoted 2 lines · Andy Green
On 26 July 2013 20:58, Wolfgang Denk <[email protected]> wrote:
...
Quoted 10 lines
Quoted 4 lines
you not make sure that you provide optimized implementations for such functions and consequently #define __HAVE_ARCH_MEMMOVE (and __HAVE_ARCH_MEMCPY) ?
Yes I found these afterwards... performance is slightly better than memcpy() thanks to Nicolas Pitre it seems. The U-Boot config for the platform we have didn't know about them, it's much better with them.
Quoted 8 lines
After I wrote this patch it was also pointed out by Will Newton at Linaro that we have Neon accelerated memcpy lying around with BSD license....
https://launchpad.net/cortex-strings
however for my purposes NOR boot is working good enough with the ARCH versions.
I've had a look to
https://launchpad.net/cortex-strings
and there downloaded
https://launchpad.net/cortex-strings/trunk/2013.01/+download/cortex-strings-1.0-2013.01.tar.bz2

Quoted 8 lines

(from the green download button on the right side).
The README mentions
src/neon contains NEON based routines for AArch32.
but the cortex-strings-1.0-2013.01.tar.bz2 seems to contain an empty src/neon directory. Is this intended?

I don't know... I agree that dir is empty... Will, do you know the story? I found nice-looking ones in reference/newlib but I don't think they're NEON.

-Andy

Quoted 5 lines

Best regards
Dirk

Will Newton

2013-07-29 10:34 UTC #8 lore raw

PATCH 1/1 uboot optimize memmove

Quoted 40 lines · Andy Green

Looping Will...
Quoted 37 lines · Dirk Behme
Quoted 2 lines · Andy Green
On 26 July 2013 20:58, Wolfgang Denk <[email protected]> wrote:
...
Quoted 10 lines
Quoted 4 lines
you not make sure that you provide optimized implementations for such functions and consequently #define __HAVE_ARCH_MEMMOVE (and __HAVE_ARCH_MEMCPY) ?
Yes I found these afterwards... performance is slightly better than memcpy() thanks to Nicolas Pitre it seems. The U-Boot config for the platform we have didn't know about them, it's much better with them.
Quoted 8 lines
After I wrote this patch it was also pointed out by Will Newton at Linaro that we have Neon accelerated memcpy lying around with BSD license....
https://launchpad.net/cortex-strings
however for my purposes NOR boot is working good enough with the ARCH versions.
I've had a look to
https://launchpad.net/cortex-strings
and there downloaded
https://launchpad.net/cortex-strings/trunk/2013.01/+download/cortex-strings-1.0-2013.01.tar.bz2
(from the green download button on the right side).
The README mentions

Quoted 8 lines

Quoted 4 lines
src/neon contains NEON based routines for AArch32.
but the cortex-strings-1.0-2013.01.tar.bz2 seems to contain an empty src/neon directory. Is this intended?
I don't know... I agree that dir is empty... Will, do you know the story? I found nice-looking ones in reference/newlib but I don't think they're NEON.

The fast memcpy code is in src/linaro-a9/memcpy.S. The directory structure pre-dates my involvement with the project so I cannot explain it completely. ;-)

--
Will Newton
Toolchain Working Group, Linaro