Use strlen when searching for a nul char

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(-)

> 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
> 
> 
>

> 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

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 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.

> 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

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>.