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.

--
  

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
  

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.
  

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
  

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.
  

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
  

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
  

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
  

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