[PATCH] Use strlen when searching for a nul char

[PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
the end of a string, however it is not the most efficient way of doing so.
Strlen is a simpler operation which is significantly faster on larger inputs
(eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).


ChangeLog:
2016-02-25  Wilco Dijkstra  <wdijkstr@arm.com>

	* string/bits/string2.h (strchr): Remove define.
	(__rawmemchr): Add new define.
	(rawmemchr): Likewise.

--

diff --git a/string/bits/string2.h b/string/bits/string2.h
index bebd158c5ff0f7bd7d9e4a4c3e120cd45b6e2143..f34fedb170352eaca0ed784ca6e76d7bbbfaefc2 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -62,14 +62,15 @@
 #endif
 
 
-#ifndef _HAVE_STRING_ARCH_strchr
+#ifndef _HAVE_STRING_ARCH_rawmemchr
 extern void *__rawmemchr (const void *__s, int __c);
-# if __GNUC_PREREQ (3, 2)
-#  define strchr(s, c) \
-  (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)	      \
-		  && (c) == '\0'					      \
-		  ? (char *) __rawmemchr (s, c)				      \
-		  : __builtin_strchr (s, c)))
+# define __rawmemchr(s, c) \
+    (__extension__ ({ char *__s = (char *)(s);		\
+      __builtin_constant_p (c) && (c) == '\0'		\
+      ? (void *)(__s + strlen (__s))			\
+      : __rawmemchr (__s, (c));}))
+# ifdef __USE_GNU
+#  define rawmemchr(s,c) __rawmemchr ((s), (c))
 # endif
 #endif

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

ping

________________________________________
From: Wilco Dijkstra
Sent: 25 February 2016 13:04
To: 'GNU C Library'
Cc: nd
Subject: [PATCH] Use strlen when searching for a nul char

Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
the end of a string, however it is not the most efficient way of doing so.
Strlen is a simpler operation which is significantly faster on larger inputs
(eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).


ChangeLog:
2016-02-25  Wilco Dijkstra  <wdijkstr@arm.com>

        * string/bits/string2.h (strchr): Remove define.
        (__rawmemchr): Add new define.
        (rawmemchr): Likewise.

--

diff --git a/string/bits/string2.h b/string/bits/string2.h
index bebd158c5ff0f7bd7d9e4a4c3e120cd45b6e2143..f34fedb170352eaca0ed784ca6e76d7bbbfaefc2 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -62,14 +62,15 @@
 #endif


-#ifndef _HAVE_STRING_ARCH_strchr
+#ifndef _HAVE_STRING_ARCH_rawmemchr
 extern void *__rawmemchr (const void *__s, int __c);
-# if __GNUC_PREREQ (3, 2)
-#  define strchr(s, c) \
-  (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)              \
-                 && (c) == '\0'                                              \
-                 ? (char *) __rawmemchr (s, c)                               \
-                 : __builtin_strchr (s, c)))
+# define __rawmemchr(s, c) \
+    (__extension__ ({ char *__s = (char *)(s);         \
+      __builtin_constant_p (c) && (c) == '\0'          \
+      ? (void *)(__s + strlen (__s))                   \
+      : __rawmemchr (__s, (c));}))
+# ifdef __USE_GNU
+#  define rawmemchr(s,c) __rawmemchr ((s), (c))
 # endif
 #endif

Re: [PATCH] Use strlen when searching for a nul char

[Mike Frysinger]

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

On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
> the end of a string, however it is not the most efficient way of doing so.
> Strlen is a simpler operation which is significantly faster on larger inputs
> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).

will there be a change in GCC to also detect rawmemchr(s,'\0') ?

even then, since this optimization isn't showing up until GCC7, shouldn't
we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
strlen before falling back ?
-mike

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] Use strlen when searching for a nul char

[Adhemerval Zanella]

On 19-04-2016 14:57, Mike Frysinger wrote:
> On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
>> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
>> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
>> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
>> the end of a string, however it is not the most efficient way of doing so.
>> Strlen is a simpler operation which is significantly faster on larger inputs
>> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).
> 
> will there be a change in GCC to also detect rawmemchr(s,'\0') ?
> 
> even then, since this optimization isn't showing up until GCC7, shouldn't
> we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
> strlen before falling back ?
> -mike
> 

Personally I am not very found on the string2.h header and its intrinsic logic,
which contains optimization logic that might not be true depending of the
architecture string optimization.

Also for the specific optimization does we really need to keep pushing for 
these specific inline implementations? I would prefer a much simple string2.h
header than a convoluted one we have today.

Re: [PATCH] Use strlen when searching for a nul char

[Mike Frysinger]

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

