[v2] Improve strsep

  This is version 2, rebased to be after the string2.h header changes
https://sourceware.org/ml/libc-alpha/2016-11/msg00853.html
(however like the earlier strtok patch there is no real dependency).

It cleans up the strsep implementation and improves performance.
Currently strsep calls strpbrk is is now a veneer to strcspn.  Calling
strcspn directly is faster.  Since it handles a delimiter string of size
1 as a special case, this is not needed in strsep itself.  Although this
means there is a slightly higher overhead if the delimiter size is 1,
all other cases are slightly faster.  The overall performance gain is 5-10%
on AArch64.

The string/bits/string2.h header contains optimizations for constant
delimiters of size 1-3.  Benchmarking these showed similar performance for
size 1 (since in all cases strchr/strchrnul is used), while size 2 and 3
can give up to 2x speedup for small input strings.  However if these cases
are common it seems much better to add this optimization to strcspn. 
So move these header optimizations to string-inlines.c.

Improve the strsep benchmark so that it actually benchmarks something.
The current version contains a delimiter character at every position in the
input string, so there is very little work to do, and the extremely inefficent
simple_strsep implementation appears fastest in every case.  The new version
has either no match in the input for the fail case and a match halfway in the
input for the success case.  The input is then restored so that each iteration
does exactly the same amount of work.  Reduce the number of testcases since
simple_strsep takes a lot of time now.

Passes GLIBC tests, OK for commit?

ChangeLog:
2015-11-23  Wilco Dijkstra  <wdijkstr@arm.com>

	* benchtests/bench-strsep.c (oldstrsep): Add old implementation.
	(do_one_test) Restore original string so iteration works.
	* string/string-inlines.c (do_test): Create better input strings.
	(test_main) Reduce number of testruns.
	* string/string-inlines.c (__old_strsep_1c): New function.
	(__old_strsep_2c): Likewise.
	(__old_strsep_3c): Likewise.
	* string/strsep.c (__strsep): Remove case of small delim string.
	Call strcspn directly rather than strpbrk.
	* string/bits/string2.h (__strsep): Remove define.
	(__strsep_1c): Remove.
	(__strsep_2c): Remove.
	(__strsep_3c): Remove.
	(strsep): Remove.

--
  

LGTM (I just replied to your older version and this one seems to have
corrected the remark I have made).

