[PATCH] Improve performance of strncpy

[PATCH] Improve performance of strncpy

[Wilco Dijkstra]

[-- Attachment #1: Type: text/plain, Size: 395 bytes --]

Hi,

This patch improves strncpy performance by using memset to clear memory after the string when the
buffer is much larger than the copied string. This is better as memset is significantly faster than
a simple byte-loop. On bench-strncpy it is ~25% faster.

ChangeLog:
2014-08-20  Wilco Dijkstra  <wdijkstr@arm.com>

	* string/strncpy.c (strncpy): Improve performance by using memset.

[-- Attachment #2: Improve-performance-of-strncpy.txt --]
[-- Type: text/plain, Size: 523 bytes --]

---
 string/strncpy.c |    9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/string/strncpy.c b/string/strncpy.c
index 0915e03..604417c 100644
--- a/string/strncpy.c
+++ b/string/strncpy.c
@@ -78,9 +78,12 @@ STRNCPY (char *s1, const char *s2, size_t n)
   while (c != '\0');
 
  zero_fill:
-  do
-    *++s1 = '\0';
-  while (--n > 0);
+  if (n >= 8)
+    memset (s1 + 1, '\0', n);
+  else
+    do
+      *++s1 = '\0';
+    while (--n > 0);
 
   return s;
 }
-- 
1.7.9.5

Re: [PATCH] Improve performance of strncpy

[Adhemerval Zanella]

On 20-08-2014 09:44, Wilco Dijkstra wrote:
> Hi,
>
> This patch improves strncpy performance by using memset to clear memory after the string when the
> buffer is much larger than the copied string. This is better as memset is significantly faster than
> a simple byte-loop. On bench-strncpy it is ~25% faster.

Hi, the patch looks ok. I also pushed a similar modification for powerpc based on same idea. 

>
> ChangeLog:
> 2014-08-20  Wilco Dijkstra  <wdijkstr@arm.com>
>
> 	* string/strncpy.c (strncpy): Improve performance by using memset.
> ---
>  string/strncpy.c |    9 ++++++---
>  1 file changed, 6 insertions(+), 3 deletions(-)
>
> diff --git a/string/strncpy.c b/string/strncpy.c
> index 0915e03..604417c 100644
> --- a/string/strncpy.c
> +++ b/string/strncpy.c
> @@ -78,9 +78,12 @@ STRNCPY (char *s1, const char *s2, size_t n)
>    while (c != '\0');
>  
>   zero_fill:
> -  do
> -    *++s1 = '\0';
> -  while (--n > 0);
> +  if (n >= 8)
> +    memset (s1 + 1, '\0', n);
> +  else
> +    do
> +      *++s1 = '\0';
> +    while (--n > 0);

I wonder if this test is really worth, my opinion is just to keep it simple
and just call memset on both 'goto' in loop and after 'last_chars'.

>  
>    return s;
>  }
> -- 1.7.9.5

RE: [PATCH] Improve performance of strncpy

[Wilco Dijkstra]

Adhemerval Zanella wrote:
> Hi, the patch looks ok. I also pushed a similar modification for powerpc based on same idea. 

>   zero_fill:
> -  do
> -    *++s1 = '\0';
> -  while (--n > 0);
> +  if (n >= 8)
> +    memset (s1 + 1, '\0', n);
> +  else
> +    do
> +      *++s1 = '\0';
> +    while (--n > 0);

> I wonder if this test is really worth, my opinion is just to keep it simple
> and just call memset on both 'goto' in loop and after 'last_chars'.

Yes, you're right, I timed it and there is actually little difference, while
the code is now even simpler. New version below (not attaching results in bad
characters due to various mail servers changing line endings).

OK for commit?

---
 string/strncpy.c |   14 +++++---------
 1 file changed, 5 insertions(+), 9 deletions(-)