On 19 Apr 2016 17:27, Adhemerval Zanella wrote:
> On 19-04-2016 14:57, Mike Frysinger wrote:
> > On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
> >> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
> >> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
> >> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
> >> the end of a string, however it is not the most efficient way of doing so.
> >> Strlen is a simpler operation which is significantly faster on larger inputs
> >> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).
> > 
> > will there be a change in GCC to also detect rawmemchr(s,'\0') ?
> > 
> > even then, since this optimization isn't showing up until GCC7, shouldn't
> > we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
> > strlen before falling back ?
> 
> Personally I am not very found on the string2.h header and its intrinsic logic,
> which contains optimization logic that might not be true depending of the
> architecture string optimization.
> 
> Also for the specific optimization does we really need to keep pushing for 
> these specific inline implementations? I would prefer a much simple string2.h
> header than a convoluted one we have today.

i don't have a real opinion on keeping it or just tossing the whole
thing out.  but if we keep it, i think we should be adding the bits
that make sense (like my question above) rather than half-assing it.
-mike

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] Use strlen when searching for a nul char

[Adhemerval Zanella]

On 19-04-2016 17:51, Mike Frysinger wrote:
> On 19 Apr 2016 17:27, Adhemerval Zanella wrote:
>> On 19-04-2016 14:57, Mike Frysinger wrote:
>>> On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
>>>> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
>>>> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
>>>> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
>>>> the end of a string, however it is not the most efficient way of doing so.
>>>> Strlen is a simpler operation which is significantly faster on larger inputs
>>>> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).
>>>
>>> will there be a change in GCC to also detect rawmemchr(s,'\0') ?
>>>
>>> even then, since this optimization isn't showing up until GCC7, shouldn't
>>> we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
>>> strlen before falling back ?
>>
>> Personally I am not very found on the string2.h header and its intrinsic logic,
>> which contains optimization logic that might not be true depending of the
>> architecture string optimization.
>>
>> Also for the specific optimization does we really need to keep pushing for 
>> these specific inline implementations? I would prefer a much simple string2.h
>> header than a convoluted one we have today.
> 
> i don't have a real opinion on keeping it or just tossing the whole
> thing out.  but if we keep it, i think we should be adding the bits
> that make sense (like my question above) rather than half-assing it.
> -mike
> 

My idea is to cleanup the header bit a bit until we could just removei
it. That's why I would prefer to not add any more optimization bits
on it.

Re: [PATCH] Use strlen when searching for a nul char

[Mike Frysinger]

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

On 19 Apr 2016 18:01, Adhemerval Zanella wrote:
> On 19-04-2016 17:51, Mike Frysinger wrote:
> > On 19 Apr 2016 17:27, Adhemerval Zanella wrote:
> >> On 19-04-2016 14:57, Mike Frysinger wrote:
> >>> On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
> >>>> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
> >>>> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
> >>>> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
> >>>> the end of a string, however it is not the most efficient way of doing so.
> >>>> Strlen is a simpler operation which is significantly faster on larger inputs
> >>>> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).
> >>>
> >>> will there be a change in GCC to also detect rawmemchr(s,'\0') ?
> >>>
> >>> even then, since this optimization isn't showing up until GCC7, shouldn't
> >>> we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
> >>> strlen before falling back ?
> >>
> >> Personally I am not very found on the string2.h header and its intrinsic logic,
> >> which contains optimization logic that might not be true depending of the
> >> architecture string optimization.
> >>
> >> Also for the specific optimization does we really need to keep pushing for 
> >> these specific inline implementations? I would prefer a much simple string2.h
> >> header than a convoluted one we have today.
> > 
> > i don't have a real opinion on keeping it or just tossing the whole
> > thing out.  but if we keep it, i think we should be adding the bits
> > that make sense (like my question above) rather than half-assing it.
> 
> My idea is to cleanup the header bit a bit until we could just removei
> it. That's why I would prefer to not add any more optimization bits
> on it.

if everyone agrees on that direction, then slowly culling it WFM
-mike

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

 Mike Frysinger wrote:
> On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
>> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
>> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
>> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
>> the end of a string, however it is not the most efficient way of doing so.
>> Strlen is a simpler operation which is significantly faster on larger inputs
>> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).
>
> will there be a change in GCC to also detect rawmemchr(s,'\0') ?

I wasn't planning to add it - GCC doesn't currently have it as a builtin so support
would need to be added first. It's unclear how often rawmemchr is used
elsewhere and what percentage is for finding the end of a string.

> even then, since this optimization isn't showing up until GCC7, shouldn't
> we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
> strlen before falling back ?

If it is common to use an old GCC to build a new GLIBC for a distro then adding
strchr->strlen with a PREREQ would be useful. But if one typically first builds GCC7
and then GLIBC with that then it would not matter.

An alternative would be fixup uses in GLIBC so it doesn't rely on header or GCC
optimizations to do the obvious.