On 23/11/2016 17:07, Wilco Dijkstra wrote:
> This is version 2, rebased to be after the string2.h header changes
> https://sourceware.org/ml/libc-alpha/2016-11/msg00853.html
> (however like the earlier strtok patch there is no real dependency).
> 
> It cleans up the strsep implementation and improves performance.
> Currently strsep calls strpbrk is is now a veneer to strcspn.  Calling
> strcspn directly is faster.  Since it handles a delimiter string of size
> 1 as a special case, this is not needed in strsep itself.  Although this
> means there is a slightly higher overhead if the delimiter size is 1,
> all other cases are slightly faster.  The overall performance gain is 5-10%
> on AArch64.
> 
> The string/bits/string2.h header contains optimizations for constant
> delimiters of size 1-3.  Benchmarking these showed similar performance for
> size 1 (since in all cases strchr/strchrnul is used), while size 2 and 3
> can give up to 2x speedup for small input strings.  However if these cases
> are common it seems much better to add this optimization to strcspn. 
> So move these header optimizations to string-inlines.c.
> 
> Improve the strsep benchmark so that it actually benchmarks something.
> The current version contains a delimiter character at every position in the
> input string, so there is very little work to do, and the extremely inefficent
> simple_strsep implementation appears fastest in every case.  The new version
> has either no match in the input for the fail case and a match halfway in the
> input for the success case.  The input is then restored so that each iteration
> does exactly the same amount of work.  Reduce the number of testcases since
> simple_strsep takes a lot of time now.
> 
> Passes GLIBC tests, OK for commit?
> 
> ChangeLog:
> 2015-11-23  Wilco Dijkstra  <wdijkstr@arm.com>
> 
> 	* benchtests/bench-strsep.c (oldstrsep): Add old implementation.
> 	(do_one_test) Restore original string so iteration works.
> 	* string/string-inlines.c (do_test): Create better input strings.
> 	(test_main) Reduce number of testruns.
> 	* string/string-inlines.c (__old_strsep_1c): New function.
> 	(__old_strsep_2c): Likewise.
> 	(__old_strsep_3c): Likewise.
> 	* string/strsep.c (__strsep): Remove case of small delim string.
> 	Call strcspn directly rather than strpbrk.
> 	* string/bits/string2.h (__strsep): Remove define.
> 	(__strsep_1c): Remove.
> 	(__strsep_2c): Remove.
> 	(__strsep_3c): Remove.
> 	(strsep): Remove.
> 
> --
> diff --git a/benchtests/bench-strsep.c b/benchtests/bench-strsep.c
> index 70dbb377563232a43895abc940d396f2c65237c6..9e0c00d9f198776a3de4857446b82125566ba4b4 100644
> --- a/benchtests/bench-strsep.c
> +++ b/benchtests/bench-strsep.c
> @@ -49,10 +49,56 @@ simple_strsep (char **s1, char *s2)
>    return begin;
>  }
>  
> +char *
> +oldstrsep (char **stringp, const char *delim)
> +{
> +  char *begin, *end;
> +
> +  begin = *stringp;
> +  if (begin == NULL)
> +    return NULL;
> +
> +  /* A frequent case is when the delimiter string contains only one
> +     character.  Here we don't need to call the expensive `strpbrk'
> +     function and instead work using `strchr'.  */
> +  if (delim[0] == '\0' || delim[1] == '\0')
> +    {
> +      char ch = delim[0];
> +
> +      if (ch == '\0')
> +	end = NULL;
> +      else
> +	{
> +	  if (*begin == ch)
> +	    end = begin;
> +	  else if (*begin == '\0')
> +	    end = NULL;
> +	  else
> +	    end = strchr (begin + 1, ch);
> +	}
> +    }
> +  else
> +    /* Find the end of the token.  */
> +    end = strpbrk (begin, delim);
> +
> +  if (end)
> +    {
> +      /* Terminate the token and set *STRINGP past NUL character.  */
> +      *end++ = '\0';
> +      *stringp = end;
> +    }
> +  else
> +    /* No more delimiters; this is the last token.  */
> +    *stringp = NULL;
> +
> +  return begin;
> +}
> +
>  typedef char *(*proto_t) (const char **, const char *);
>  
>  IMPL (simple_strsep, 0)
>  IMPL (strsep, 1)
> +IMPL (oldstrsep, 2)
>  
>  static void
>  do_one_test (impl_t * impl, const char *s1, const char *s2)
> @@ -63,7 +109,10 @@ do_one_test (impl_t * impl, const char *s1, const char *s2)
>    TIMING_NOW (start);
>    for (i = 0; i < iters; ++i)
>      {
> -      CALL (impl, &s1, s2);
> +      const char *s1a = s1;
> +      CALL (impl, &s1a, s2);
> +      if (s1a != NULL)
> +	((char*)s1a)[-1] = '1';
>      }
>    TIMING_NOW (stop);
>  
> @@ -76,7 +125,7 @@ static void
>  do_test (size_t align1, size_t align2, size_t len1, size_t len2, int fail)
>  {
>    char *s2 = (char *) (buf2 + align2);
> -  static const char d[] = "1234567890abcdef";
> +  static const char d[] = "1234567891abcdef";
>  #define dl (sizeof (d) - 1)
>    char *ss2 = s2;
>    for (size_t l = len2; l > 0; l = l > dl ? l - dl : 0)
> @@ -92,24 +141,9 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2, int fail)
>    FOR_EACH_IMPL (impl, 0)
>    {
>      char *s1 = (char *) (buf1 + align1);
> -    if (fail)
> -      {
> -	char *ss1 = s1;
> -	for (size_t l = len1; l > 0; l = l > dl ? l - dl : 0)
> -	  {
> -	    size_t t = l > dl ? dl : l;
> -	    memcpy (ss1, d, t);
> -	    ++ss1[len2 > 7 ? 7 : len2 - 1];
> -	    ss1 += t;
> -	  }
> -      }
> -    else
> -      {
> -	memset (s1, '0', len1);
> -	memcpy (s1 + (len1 - len2) - 2, s2, len2);
> -	if ((len1 / len2) > 4)
> -	  memcpy (s1 + (len1 - len2) - (3 * len2), s2, len2);
> -      }
> +    memset (s1, '0', len1);
> +    if (!fail)
> +      s1[len1 / 2] = '1';
>      s1[len1] = '\0';
>      do_one_test (impl, s1, s2);
>    }
> @@ -127,7 +161,7 @@ test_main (void)
>    putchar ('\n');
>  
>    for (size_t klen = 2; klen < 32; ++klen)
> -    for (size_t hlen = 2 * klen; hlen < 16 * klen; hlen += klen)
> +    for (size_t hlen = 4 * klen; hlen < 8 * klen; hlen += klen)
>        {
>  	do_test (0, 0, hlen, klen, 0);
>  	do_test (0, 0, hlen, klen, 1);
> diff --git a/string/bits/string2.h b/string/bits/string2.h
> index 5acdb7866e4e70a6c3aa050b0427b31aed8943ec..03af22cc27a33c81f36d56ddc52fce0a5ea81ece 100644
> --- a/string/bits/string2.h
> +++ b/string/bits/string2.h
> @@ -118,96 +118,6 @@
>  #endif
>  
>  
> -#if !defined _HAVE_STRING_ARCH_strsep || defined _FORCE_INLINES
> -# ifndef _HAVE_STRING_ARCH_strsep
> -
> -extern char *__strsep_g (char **__stringp, const char *__delim);
> -#  define __strsep(s, reject) \
> -  __extension__								      \
> -  ({ char __r0, __r1, __r2;						      \
> -     (__builtin_constant_p (reject) && __string2_1bptr_p (reject)	      \
> -      && (__r0 = ((const char *) (reject))[0],				      \
> -	  ((const char *) (reject))[0] != '\0')				      \
> -      ? ((__r1 = ((const char *) (reject))[1],				      \
> -	 ((const char *) (reject))[1] == '\0')				      \
> -	 ? __strsep_1c (s, __r0)					      \
> -	 : ((__r2 = ((const char *) (reject))[2], __r2 == '\0')		      \
> -	    ? __strsep_2c (s, __r0, __r1)				      \
> -	    : (((const char *) (reject))[3] == '\0'			      \
> -	       ? __strsep_3c (s, __r0, __r1, __r2)			      \
> -	       : __strsep_g (s, reject))))				      \
> -      : __strsep_g (s, reject)); })
> -# endif
> -
> -__STRING_INLINE char *__strsep_1c (char **__s, char __reject);
> -__STRING_INLINE char *
> -__strsep_1c (char **__s, char __reject)
> -{
> -  char *__retval = *__s;
> -  if (__retval != NULL && (*__s = strchr (__retval, __reject)) != NULL)
> -    *(*__s)++ = '\0';
> -  return __retval;
> -}
> -
> -__STRING_INLINE char *__strsep_2c (char **__s, char __reject1, char __reject2);
> -__STRING_INLINE char *
> -__strsep_2c (char **__s, char __reject1, char __reject2)
> -{
> -  char *__retval = *__s;
> -  if (__retval != NULL)
> -    {
> -      char *__cp = __retval;
> -      while (1)
> -	{
> -	  if (*__cp == '\0')
> -	    {
> -	      __cp = NULL;
> -	  break;
> -	    }
> -	  if (*__cp == __reject1 || *__cp == __reject2)
> -	    {
> -	      *__cp++ = '\0';
> -	      break;
> -	    }
> -	  ++__cp;
> -	}
> -      *__s = __cp;
> -    }
> -  return __retval;
> -}
> -
> -__STRING_INLINE char *__strsep_3c (char **__s, char __reject1, char __reject2,
> -				   char __reject3);
> -__STRING_INLINE char *
> -__strsep_3c (char **__s, char __reject1, char __reject2, char __reject3)
> -{
> -  char *__retval = *__s;
> -  if (__retval != NULL)
> -    {
> -      char *__cp = __retval;
> -      while (1)
> -	{
> -	  if (*__cp == '\0')
> -	    {
> -	      __cp = NULL;
> -	  break;
> -	    }
> -	  if (*__cp == __reject1 || *__cp == __reject2 || *__cp == __reject3)
> -	    {
> -	      *__cp++ = '\0';
> -	      break;
> -	    }
> -	  ++__cp;
> -	}
> -      *__s = __cp;
> -    }
> -  return __retval;
> -}
> -# ifdef __USE_MISC
> -#  define strsep(s, reject) __strsep (s, reject)
> -# endif
> -#endif
> -
>  /* We need the memory allocation functions for inline strdup().
>     Referring to stdlib.h (even minimally) is not allowed
>     in any of the tight standards compliant modes.  */
> diff --git a/string/string-inlines.c b/string/string-inlines.c
> index f6f56c56f875a89fbc05dec61a7603c2a869607c..6d0c0c51b3027f99d26aace85523d7f337df8308 100644
> --- a/string/string-inlines.c
> +++ b/string/string-inlines.c
> @@ -62,6 +62,70 @@ __old_strtok_r_1c (char *__s, char __sep, char **__nextp)
>    return __result;
>  }
>  compat_symbol (libc, __old_strtok_r_1c, __strtok_r_1c, GLIBC_2_1_1);
> +
> +char *
> +__old_strsep_1c (char **__s, char __reject)
> +{
> +  char *__retval = *__s;
> +  if (__retval != NULL && (*__s = strchr (__retval, __reject)) != NULL)
> +    *(*__s)++ = '\0';
> +  return __retval;
> +}
> +compat_symbol (libc, __old_strsep_1c, __strsep_1c, GLIBC_2_1_1);
> +
> +char *
> +__old_strsep_2c (char **__s, char __reject1, char __reject2)
> +{
> +  char *__retval = *__s;
> +  if (__retval != NULL)
> +    {
> +      char *__cp = __retval;
> +      while (1)
> +	{
> +	  if (*__cp == '\0')
> +	    {
> +	      __cp = NULL;
> +	      break;
> +	    }
> +	  if (*__cp == __reject1 || *__cp == __reject2)
> +	    {
> +	      *__cp++ = '\0';
> +	      break;
> +	    }
> +	  ++__cp;
> +	}
> +      *__s = __cp;
> +    }
> +  return __retval;
> +}
> +compat_symbol (libc, __old_strsep_2c, __strsep_2c, GLIBC_2_1_1);
> +
> +char *
> +__old_strsep_3c (char **__s, char __reject1, char __reject2, char __reject3)
> +{
> +  char *__retval = *__s;
> +  if (__retval != NULL)
> +    {
> +      char *__cp = __retval;
> +      while (1)
> +	{
> +	  if (*__cp == '\0')
> +	    {
> +	      __cp = NULL;
> +	      break;
> +	    }
> +	  if (*__cp == __reject1 || *__cp == __reject2 || *__cp == __reject3)
> +	    {
> +	      *__cp++ = '\0';
> +	      break;
> +	    }
> +	  ++__cp;
> +	}
> +      *__s = __cp;
> +    }
> +  return __retval;
> +}
> +compat_symbol (libc, __old_strsep_3c, __strsep_3c, GLIBC_2_1_1);
>  #endif
>  
>  #if SHLIB_COMPAT (libc, GLIBC_2_1_1, GLIBC_2_24)
> diff --git a/string/strsep.c b/string/strsep.c
> index 10547740481bed8f7a065f76eccfe7b320c3c49c..68581c863980c1e86ae8559400ca0d1cec80d95e 100644
> --- a/string/strsep.c
> +++ b/string/strsep.c
> @@ -29,30 +29,10 @@ __strsep (char **stringp, const char *delim)
>    if (begin == NULL)
>      return NULL;
>  
> -  /* A frequent case is when the delimiter string contains only one
> -     character.  Here we don't need to call the expensive `strpbrk'
> -     function and instead work using `strchr'.  */
> -  if (delim[0] == '\0' || delim[1] == '\0')
> -    {
> -      char ch = delim[0];
> -
> -      if (ch == '\0')
> -	end = NULL;
> -      else
> -	{
> -	  if (*begin == ch)
> -	    end = begin;
> -	  else if (*begin == '\0')
> -	    end = NULL;
> -	  else
> -	    end = strchr (begin + 1, ch);
> -	}
> -    }
> -  else
> -    /* Find the end of the token.  */
> -    end = strpbrk (begin, delim);
> +  /* Find the end of the token.  */
> +  end = begin + strcspn (begin, delim);
>  
> -  if (end)
> +  if (*end)
>      {
>        /* Terminate the token and set *STRINGP past NUL character.  */
>        *end++ = '\0';
>
  

(replying to https://sourceware.org/ml/libc-alpha/2016-11/msg00856.html to keep things
in the right thread) 

Adhemerval Zanella wrote:

> > -  static const char d[] = "1234567890abcdef";
> > +  static const char d[] = "1234567891abcdef";
>
> I think it worth a comment saying '1' is duplicated to avoid
> have a delimiter in every position.

I'll add a comment. The benchmark at least does do something now - however we
really need to get some traces as unlike memcpy it is hard to even have a gut feeling
about typical use...

> > -    for (size_t hlen = 2 * klen; hlen < 16 * klen; hlen += klen)
> > +    for (size_t hlen = 4 * klen; hlen < 8 * klen; hlen += klen)
> 
> Why change the lengths to test?

Did you try running it? It takes forever and generates a huge amount of useless output.
With my fix it runs much slower as it now does actual work so I needed to reduce the
number of tests.

> OK. Also not related to patch itself, but since it does not apply clean
> I would recommend to list the possible prerequisites for this patch
> if the intention is indeed using on top of any other patch.

It should apply cleanly now in v2, but you can still get merge conflicts when trying
it out of order.

Wilco