diff --git a/string/strncpy.c b/string/strncpy.c
index 0915e03..d5fa5be 100644
--- a/string/strncpy.c
+++ b/string/strncpy.c
@@ -57,10 +57,10 @@ STRNCPY (char *s1, const char *s2, size_t n)
 	  if (--n4 == 0)
 	    goto last_chars;
 	}
-      n = n - (s1 - s) - 1;
-      if (n == 0)
-	return s;
-      goto zero_fill;
+      s1++;
+      n = n - (s1 - s);
+      memset (s1, '\0', n);
+      return s;
     }
 
  last_chars:
@@ -77,11 +77,7 @@ STRNCPY (char *s1, const char *s2, size_t n)
     }
   while (c != '\0');
 
- zero_fill:
-  do
-    *++s1 = '\0';
-  while (--n > 0);
-
+  memset (s1 + 1, '\0', n);
   return s;
 }
 libc_hidden_builtin_def (strncpy)
-- 
1.7.9.5

Re: [PATCH] Improve performance of strncpy

[Florian Weimer]

On 09/10/2014 05:21 PM, Wilco Dijkstra wrote:
> Yes, you're right, I timed it and there is actually little difference, while
> the code is now even simpler. New version below (not attaching results in bad
> characters due to various mail servers changing line endings).
>
> OK for commit?

I think you could simplify it down to strnlen, memcpy, and memset.

-- 
Florian Weimer / Red Hat Product Security

Re: [PATCH] Improve performance of strncpy

[Rich Felker]

On Wed, Sep 10, 2014 at 07:34:40PM +0200, Florian Weimer wrote:
> On 09/10/2014 05:21 PM, Wilco Dijkstra wrote:
> >Yes, you're right, I timed it and there is actually little difference, while
> >the code is now even simpler. New version below (not attaching results in bad
> >characters due to various mail servers changing line endings).
> >
> >OK for commit?
> 
> I think you could simplify it down to strnlen, memcpy, and memset.

I don't think that's an improvement, at least not in the general case.
It involves iterating twice over the source string, which for long
strings could mean blowing the whole cache twice and fetching from
main memory twice. There's a good reason that string operations are
usually implemented to perform the copy and length computation
together in a single pass.

Rich

RE: [PATCH] Improve performance of strncpy

[Wilco Dijkstra]

> Rich Felker wrote:
> On Wed, Sep 10, 2014 at 07:34:40PM +0200, Florian Weimer wrote:
> > On 09/10/2014 05:21 PM, Wilco Dijkstra wrote:
> > >Yes, you're right, I timed it and there is actually little difference, while
> > >the code is now even simpler. New version below (not attaching results in bad
> > >characters due to various mail servers changing line endings).
> > >
> > >OK for commit?
> >
> > I think you could simplify it down to strnlen, memcpy, and memset.
> 
> I don't think that's an improvement, at least not in the general case.
> It involves iterating twice over the source string, which for long
> strings could mean blowing the whole cache twice and fetching from
> main memory twice. There's a good reason that string operations are
> usually implemented to perform the copy and length computation
> together in a single pass.
> 
> Rich