Wilco

Re: [PATCH] Use strlen when searching for a nul char

[Mike Frysinger]

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

On 19 Apr 2016 22:03, Wilco Dijkstra wrote:
>  Mike Frysinger wrote:
> > On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
> >> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
> >> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
> >> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
> >> the end of a string, however it is not the most efficient way of doing so.
> >> Strlen is a simpler operation which is significantly faster on larger inputs
> >> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).
> >
> > will there be a change in GCC to also detect rawmemchr(s,'\0') ?
> 
> I wasn't planning to add it - GCC doesn't currently have it as a builtin so support
> would need to be added first. It's unclear how often rawmemchr is used
> elsewhere and what percentage is for finding the end of a string.
> 
> > even then, since this optimization isn't showing up until GCC7, shouldn't
> > we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
> > strlen before falling back ?
> 
> If it is common to use an old GCC to build a new GLIBC for a distro then adding
> strchr->strlen with a PREREQ would be useful. But if one typically first builds GCC7
> and then GLIBC with that then it would not matter.

the issue isn't what version of gcc is used to build glibc.  this is an
installed header, and we made guarantees that the installed headers work
with much older versions of gcc at runtime.  those guarantees don't hard
extend to pure-optimizations, but typically we wait much longer for those
versions to cycle out of common use.  dropping code that requires gcc7
(which doesn't even exist yet) doesn't fall into that bucket.
-mike

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

Mike Frysinger wrote:
> the issue isn't what version of gcc is used to build glibc.  this is an
> installed header, and we made guarantees that the installed headers work
> with much older versions of gcc at runtime.  those guarantees don't hard
> extend to pure-optimizations, but typically we wait much longer for those
> versions to cycle out of common use.  dropping code that requires gcc7
> (which doesn't even exist yet) doesn't fall into that bucket.

OK, here is the patch with the old define left in:

diff --git a/string/bits/string2.h b/string/bits/string2.h
index 80987602f34ded483854bcea86dabd5b81e42a18..62edc93b0f04249a504078caeee8fca192e91df8 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -60,13 +60,25 @@
 
 #ifndef _HAVE_STRING_ARCH_strchr
 extern void *__rawmemchr (const void *__s, int __c);
-#  define strchr(s, c) \
+# define strchr(s, c) \
   (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)	      \
 		  && (c) == '\0'					      \
 		  ? (char *) __rawmemchr (s, c)				      \
 		  : __builtin_strchr (s, c)))
 #endif
 
+#ifndef _HAVE_STRING_ARCH_rawmemchr
+extern void *__rawmemchr (const void *__s, int __c);
+# define __rawmemchr(s, c) \
+    (__extension__ ({ char *__s = (char *)(s);		\
+      __builtin_constant_p (c) && (c) == '\0'		\
+      ? (void *)(__s + strlen (__s))			\
+      : __rawmemchr (__s, (c));}))
+# ifdef __USE_GNU
+#  define rawmemchr(s,c) __rawmemchr ((s), (c))
+# endif
+#endif
+
 
 /* Copy SRC to DEST, returning pointer to final NUL byte.  */
 #ifdef __USE_GNU

Re: [PATCH] Use strlen when searching for a nul char

[Mike Frysinger]

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

On 20 Apr 2016 14:50, Wilco Dijkstra wrote:
>  #ifndef _HAVE_STRING_ARCH_strchr
>  extern void *__rawmemchr (const void *__s, int __c);
> -#  define strchr(s, c) \
> +# define strchr(s, c) \
>    (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)	      \
>  		  && (c) == '\0'					      \
>  		  ? (char *) __rawmemchr (s, c)				      \
>  		  : __builtin_strchr (s, c)))
>  #endif
>  
> +#ifndef _HAVE_STRING_ARCH_rawmemchr
> +extern void *__rawmemchr (const void *__s, int __c);
> +# define __rawmemchr(s, c) \
> +    (__extension__ ({ char *__s = (char *)(s);		\
> +      __builtin_constant_p (c) && (c) == '\0'		\
> +      ? (void *)(__s + strlen (__s))			\
> +      : __rawmemchr (__s, (c));}))
> +# ifdef __USE_GNU
> +#  define rawmemchr(s,c) __rawmemchr ((s), (c))
> +# endif
> +#endif

this relies on _HAVE_STRING_ARCH_strchr & _HAVE_STRING_ARCH_rawmemchr
being in sync in order for the strchr->strlen rewrite.  should we just
do the strlen change in strchr itself too ?
-mike

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

