[05/11] Improve generic strrchr

  * string/strrchr.c: Use haszero.h.
---
 string/strrchr.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 56 insertions(+), 11 deletions(-)
  

As for strchr and and strnlen, I think default strrchr can be changed 
use already optimized symbols:

--
#ifndef STRRCHR
# define STRRCHR strrchr
#endif

/* Find the last occurrence of C in S.  */
char *
STRRCHR (const char *s, int int_c)
{
  return __memrchr (s, int_c, strlen (s) + 1);
}
--

On 17/12/2016 04:57, Richard Henderson wrote:
>      * string/strrchr.c: Use haszero.h.
> ---
>  string/strrchr.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++----------
>  1 file changed, 56 insertions(+), 11 deletions(-)
> 
> diff --git a/string/strrchr.c b/string/strrchr.c
> index a07457e..bea7d76 100644
> --- a/string/strrchr.c
> +++ b/string/strrchr.c
> @@ -16,6 +16,10 @@
>     <http://www.gnu.org/licenses/>.  */
>  
>  #include <string.h>
> +#include <stdint.h>
> +#include <haszero.h>
> +#include <whichzero.h>
> +#include <extractbyte.h>
>  
>  #undef strrchr
>  
> @@ -25,25 +29,66 @@
>  
>  /* Find the last occurrence of C in S.  */
>  char *
> -STRRCHR (const char *s, int c)
> +STRRCHR (const char *s, int int_c)
>  {
> -  const char *found, *p;
> +  const unsigned char *found_c = NULL, *ptr_c;
> +  const unsigned long int *found_w = NULL, *ptr_w;
> +  unsigned long int longword, repeated_c;
> +  uintptr_t i, align;
> +  unsigned char c;
>  
> -  c = (unsigned char) c;
> +  c = (unsigned char) int_c;
> +  ptr_c = (const unsigned char *) s;
>  
> -  /* Since strchr is fast, we use it rather than the obvious loop.  */
> +  /* Handle the first few characters by reading one character at a time.
> +     Do this until CHAR_PTR is aligned on a longword boundary.  */
> +  align = -(uintptr_t)ptr_c % sizeof(longword);
> +  for (i = 0; i < align; ++i, ++ptr_c)
> +    {
> +      unsigned char this_c = *ptr_c;
> +      if (this_c == c)
> +        found_c = ptr_c;
> +      if (this_c == '\0')
> +        goto done;
> +    }
> +
> +  /* Set up a longword, each of whose bytes is C.  */
> +  repeated_c = (-1ul / 0xff) * c;
> +
> +  /* Search words for C.  At this point, merely record the last word
> +     that contained the character.  Stop when we find EOS.  */
> +  ptr_w = (const unsigned long int *) ptr_c;
> +  while (1)
> +    {
> +      longword = *ptr_w;
> +      if (haszero (longword))
> +	break;
> +      if (haszero (longword ^ repeated_c))
> +	found_w = ptr_w;
> +      ptr_w++;
> +    }
>  
> -  if (c == '\0')
> -    return strchr (s, '\0');
> +  /* Check to see if we've got C in the last longword.  */
> +  i = whichzero2 (longword, longword ^ repeated_c);
> +  if (extractbyte (longword, i) == c)
> +    found_w = ptr_w;
>  
> -  found = NULL;
> -  while ((p = strchr (s, c)) != NULL)
> +  /* If we found a word containing C, go back and search it byte by byte.  */
> +  if (found_w)
>      {
> -      found = p;
> -      s = p + 1;
> +      ptr_c = (const unsigned char *) found_w;
> +      for (i = 0; i < sizeof(longword); ++i, ++ptr_c)
> +	{
> +	  unsigned char this_c = *ptr_c;
> +	  if (this_c == c)
> +	    found_c = ptr_c;
> +	  if (this_c == '\0')
> +	    break;
> +	}
>      }
>  
> -  return (char *) found;
> + done:
> +  return (char *) found_c;
>  }
>  
>  #ifdef weak_alias
>
  

On 12/20/2016 04:50 AM, Adhemerval Zanella wrote:
> /* Find the last occurrence of C in S.  */
> char *
> STRRCHR (const char *s, int int_c)
> {
>   return __memrchr (s, int_c, strlen (s) + 1);
> }

Do we really want to touch the memory twice for such a common function?


r~
  

On 20/12/2016 15:20, Richard Henderson wrote:
> On 12/20/2016 04:50 AM, Adhemerval Zanella wrote:
>> /* Find the last occurrence of C in S.  */
>> char *
>> STRRCHR (const char *s, int int_c)
>> {
>>   return __memrchr (s, int_c, strlen (s) + 1);
>> }
> 
> Do we really want to touch the memory twice for such a common function?

It really depends of the pattern strrchr is usually issue with.  If last
occurrence is near end of string it can be potentially faster, however
if it is not the case it can potentially touch memory twice indeed.
Using current benchtest I am seeing exactly this:

  - first two loops where string size way larger than character position
    the simplified implementation is slower (about 60% in some cases);

  - third loop show some gains from size 2 and larger (about 15%)

  - it shows also some gain on 4th loop and forward where is acts 
    basically as strlen (since it searches for 0).