Few strings will be larger than the typical L1 size of 32KB. You're right
that it is best to do a single pass in a highly optimized implementation.
However the issue is that the C versions are so slow that even doing 2
passes will be significantly faster due to processing 8 bytes at a time - 
likely even if much larger than L1 (I'll check that).

The goal of these patches is to ensure the C string routines are quite
competitive out of the box, and benefit further when you add a few highly
optimized routines (eg. strlen/strcpy). That means new targets are not
forced to add optimized versions of all of the string routines in order to
get decent performance (as unfortunately is the case today).

Wilco

RE: [PATCH] Improve performance of strncpy

[Wilco Dijkstra]

> Rich Felker wrote:
> On Wed, Sep 10, 2014 at 07:34:40PM +0200, Florian Weimer wrote:
> > On 09/10/2014 05:21 PM, Wilco Dijkstra wrote:
> > >Yes, you're right, I timed it and there is actually little difference, while
> > >the code is now even simpler. New version below (not attaching results in bad
> > >characters due to various mail servers changing line endings).
> > >
> > >OK for commit?
> >
> > I think you could simplify it down to strnlen, memcpy, and memset.
> 
> I don't think that's an improvement, at least not in the general case.
> It involves iterating twice over the source string, which for long
> strings could mean blowing the whole cache twice and fetching from
> main memory twice. There's a good reason that string operations are
> usually implemented to perform the copy and length computation
> together in a single pass.

I did a quick experiment with strcpy as it's simpler. Replacing it 
with memcpy (d, s, strlen (s) + 1) is 3 times faster even on strings 
of 16Mbytes! Perhaps more surprisingly, it has similar performance on 
these huge strings as an optimized strcpy.

So the results are pretty clear, if you don't have a super optimized
strcpy, then strlen+memcpy is the best way to do it.

Wilco

Re: [PATCH] Improve performance of strncpy

[Ondřej Bílka]

On Thu, Sep 11, 2014 at 08:37:17PM +0100, Wilco Dijkstra wrote:
> > Rich Felker wrote:
> > On Wed, Sep 10, 2014 at 07:34:40PM +0200, Florian Weimer wrote:
> > > On 09/10/2014 05:21 PM, Wilco Dijkstra wrote:
> > > >Yes, you're right, I timed it and there is actually little difference, while
> > > >the code is now even simpler. New version below (not attaching results in bad
> > > >characters due to various mail servers changing line endings).
> > > >
> > > >OK for commit?
> > >
> > > I think you could simplify it down to strnlen, memcpy, and memset.
> > 
> > I don't think that's an improvement, at least not in the general case.
> > It involves iterating twice over the source string, which for long
> > strings could mean blowing the whole cache twice and fetching from
> > main memory twice. There's a good reason that string operations are
> > usually implemented to perform the copy and length computation
> > together in a single pass.
>
No that is what you think but never tested it. A problem is that in
strcpy you spend most of time in call that are at most 256 bytes large. 
And if you spend 99% of time in some path and you slow down it by 2% to
make case in with you spend 1% of time faster it is bad idea even if you
could make that 1% for free.

Give me name of linux package that regularly does strcpy of 32k+ strings, 
until then you should not focus on case that does not happen.

Anyway we talk about strncpy here, anybody that uses it does not care
about performance, its terrible by design, like write 64 byte string then do
useless zeroing of remaining 4032 bytes speaks for itself.

And as main usage is for fixed size buffers and these buffers are
typically less than 32k its even more dubious to optimize for large
sizes.

> I did a quick experiment with strcpy as it's simpler. Replacing it 
> with memcpy (d, s, strlen (s) + 1) is 3 times faster even on strings 
> of 16Mbytes! Perhaps more surprisingly, it has similar performance on 
> these huge strings as an optimized strcpy.
>
What architecture? This could also happen because memcpy has special 
case to handle large strings that speeds this up. Its something that I
tried in one-pass strcpy but it harms performance as overhead of checking
size is bigger than benefit of larger size.
 
> So the results are pretty clear, if you don't have a super optimized
> strcpy, then strlen+memcpy is the best way to do it.
> 
It is not that clear as you spend considerable amount of time on small
lenghts, what is important is constant overhead of strcpy startup.
However this needs platform specific tricks to decide which alternative
is fastest.

RE: [PATCH] Improve performance of strncpy

[Wilco Dijkstra]

> Ondřej Bílka wrote:
> On Thu, Sep 11, 2014 at 08:37:17PM +0100, Wilco Dijkstra wrote:
> > I did a quick experiment with strcpy as it's simpler. Replacing it
> > with memcpy (d, s, strlen (s) + 1) is 3 times faster even on strings
> > of 16Mbytes! Perhaps more surprisingly, it has similar performance on
> > these huge strings as an optimized strcpy.
> >
> What architecture? This could also happen because memcpy has special
> case to handle large strings that speeds this up. Its something that I
> tried in one-pass strcpy but it harms performance as overhead of checking
> size is bigger than benefit of larger size.

The 3x happens on all 3 ISAs I tried. On ARM the memcpy/strlen variant
even beats the optimized strcmp case for most sizes, on x64 it runs at
about 80% of the optimized strcpy for sizes above 4KB.

> > So the results are pretty clear, if you don't have a super optimized
> > strcpy, then strlen+memcpy is the best way to do it.
> >
> It is not that clear as you spend considerable amount of time on small
> lenghts, what is important is constant overhead of strcpy startup.
> However this needs platform specific tricks to decide which alternative
> is fastest.

The overheads are relatively small on modern cores. The memcpy/strlen
is always faster than the single loop for lengths larger than 8-16.

Wilco

RE: [PATCH] Improve performance of strncpy

[Wilco Dijkstra]

> Florian Weimer wrote:
> On 09/10/2014 05:21 PM, Wilco Dijkstra wrote:
> > Yes, you're right, I timed it and there is actually little difference, while
> > the code is now even simpler. New version below (not attaching results in bad
> > characters due to various mail servers changing line endings).
> >
> > OK for commit?
> 
> I think you could simplify it down to strnlen, memcpy, and memset.

I'll have a go at that in a follow-on patch. Something similar is possible with
strcpy and strncat which currently do byte-by-byte copies as well. Simplifying 
the code is certainly a nice benefit besides the performance gain on longer
strings.

Wilco

RE: [PATCH] Improve performance of strncpy

[Wilco Dijkstra]

Ping (there was some further discussion but I don't see an OK for this patch)

> -----Original Message-----
> From: Wilco Dijkstra [mailto:wdijkstr@arm.com]
> Sent: 10 September 2014 16:22
> To: 'azanella@linux.vnet.ibm.com'
> Cc: 'libc-alpha@sourceware.org'
> Subject: RE: [PATCH] Improve performance of strncpy
> 
> Adhemerval Zanella wrote:
> > Hi, the patch looks ok. I also pushed a similar modification for powerpc based on same idea.
> 
> >   zero_fill:
> > -  do
> > -    *++s1 = '\0';
> > -  while (--n > 0);
> > +  if (n >= 8)
> > +    memset (s1 + 1, '\0', n);
> > +  else
> > +    do
> > +      *++s1 = '\0';
> > +    while (--n > 0);
> 
> > I wonder if this test is really worth, my opinion is just to keep it simple
> > and just call memset on both 'goto' in loop and after 'last_chars'.
> 
> Yes, you're right, I timed it and there is actually little difference, while
> the code is now even simpler. New version below (not attaching results in bad
> characters due to various mail servers changing line endings).
> 
> OK for commit?
> 
> ---
>  string/strncpy.c |   14 +++++---------
>  1 file changed, 5 insertions(+), 9 deletions(-)
> 
> diff --git a/string/strncpy.c b/string/strncpy.c
> index 0915e03..d5fa5be 100644
> --- a/string/strncpy.c
> +++ b/string/strncpy.c
> @@ -57,10 +57,10 @@ STRNCPY (char *s1, const char *s2, size_t n)
>  	  if (--n4 == 0)
>  	    goto last_chars;
>  	}
> -      n = n - (s1 - s) - 1;
> -      if (n == 0)
> -	return s;
> -      goto zero_fill;
> +      s1++;
> +      n = n - (s1 - s);
> +      memset (s1, '\0', n);
> +      return s;
>      }
> 
>   last_chars:
> @@ -77,11 +77,7 @@ STRNCPY (char *s1, const char *s2, size_t n)
>      }
>    while (c != '\0');
> 
> - zero_fill:
> -  do
> -    *++s1 = '\0';
> -  while (--n > 0);
> -
> +  memset (s1 + 1, '\0', n);
>    return s;
>  }
>  libc_hidden_builtin_def (strncpy)
> --
> 1.7.9.5