On 19 Apr 2016 18:01, Adhemerval Zanella wrote:
> On 19-04-2016 17:51, Mike Frysinger wrote:
> > On 19 Apr 2016 17:27, Adhemerval Zanella wrote:
> >> On 19-04-2016 14:57, Mike Frysinger wrote:
> >>> On 25 Feb 2016 13:04, Wilco Dijkstra wrote:
> >>>> Remove the strchr (s, '\0') to rawmemchr optimization as using rawmemchr is
> >>>> a bad idea - I have a patch to add strchr (s, '\0') -> strlen to GCC7.
> >>>> Like strchr (s, '\0'), rawmemchr (s, '\0') appears a common idiom for finding
> >>>> the end of a string, however it is not the most efficient way of doing so.
> >>>> Strlen is a simpler operation which is significantly faster on larger inputs
> >>>> (eg. on x86 strlen is 50% faster than rawmemchr on strings of 1KB).
> >>>
> >>> will there be a change in GCC to also detect rawmemchr(s,'\0') ?
> >>>
> >>> even then, since this optimization isn't showing up until GCC7, shouldn't
> >>> we keep some logic here ?  i.e. transform strchr/rawmemchr(s, '\0') into
> >>> strlen before falling back ?
> >>
> >> Personally I am not very found on the string2.h header and its intrinsic logic,
> >> which contains optimization logic that might not be true depending of the
> >> architecture string optimization.
> >>
> >> Also for the specific optimization does we really need to keep pushing for 
> >> these specific inline implementations? I would prefer a much simple string2.h
> >> header than a convoluted one we have today.
> > 
> > i don't have a real opinion on keeping it or just tossing the whole
> > thing out.  but if we keep it, i think we should be adding the bits
> > that make sense (like my question above) rather than half-assing it.
> 
> My idea is to cleanup the header bit a bit until we could just removei
> it. That's why I would prefer to not add any more optimization bits
> on it.

The latest string.h is already a lot smaller, and it should be feasible to get rid of
it this release. However it means removing some optimizations as not all are
useful enough to move to string.h (and/or be added to GCC):

The strdup case with a string literal is likely so rare and the possible speedup
by inlining memcpy so small (compared to the overhead of malloc) that removing
it can't make any difference.

The __strsep_*/__strok_* inlines are unlikely beneficial if we ensure small match
strings are special cased in the strsep/strtok code (which is already much faster
with the improved strpbrk and strspn).

The strncmp inline doesn't appear generally useful - do people really accidentally
write strncmp (s, "abc", 2)??? The strcmp one could be useful but it's better done
inside GCC based on target preferences and whether it is an equality comparison.

That leaves mostly defines like this:

#ifndef _HAVE_STRING_ARCH_strncpy
# define strncpy(dest, src, n) __builtin_strncpy (dest, src, n)
#endif

I believe these have no benefit so can be removed completely.

If we can agree on this then string2.h can be removed completely!

Wilco

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

Mike Frysinger wrote:
> this relies on _HAVE_STRING_ARCH_strchr & _HAVE_STRING_ARCH_rawmemchr
> being in sync in order for the strchr->strlen rewrite.  should we just
> do the strlen change in strchr itself too ?

If a target only defines _HAVE_STRING_ARCH_rawmemchr then presumably
it supports a fast rawmemchr, so it might be expected that strchr defers to rawmemchr
as it does today rather than using strlen.

If a target only defines _HAVE_STRING_ARCH_strchr then rawmemchr
would still use strlen, which is fine.

Wilco

>  #ifndef _HAVE_STRING_ARCH_strchr
>  extern void *__rawmemchr (const void *__s, int __c);
> -#  define strchr(s, c) \
> +# define strchr(s, c) \
>    (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)            \
>                 && (c) == '\0'                                              \
>                 ? (char *) __rawmemchr (s, c)                               \
>                 : __builtin_strchr (s, c)))
>  #endif
>
> +#ifndef _HAVE_STRING_ARCH_rawmemchr
> +extern void *__rawmemchr (const void *__s, int __c);
> +# define __rawmemchr(s, c) \
> +    (__extension__ ({ char *__s = (char *)(s);               \
> +      __builtin_constant_p (c) && (c) == '\0'                \
> +      ? (void *)(__s + strlen (__s))                 \
> +      : __rawmemchr (__s, (c));}))
> +# ifdef __USE_GNU
> +#  define rawmemchr(s,c) __rawmemchr ((s), (c))
> +# endif
> +#endif

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

ping

________________________________________
From: Wilco Dijkstra
Sent: 20 April 2016 15:50
To: Mike Frysinger
Cc: 'GNU C Library'; nd
Subject: Re: [PATCH] Use strlen when searching for a nul char

