optimalisation for strlcpy (lib/string.c)
Hi,
Like the other patch (by that other person), I think it is faster to not do a strlen first.
E.g. replace this:ize_t strlcpy(char *dest, const char *src, size_t size)
{
size_t ret = strlen(src);
if (size) {
size_t len = (ret >= size) ? size - 1 : ret;
memcpy(dest, src, len);
dest[len] = '\0';
}
return ret;
}
by this:
size_t strlcpy(char *dest, const char *src, size_t size)
{
char *tmp = dest;
for(;;)
{
*dest = *src;
if (!*src)
break;
if (--size == 0)
break;
dest++;
src++;
}
*dest = 0x00;
return dest - tmp;
}patch:
string-new.c 2006-12-10 22:22:08.000000000 +0100 renamed from string.c 2006-11-04 02:33:58.000000000 +0100 +16 -6
@@ -121,14 +121,24 @@ */ size_t strlcpy(char *dest, const char *src, size_t size) { - size_t ret = strlen(src); + char *tmp = dest; - if (size) { - size_t len = (ret >= size) ? size - 1 : ret; - memcpy(dest, src, len); - dest[len] = '\0'; + for(;;) + { + *dest = *src; + if (!*src) + break; + + if (--size == 0) + break; + + dest++; + src++; } - return ret; + + *dest = 0x00; + + return dest - tmp; } EXPORT_SYMBOL(strlcpy); #endif
I've tested the speed difference with this:
http://www.vanheusden.com/misc/kernel-strlcpy-opt-test.c
and the speed difference is quite a bit on a P4: 28% faster.
Signed-off by: Folkert van Heusden <[email protected]>
Folkert van Heusden
Signature · 4 lines
www.vanheusden.com/multitail - multitail is tail on steroids. multiple
windows, filtering, coloring, anything you can think of
----------------------------------------------------------------------
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.comQuoted 2 lines · Folkert van Heusden
Like the other patch (by that other person), I think it is faster to not do a strlen first.
Debatable. You've replaced a call to the highly-optimized memcpy function with a byte-by-byte copy. It's probably a wash performance wise (have you benchmarked?) and is certainly less clear.
-Mitch
Quoted 5 lines
Quoted 2 lines
Like the other patch (by that other person), I think it is faster to not do a strlen first.
Debatable. You've replaced a call to the highly-optimized memcpy function with a byte-by-byte copy. It's probably a wash performance wise (have you benchmarked?) and is certainly less clear.
I tested it outside the kernel.
The test source can be found here:
http://www.vanheusden.com/misc/kernel-strlcpy-opt-test.c
Folkert van Heusden
Signature · 3 lines
Feeling generous? -> http://www.vanheusden.com/wishlist.php ---------------------------------------------------------------------- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
Quoted 80 lines · Folkert van Heusden
Hi,
Like the other patch (by that other person), I think it is faster to not do a strlen first.
E.g. replace this:ize_tstrlcpy(char *dest, const char *src, size_t size){ size_t ret = strlen(src); if (size) { size_t len = (ret >= size) ? size - 1 : ret; memcpy(dest, src, len); dest[len] = '\0'; } return ret; } by this: size_t strlcpy(char *dest, const char *src, size_t size) { char *tmp = dest; for(;;) { *dest = *src; if (!*src) break; if (--size == 0) break; dest++; src++; } *dest = 0x00; return dest - tmp; }patch:
diff -uNrBbdlib/string.cstring-new.cstring-new.c 2006-12-10 22:22:08.000000000 +0100 renamed from string.c 2006-11-04 02:33:58.000000000 +0100 +16
-6@@ -121,14 +121,24 @@ */ size_t strlcpy(char *dest, const char *src, size_t size) { - size_t ret = strlen(src); + char *tmp = dest; - if (size) { - size_t len = (ret >= size) ? size - 1 : ret; - memcpy(dest, src, len); - dest[len] = '\0'; + for(;;) + { + *dest = *src; + if (!*src) + break; + + if (--size == 0) + break; + + dest++; + src++; } - return ret; + + *dest = 0x00; + + return dest - tmp; } EXPORT_SYMBOL(strlcpy); #endifI've tested the speed difference with this:
http://www.vanheusden.com/misc/kernel-strlcpy-opt-test.c
and the speed difference is quite a bit on a P4: 28% faster.
Quoted 4 lines
Signed-off by: Folkert van Heusden <[email protected]>
Folkert van Heusden
The two do not do exactly the same. The first one handles 'size == 0' (should not happen?) safely while the other does not.
Signature · 2 lines
Eyal Lebedinsky ([email protected]) <http://samba.org/eyal/> attach .zip as .dat
Quoted 23 lines
Quoted 23 lines
by this:
size_tstrlcpy(char *dest, const char *src, size_t size){ char *tmp = dest; for(;;) { *dest = *src; if (!*src) break; if (--size == 0) break; dest++; src++; } *dest = 0x00; return dest - tmp; }
Quoted 6 lines
Quoted 3 lines
I've tested the speed difference with this:
http://www.vanheusden.com/misc/kernel-strlcpy-opt-test.c
and the speed difference is quite a bit on a P4: 28% faster.The two do not do exactly the same. The first one handles 'size == 0' (should not happen?) safely while the other does not.
Ok, small change:
string-new.c 2006-12-10 23:02:26.000000000 +0100 renamed from string.c 2006-11-04 02:33:58.000000000 +0100 +19 -6
@@ -121,14 +122,27 @@ */ size_t strlcpy(char *dest, const char *src, size_t size) { - size_t ret = strlen(src); + char *tmp = dest; - if (size) { - size_t len = (ret >= size) ? size - 1 : ret; - memcpy(dest, src, len); - dest[len] = '\0'; + if (likeley(size > 0)) + { + for(;;) + { + *dest = *src; + if (unlikely(!*src)) + break; + + if (unlikely(--size == 0)) + break; + + dest++; + src++; } - return ret; + } + + *dest = 0x00; + + return dest - tmp; } EXPORT_SYMBOL(strlcpy); #endif
Folkert van Heusden
Signature · 4 lines
Ever wonder what is out there? Any alien races? Then please support the seti@home project: setiathome.ssl.berkeley.edu ---------------------------------------------------------------------- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
Quoted 26 lines · Folkert van Heusden
Hi,
Like the other patch (by that other person), I think it is faster to not do a strlen first.
...string-new.c 2006-12-10 22:22:08.000000000 +0100 renamed from string.c 2006-11-04 02:33:58.000000000 +0100 +9
-5@@ -121,14 +121,24 @@ */ size_t strlcpy(char *dest, const char *src, size_t size) { - size_t ret = strlen(src); + char *tmp = dest; - if (size) { - size_t len = (ret >= size) ? size - 1 : ret; - memcpy(dest, src, len); - dest[len] = '\0'; + for(;;) + { + *dest = *src; + if (!*src) + break; + + if (--size == 0) + break;
string-new.c 2006-12-10 22:22:08.000000000 +0100 line 141
Quoted 10 lines
string-new.c 2006-12-10 22:22:08.000000000 +0100 renamed from string.c 2006-11-04 02:33:58.000000000 +0100 +7
-1+ + dest++; + src++; } - return ret; + + *dest = 0x00; + + return dest - tmp;
Two bugs in your code:
- you copy a maximum of size bytes _plus_ \0
- size == 0 is no longer handled correctly
Quoted 4 lines
I've tested the speed difference with this:
http://www.vanheusden.com/misc/kernel-strlcpy-opt-test.c
and the speed difference is quite a bit on a P4: 28% faster.
...
My Athlon says:
org: 2.400000
new: 6.710000
IOW, your version is much slower.
But the main question is actually:
Does the performance of this function matter anywhere inside the kernel? Is strlcpy() used in any fast path?
If not, there's no point in trying to optimize it.
Quoted 1 line
Folkert van Heusden
cu
Adrian
Signature · 4 lines
"Is there not promise of rain?" Ling Tan asked suddenly out
of the darkness. There had been need of rain for many days.
"Only a promise," Lao Er said.
Pearl S. Buck - Dragon SeedHi, Adrian & Friends!
Quoted 2 lines
Quoted 2 lines
Like the other patch (by that other person), I think it is faster to not do a strlen first.
There are PowerPC architectures, where a strlen is a matter of a single instruction of the CPU.
Quote: "PowerPC 405 and 440 instruction sets offer the powerful Determine Left-Most Zero Byte (DLMZB) instruction."
That's propably hard to beat.
So, if we really want to speed up these things, we should write code which helps the compiler get that optimized instructions for us - by improving the code of strlen() i.e.
Reference:
http://www-03.ibm.com/chips/power/powerpc/newsletter/sep2003/ppc_process_at_work2.html
Greets,
Clemens Koller
_______________________________
R&D Imaging Devices
Anagramm GmbH
Rupert-Mayer-Str. 45/1
81379 Muenchen
Germany
http://www.anagramm-technology.com
Phone: +49-89-741518-50
Fax: +49-89-741518-19