Re: [PATCH] Improve performance of strncpy

[Ondřej Bílka]

On Fri, Oct 24, 2014 at 04:56:23PM +0100, Wilco Dijkstra wrote:
> Ping (there was some further discussion but I don't see an OK for this patch)
> 
Looks ok, any reason why not simplify it more to strnlen+memcpy+memset?

RE: [PATCH] Improve performance of strncpy

[Wilco Dijkstra]

> Ondřej Bílka wrote:
> On Fri, Oct 24, 2014 at 04:56:23PM +0100, Wilco Dijkstra wrote:
> > Ping (there was some further discussion but I don't see an OK for this patch)
> >
> Looks ok, any reason why not simplify it more to strnlen+memcpy+memset?

Well that is possible too. I benchmarked this and it is 1.7x on x64, and 2x
on AArch64 (compared to my patch). However it does seem to be mostly due to
the large strings, small strings are slower as you can see below. I don't
believe that bench-strncpy is a good benchmark as it only seems to test strings
of 0.5x, 1.0x and 2.0x the buffer size (none of which would be common in the
real world), do you happen to know a better strncpy benchmark?

                                strncpy_orig    strncpy
Length   16, n   16, alignment  1/ 1:   31.1694 60.0666
Length   16, n   16, alignment  1/ 1:   36.8311 60.0364
Length   16, n   16, alignment  1/ 2:   35.9034 60.0394
Length   16, n   16, alignment  2/ 1:   37.768  60.0356
Length    2, n    4, alignment  7/ 2:   60.9953 75.4958
Length    4, n    2, alignment  2/ 7:   19.6473 57.3082
Length    2, n    4, alignment  7/ 2:   57.9887 75.4963
Length    4, n    2, alignment  2/ 7:   21.8327 57.3139
...
Length  256, n  512, alignment  0/ 0:   423.878 193.744
Length 1024, n  512, alignment  0/ 0:   729.506 262.873
Length  256, n  512, alignment  2/ 4:   423.877 207.391
Length 1024, n  512, alignment  2/ 4:   728.664 273.792
Length  512, n 1024, alignment  0/ 0:   796.739 315.629
Length 2048, n 1024, alignment  0/ 0:   1425.05 479.289
Length  512, n 1024, alignment  1/ 6:   791.347 333.821
Length 2048, n 1024, alignment  1/ 6:   1428.08 493.005

Re: [PATCH] Improve performance of strncpy

[Ondřej Bílka]

On Thu, Nov 27, 2014 at 07:20:43PM -0000, Wilco Dijkstra wrote:
> > Ondřej Bílka wrote:
> > On Fri, Oct 24, 2014 at 04:56:23PM +0100, Wilco Dijkstra wrote:
> > > Ping (there was some further discussion but I don't see an OK for this patch)
> > >
> > Looks ok, any reason why not simplify it more to strnlen+memcpy+memset?
> 
> Well that is possible too. I benchmarked this and it is 1.7x on x64, and 2x
> on AArch64 (compared to my patch). However it does seem to be mostly due to
> the large strings, small strings are slower as you can see below. I don't
> believe that bench-strncpy is a good benchmark as it only seems to test strings
> of 0.5x, 1.0x and 2.0x the buffer size (none of which would be common in the
> real world), do you happen to know a better strncpy benchmark?
> 
Not yet, I tried to find use case but nothing on my computer calls it.

That is nice as strncpy function that should not be used at performance
sensitive code. A zero fill that standard requires is totally unnecesary
and even if you have good idea about buffer size you easily be 20%
faster by using strlen+memcpy+writing terminator.

A real problem is when you do estimate buffer well or do not carefully
read strncpy description. Then its easy to write code that is ten times
slower as strcpy copies ~64 byte string followed by zeroing remaining
4032 bytes of buffer.