Mike Frysinger wrote:
> the issue isn't what version of gcc is used to build glibc.  this is an
> installed header, and we made guarantees that the installed headers work
> with much older versions of gcc at runtime.  those guarantees don't hard
> extend to pure-optimizations, but typically we wait much longer for those
> versions to cycle out of common use.  dropping code that requires gcc7
> (which doesn't even exist yet) doesn't fall into that bucket.

OK, here is the patch with the old define left in:

diff --git a/string/bits/string2.h b/string/bits/string2.h
index 80987602f34ded483854bcea86dabd5b81e42a18..62edc93b0f04249a504078caeee8fca192e91df8 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -60,13 +60,25 @@

 #ifndef _HAVE_STRING_ARCH_strchr
 extern void *__rawmemchr (const void *__s, int __c);
-#  define strchr(s, c) \
+# define strchr(s, c) \
   (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)              \
                  && (c) == '\0'                                              \
                  ? (char *) __rawmemchr (s, c)                               \
                  : __builtin_strchr (s, c)))
 #endif

+#ifndef _HAVE_STRING_ARCH_rawmemchr
+extern void *__rawmemchr (const void *__s, int __c);
+# define __rawmemchr(s, c) \
+    (__extension__ ({ char *__s = (char *)(s);         \
+      __builtin_constant_p (c) && (c) == '\0'          \
+      ? (void *)(__s + strlen (__s))                   \
+      : __rawmemchr (__s, (c));}))
+# ifdef __USE_GNU
+#  define rawmemchr(s,c) __rawmemchr ((s), (c))
+# endif
+#endif
+

 /* Copy SRC to DEST, returning pointer to final NUL byte.  */
 #ifdef __USE_GNU

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

ping

________________________________________
From: Wilco Dijkstra
Sent: 20 April 2016 15:50
To: Mike Frysinger
Cc: 'GNU C Library'; nd
Subject: Re: [PATCH] Use strlen when searching for a nul char

Mike Frysinger wrote:
> the issue isn't what version of gcc is used to build glibc.  this is an
> installed header, and we made guarantees that the installed headers work
> with much older versions of gcc at runtime.  those guarantees don't hard
> extend to pure-optimizations, but typically we wait much longer for those
> versions to cycle out of common use.  dropping code that requires gcc7
> (which doesn't even exist yet) doesn't fall into that bucket.

OK, here is the patch with the old define left in:

diff --git a/string/bits/string2.h b/string/bits/string2.h
index 80987602f34ded483854bcea86dabd5b81e42a18..62edc93b0f04249a504078caeee8fca192e91df8 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -60,13 +60,25 @@

 #ifndef _HAVE_STRING_ARCH_strchr
 extern void *__rawmemchr (const void *__s, int __c);
-#  define strchr(s, c) \
+# define strchr(s, c) \
   (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)              \
                  && (c) == '\0'                                              \
                  ? (char *) __rawmemchr (s, c)                               \
                  : __builtin_strchr (s, c)))
 #endif

+#ifndef _HAVE_STRING_ARCH_rawmemchr
+extern void *__rawmemchr (const void *__s, int __c);
+# define __rawmemchr(s, c) \
+    (__extension__ ({ char *__s = (char *)(s);         \
+      __builtin_constant_p (c) && (c) == '\0'          \
+      ? (void *)(__s + strlen (__s))                   \
+      : __rawmemchr (__s, (c));}))
+# ifdef __USE_GNU
+#  define rawmemchr(s,c) __rawmemchr ((s), (c))
+# endif
+#endif
+

 /* Copy SRC to DEST, returning pointer to final NUL byte.  */
 #ifdef __USE_GNU

Re: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

ping

________________________________________
From: Wilco Dijkstra
Sent: 20 April 2016 15:50
To: Mike Frysinger
Cc: 'GNU C Library'; nd
Subject: Re: [PATCH] Use strlen when searching for a nul char

Mike Frysinger wrote:
> the issue isn't what version of gcc is used to build glibc.  this is an
> installed header, and we made guarantees that the installed headers work
> with much older versions of gcc at runtime.  those guarantees don't hard
> extend to pure-optimizations, but typically we wait much longer for those
> versions to cycle out of common use.  dropping code that requires gcc7
> (which doesn't even exist yet) doesn't fall into that bucket.

OK, here is the patch with the old define left in:

diff --git a/string/bits/string2.h b/string/bits/string2.h
index 80987602f34ded483854bcea86dabd5b81e42a18..62edc93b0f04249a504078caeee8fca192e91df8 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -60,13 +60,25 @@

 #ifndef _HAVE_STRING_ARCH_strchr
 extern void *__rawmemchr (const void *__s, int __c);
-#  define strchr(s, c) \
+# define strchr(s, c) \
   (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)              \
                  && (c) == '\0'                                              \
                  ? (char *) __rawmemchr (s, c)                               \
                  : __builtin_strchr (s, c)))
 #endif

+#ifndef _HAVE_STRING_ARCH_rawmemchr
+extern void *__rawmemchr (const void *__s, int __c);
+# define __rawmemchr(s, c) \
+    (__extension__ ({ char *__s = (char *)(s);         \
+      __builtin_constant_p (c) && (c) == '\0'          \
+      ? (void *)(__s + strlen (__s))                   \
+      : __rawmemchr (__s, (c));}))
+# ifdef __USE_GNU
+#  define rawmemchr(s,c) __rawmemchr ((s), (c))
+# endif
+#endif
+

 /* Copy SRC to DEST, returning pointer to final NUL byte.  */
 #ifdef __USE_GNU

RE: [PATCH] Use strlen when searching for a nul char

[Joseph Myers]

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

On Wed, 7 Oct 2015, Wilco Dijkstra wrote:

> > I agree; I'd rather discourage the addition of such optimizations as
> > inlines in glibc unless they depend on information that's inherently not
> > available to GCC (e.g. properties of architecture-specific function
> > implementations in glibc).  As I said before in
> > <https://sourceware.org/ml/libc-alpha/2015-06/msg00146.html> the aim
> > should be to make the GNU system as a whole as good as possible.
> 
> Does this mean we no longer care about supporting older GCC versions
> efficiently in GLIBC?

We expect people caring about microoptimizations to use current tool 
versions.

> Ie. can we remove bits/string2.h and just do a trivial implementation of
> the inlines in string/string-inlines.c?

See the discussion starting at 
<https://sourceware.org/ml/libc-alpha/2015-05/msg00526.html>.  We could 
remove optimizations only relevant to old compilers (say pre-4.1 or 
pre-4.3, potentially pre-4.6 if that actually means significant cleanup), 
yes.

Note this does *not* automatically mean completely removing the header - 
for example, code mapping __func to __builtin_func may still be relevant, 
at least when building glibc, so you need to be careful that the code you 
remove really is dead with modern GCC.  And you need to allow for the x86 
version of string-inlines.c as well.  See my reviews of Ondøej's patches 
<https://sourceware.org/ml/libc-alpha/2015-05/msg00770.html> and 
<https://sourceware.org/ml/libc-alpha/2015-05/msg00772.html>.

-- 
Joseph S. Myers
joseph@codesourcery.com

RE: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

> Joseph Myers wrote:
> On Wed, 7 Oct 2015, pinskia@gmail.com wrote:
> 
> > > On Oct 7, 2015, at 7:30 AM, Wilco Dijkstra <wdijkstr@arm.com> wrote:
> > >
> > > Expand strchr (s, '\0') in C/C++ to use strlen. This is faster on most
> > > targets as strlen is a simpler function. Passes GLIBC tests. I'm
> > > planning to do the same for strrchr, strchrnul and rawmemchr in future
> > > patches as people frequently use all of these to find the end of a
> > > string.
> > >
> > > OK for commit?
> >
> > Shouldn't this also be an optimization inside gcc if not already?
> 
> I agree; I'd rather discourage the addition of such optimizations as
> inlines in glibc unless they depend on information that's inherently not
> available to GCC (e.g. properties of architecture-specific function
> implementations in glibc).  As I said before in
> <https://sourceware.org/ml/libc-alpha/2015-06/msg00146.html> the aim
> should be to make the GNU system as a whole as good as possible.

Does this mean we no longer care about supporting older GCC versions
efficiently in GLIBC?

Ie. can we remove bits/string2.h and just do a trivial implementation of
the inlines in string/string-inlines.c?

> (And please accompany performance claims such as "faster on most targets"
> with figures from the benchtests or a reason it's hard to produce such
> figures.  In this case I think the transformation could be justified for
> GCC as something architecture-independent without specific performance
> claims - strlen being inherently simpler because it only ever has to
> search for 0 bytes, so it should never be asymptotically slower than the
> alternative and may be faster.)

I did benchmark it of course, however the existing benchmarks don't address
constant arguments at all. Strlen is a good 2x faster than strchr on Cortex-A57
for larger sizes (for really small sizes strchr is sometimes better but that
just shows that strlen could be further improved for small sizes).

Wilco

Re: [PATCH] Use strlen when searching for a nul char

[Andreas Schwab]

Joseph Myers <joseph@codesourcery.com> writes:

> (And please accompany performance claims such as "faster on most targets" 
> with figures from the benchtests or a reason it's hard to produce such 
> figures.  In this case I think the transformation could be justified for 
> GCC as something architecture-independent without specific performance 
> claims - strlen being inherently simpler because it only ever has to 
> search for 0 bytes, so it should never be asymptotically slower than the 
> alternative and may be faster.)

On the debit side you have to keep the value of the pointer around in
order to add it afterwards.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Use strlen when searching for a nul char

[Joseph Myers]

On Wed, 7 Oct 2015, pinskia@gmail.com wrote:

> > On Oct 7, 2015, at 7:30 AM, Wilco Dijkstra <wdijkstr@arm.com> wrote:
> > 
> > Expand strchr (s, '\0') in C/C++ to use strlen. This is faster on most 
> > targets as strlen is a simpler function. Passes GLIBC tests. I'm 
> > planning to do the same for strrchr, strchrnul and rawmemchr in future 
> > patches as people frequently use all of these to find the end of a 
> > string.
> > 
> > OK for commit?
> 
> Shouldn't this also be an optimization inside gcc if not already?

I agree; I'd rather discourage the addition of such optimizations as 
inlines in glibc unless they depend on information that's inherently not 
available to GCC (e.g. properties of architecture-specific function 
implementations in glibc).  As I said before in 
<https://sourceware.org/ml/libc-alpha/2015-06/msg00146.html> the aim 
should be to make the GNU system as a whole as good as possible.

(And please accompany performance claims such as "faster on most targets" 
with figures from the benchtests or a reason it's hard to produce such 
figures.  In this case I think the transformation could be justified for 
GCC as something architecture-independent without specific performance 
claims - strlen being inherently simpler because it only ever has to 
search for 0 bytes, so it should never be asymptotically slower than the 
alternative and may be faster.)

-- 
Joseph S. Myers
joseph@codesourcery.com

RE: [PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

> pinskia@gmail.com wrote:
> > On Oct 7, 2015, at 7:30 AM, Wilco Dijkstra <wdijkstr@arm.com> wrote:
> >
> > Expand strchr (s, '\0') in C/C++ to use strlen. This is faster on most targets as strlen is
> a
> > simpler function. Passes GLIBC tests. I'm planning to do the same for strrchr, strchrnul and
> > rawmemchr in future patches as people frequently use all of these to find the end of a
> string.
> >
> > OK for commit?
> 
> Shouldn't this also be an optimization inside gcc if not already?

Absolutely, GCC is missing many of these simple optimizations.

Wilco

Re: [PATCH] Use strlen when searching for a nul char

[pinskia]

> On Oct 7, 2015, at 7:30 AM, Wilco Dijkstra <wdijkstr@arm.com> wrote:
> 
> Expand strchr (s, '\0') in C/C++ to use strlen. This is faster on most targets as strlen is a
> simpler function. Passes GLIBC tests. I'm planning to do the same for strrchr, strchrnul and
> rawmemchr in future patches as people frequently use all of these to find the end of a string.
> 
> OK for commit?

Shouldn't this also be an optimization inside gcc if not already?

Thanks,
Andrew

> 
> ChangeLog:
> 2015-10-07  Wilco Dijkstra  wdijkstr@arm.com
> 
>    * string/string.h (strchr): Use strlen when searching for nul char.
>    * string/bits/string.h (strchr): Remove define.
> 
> --
> string/bits/string2.h | 19 -------------------
> string/string.h       | 17 +++++++++++++++++
> 2 files changed, 17 insertions(+), 19 deletions(-)
> 
> diff --git a/string/bits/string2.h b/string/bits/string2.h
> index 7645176..db6457e 100644
> --- a/string/bits/string2.h
> +++ b/string/bits/string2.h
> @@ -387,25 +387,6 @@ __mempcpy_small (void *__dest, char __src1,
> # endif
> #endif
> 
> -
> -/* Return pointer to C in S.  */
> -#ifndef _HAVE_STRING_ARCH_strchr
> -extern void *__rawmemchr (const void *__s, int __c);
> -# if __GNUC_PREREQ (3, 2)
> -#  define strchr(s, c) \
> -  (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)          \
> -          && (c) == '\0'                          \
> -          ? (char *) __rawmemchr (s, c)                      \
> -          : __builtin_strchr (s, c)))
> -# else
> -#  define strchr(s, c) \
> -  (__extension__ (__builtin_constant_p (c) && (c) == '\0'              \
> -          ? (char *) __rawmemchr (s, c)                      \
> -          : strchr (s, c)))
> -# endif
> -#endif
> -
> -
> /* Copy SRC to DEST.  */
> #if (!defined _HAVE_STRING_ARCH_strcpy && !__GNUC_PREREQ (3, 0)) \
>     || defined _FORCE_INLINES
> diff --git a/string/string.h b/string/string.h
> index 3ab7103..599f2db 100644
> --- a/string/string.h
> +++ b/string/string.h
> @@ -217,12 +217,16 @@ extern const char *strchr (const char *__s, int __c)
> __extern_always_inline char *
> strchr (char *__s, int __c) __THROW
> {
> +  if (__builtin_constant_p (__c) && __c == '\0')
> +    return __s + __builtin_strlen ((const char *) __s);
>   return __builtin_strchr (__s, __c);
> }
> 
> __extern_always_inline const char *
> strchr (const char *__s, int __c) __THROW
> {
> +  if (__builtin_constant_p (__c) && __c == '\0')
> +    return __s + __builtin_strlen (__s);
>   return __builtin_strchr (__s, __c);
> }
> # endif
> @@ -230,6 +234,19 @@ strchr (const char *__s, int __c) __THROW
> #else
> extern char *strchr (const char *__s, int __c)
>      __THROW __attribute_pure__ __nonnull ((1));
> +
> +# if defined __OPTIMIZE__ && defined __extern_always_inline \
> +    && __GNUC_PREREQ (3,2) && !defined _FORCE_INLINES        \
> +    && !defined _HAVE_STRING_ARCH_strchr
> +__extern_always_inline char *
> +strchr (const char *__s, int __c)
> +{
> +  if (__builtin_constant_p (__c) && __c == '\0')
> +    return (char *)__s + __builtin_strlen (__s);
> +  return __builtin_strchr (__s, __c);
> +}
> +#endif
> +
> #endif
> /* Find the last occurrence of C in S.  */
> #ifdef __CORRECT_ISO_CPP_STRING_H_PROTO
> -- 
> 1.9.1
> 
> 
> 

[PATCH] Use strlen when searching for a nul char

[Wilco Dijkstra]

Expand strchr (s, '\0') in C/C++ to use strlen. This is faster on most targets as strlen is a
simpler function. Passes GLIBC tests. I'm planning to do the same for strrchr, strchrnul and
rawmemchr in future patches as people frequently use all of these to find the end of a string.

OK for commit?

ChangeLog:
2015-10-07  Wilco Dijkstra  wdijkstr@arm.com

	* string/string.h (strchr): Use strlen when searching for nul char.
	* string/bits/string.h (strchr): Remove define.

--
 string/bits/string2.h | 19 -------------------
 string/string.h       | 17 +++++++++++++++++
 2 files changed, 17 insertions(+), 19 deletions(-)

diff --git a/string/bits/string2.h b/string/bits/string2.h
index 7645176..db6457e 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -387,25 +387,6 @@ __mempcpy_small (void *__dest, char __src1,
 # endif
 #endif
 
-
-/* Return pointer to C in S.  */
-#ifndef _HAVE_STRING_ARCH_strchr
-extern void *__rawmemchr (const void *__s, int __c);
-# if __GNUC_PREREQ (3, 2)
-#  define strchr(s, c) \
-  (__extension__ (__builtin_constant_p (c) && !__builtin_constant_p (s)	      \
-		  && (c) == '\0'					      \
-		  ? (char *) __rawmemchr (s, c)				      \
-		  : __builtin_strchr (s, c)))
-# else
-#  define strchr(s, c) \
-  (__extension__ (__builtin_constant_p (c) && (c) == '\0'		      \
-		  ? (char *) __rawmemchr (s, c)				      \
-		  : strchr (s, c)))
-# endif
-#endif
-
-
 /* Copy SRC to DEST.  */
 #if (!defined _HAVE_STRING_ARCH_strcpy && !__GNUC_PREREQ (3, 0)) \
     || defined _FORCE_INLINES
diff --git a/string/string.h b/string/string.h
index 3ab7103..599f2db 100644
--- a/string/string.h
+++ b/string/string.h
@@ -217,12 +217,16 @@ extern const char *strchr (const char *__s, int __c)
 __extern_always_inline char *
 strchr (char *__s, int __c) __THROW
 {
+  if (__builtin_constant_p (__c) && __c == '\0')
+    return __s + __builtin_strlen ((const char *) __s);
   return __builtin_strchr (__s, __c);
 }
 
 __extern_always_inline const char *
 strchr (const char *__s, int __c) __THROW
 {
+  if (__builtin_constant_p (__c) && __c == '\0')
+    return __s + __builtin_strlen (__s);
   return __builtin_strchr (__s, __c);
 }
 # endif
@@ -230,6 +234,19 @@ strchr (const char *__s, int __c) __THROW
 #else
 extern char *strchr (const char *__s, int __c)
      __THROW __attribute_pure__ __nonnull ((1));
+
+# if defined __OPTIMIZE__ && defined __extern_always_inline \
+    && __GNUC_PREREQ (3,2) && !defined _FORCE_INLINES	    \
+    && !defined _HAVE_STRING_ARCH_strchr
+__extern_always_inline char *
+strchr (const char *__s, int __c)
+{
+  if (__builtin_constant_p (__c) && __c == '\0')
+    return (char *)__s + __builtin_strlen (__s);
+  return __builtin_strchr (__s, __c);
+}
+#endif
+
 #endif
 /* Find the last occurrence of C in S.  */
 #ifdef __CORRECT_ISO_CPP_STRING_H_PROTO
-- 
1.9.1