powerpc: strstr optimization

  This patch optimizes strstr function for power >= 7 systems.  Performance
gain is obtained using doubleword aligned memory access and usage of cmpb
instruction for quicker comparison.  The average improvement of this
optimization is ~40%.

2015-04-17  Rajalakshmi Srinivasaraghavan  <raji@linux.vnet.ibm.com>

	* sysdeps/powerpc/powerpc64/multiarch/Makefile: Add strstr().
	* sysdeps/powerpc/powerpc64/multiarch/ifunc-impl-list.c: Likewise.
	* sysdeps/powerpc/powerpc64/power7/strstr.S: New File.
	* sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S: New File.
	* sysdeps/powerpc/powerpc64/multiarch/strstr-ppc64.c: New File.
	* sysdeps/powerpc/powerpc64/multiarch/strstr.c: New File.
---
 sysdeps/powerpc/powerpc64/multiarch/Makefile       |   2 +-
 .../powerpc/powerpc64/multiarch/ifunc-impl-list.c  |   8 +
 .../powerpc/powerpc64/multiarch/strstr-power7.S    |  44 ++
 sysdeps/powerpc/powerpc64/multiarch/strstr-ppc64.c |  29 ++
 sysdeps/powerpc/powerpc64/multiarch/strstr.c       |  34 ++
 sysdeps/powerpc/powerpc64/power7/strstr.S          | 500 +++++++++++++++++++++
 6 files changed, 616 insertions(+), 1 deletion(-)
 create mode 100644 sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S
 create mode 100644 sysdeps/powerpc/powerpc64/multiarch/strstr-ppc64.c
 create mode 100644 sysdeps/powerpc/powerpc64/multiarch/strstr.c
 create mode 100644 sysdeps/powerpc/powerpc64/power7/strstr.S
  

On Fri, Apr 17, 2015 at 02:09:44AM -0500, Rajalakshmi Srinivasaraghavan wrote:
> This patch optimizes strstr function for power >= 7 systems.  Performance
> gain is obtained using doubleword aligned memory access and usage of cmpb
> instruction for quicker comparison.  The average improvement of this
> optimization is ~40%.

As I did same with x64 I will add improvements, I didn't look at patch
in detail.

First problem looks there is  quadratic worst case. That is solved by
buy-or-rent technique. You count number of comparisons and if that
exceeds C*N where N is number of haystack bytes read so far and C
suitable constant then you switch to slower generic algorithm.

Main improvement in x64 case was checking for pair of characters. A pair
of characters is less likely than single character even vectorized
branch would be rarely triggered saving misprediction cost that
dominates performance.

That improved performance about 25 times.


For checking pair only with arithmetic you look on zero bytes of
following expression

(LOAD (haystack + n) ^ BROADCAST(needle[0])) | (LOAD (haystack + n + 1) ^ BROADCAST(needle[1]))

Then you need to do technical improvements.

One is unrolling to test 64 bytes at once, you could keep that to 32/16
if that improves performance. Hot portion is header, loop is rarely used
so you should check first 64 bytes without going to main loop.

Next is that you need to load vector twice, once for first character and
then for second character. You need to have loads corresponding to
second character aligned. For first character you could use unaligned
loads if they are fast or get these by bit fiddling from second
character loads. This way you don't have to worry about crossing page
boundaries.

Here is template that I used to generate x64 version you could use that
with modifications. Main problem is mapping suitable instrincts or
replacing these with corresponding powerpc instructions.


#include <emmintrin.h>
#include <stdint.h>
#include <stdlib.h>
#include "../header.h"

#ifdef AS_SSSE3
# define PREVCHAR(s, va, vb) CONCAT (va, vb, 15)
#else
# define PREVCHAR(s, va, vb) LOADU (s)
#endif

static inline tp_mask
forget_first_bit (tp_mask x)
{
  return x & (x - 1);
}

static inline int
strcmp2 (char *x, char *y, long *buy)
{
  int i = 0;
  while (1)
    {
      if (!y[i])
	return 0;

      if (x[i] != y[i])
	{
	  buy += i; return 1;
	}
      i++;
    }
}
char *strchr (char *s, int n);

char *strstr_string (char *a, char *b);

unsigned char *
strstr_new (unsigned char *s, unsigned char *n)
{
  long i;
  unsigned char *s_or, *s_al;
  if (__builtin_expect (!n[0], 0))
    return s;

  if (!n[1])
    return strchr (s, n[0]);

  tp_vector v0 = BROADCAST (n[0]), v1 = BROADCAST (n[1]), vz = BROADCAST (0);
  tp_vector vs0, vs1, vs2, vs3, vsb;
  long buy;
  long unused;
  if ((((size_t) s) & 4095) <= 4096 - 65)
    {
      vs0 = LOADU (s);
      /*or test three chars. */
      vs0 = OR (MIN (EQ (vs0, v0), EQ (v1, LOADU (s + 1))), EQ (vs0, vz));
      tp_mask m = get_mask (vs0);    //| (get_mask(vs1) << 16) | (get_mask(vs2) <<32) | (get_mask(vs3)<<48);

      while (m)
	{
	  unsigned char *r = s + first_bit (m);
	  if (!*r)
	    return NULL;

	  if (!strcmp2 (r + 2, n + 2, &unused))
	    return r;

	  m = forget_first_bit (m);
	}

      vs1 = LOADU (s + 16);
      vs2 = LOADU (s + 32);
      vs3 = LOADU (s + 48);
      /*or test three chars. */
      vs1 = OR (MIN (EQ (vs1, v0), EQ (v1, LOADU (s + 16 + 1))), EQ (vs1, vz));
      vs2 = OR (MIN (EQ (vs2, v0), EQ (v1, LOADU (s + 32 + 1))), EQ (vs2, vz));
      vs3 = OR (MIN (EQ (vs3, v0), EQ (v1, LOADU (s + 48 + 1))), EQ (vs3, vz));
      m = (get_mask (vs1) << 16) | (get_mask (vs2) << 32) | (get_mask (vs3) << 48);

      while (m)
	{
	  unsigned char *r = s + first_bit (m);
	  if (!*r)
	    return NULL;

	  if (!strcmp2 (r + 2, n + 2, &unused))
	    return r;

	  m = forget_first_bit (m);
	}
    }
  else
    {
      s_al = ALIGN_DOWN (s, 64);

      vs0 = LOAD (s_al);
      vs1 = LOAD (s_al + 16);
      vs2 = LOAD (s_al + 32);
      vs3 = LOAD (s_al + 48);
      /*or test three chars. */
      vs0 = OR (MIN (EQ (vs0, v1), EQ (v0, LOADU (s_al - 1))), EQ (vs0, vz));
      vs1 = OR (MIN (EQ (vs1, v1), EQ (v0, LOADU (s_al + 16 - 1))), EQ (vs1, vz));
      vs2 = OR (MIN (EQ (vs2, v1), EQ (v0, LOADU (s_al + 32 - 1))), EQ (vs2, vz));
      vs3 = OR (MIN (EQ (vs3, v1), EQ (v0, LOADU (s_al + 48 - 1))), EQ (vs3, vz));
      tp_mask m = get_mask (vs0) | (get_mask (vs1) << 16) | (get_mask (vs2) << 32) | (get_mask (vs3) << 48);
      m = m >> (s - s_al);
      while (m)
	{
	  unsigned char *r = s + first_bit (m);
	  if (!*r)
	    return NULL;

	  if (r != s && !strcmp2 (r + 2, n + 2, &unused))
	    return r;

	  m = forget_first_bit (m);
	}
    }

  buy = -512;
  s_or = s;
  s = ALIGN_DOWN (s + 64, 64);
#ifdef AS_SSSE3
  vs3 = LOAD (s - 16);
#endif
  while (1)
    {
      vs0 = LOAD (s);
      vs1 = LOAD (s + 16);
      vs2 = LOAD (s + 32);
      vs3 = LOAD (s + 48);
      /*or test three chars. */
      tp_vector ret = vs0;
      ret = MIN (ret, vs1);
      ret = MIN (ret, vs2);
      ret = MIN (ret, vs3);
      tp_vector ret2 = OR (XOR (PREVCHAR (s - 1, vs3, vs0), v0), XOR (vs0, v1));
      ret2 = MIN (ret2, OR (XOR (PREVCHAR (s - 1 + 16, vs0, vs1), v0), XOR (vs1, v1)));
      ret2 = MIN (ret2, OR (XOR (PREVCHAR (s - 1 + 32, vs1, vs2), v0), XOR (vs2, v1)));
      ret2 = MIN (ret2, OR (XOR (PREVCHAR (s - 1 + 48, vs2, vs3), v0), XOR (vs3, v1)));
      ret = MIN (ret, ret2);
      if (get_mask (EQ (ret, vz)))
	{
	  s_al = ALIGN_DOWN (s, 64);

	  vs0 = LOAD (s_al);
	  vs1 = LOAD (s_al + 16);
	  vs2 = LOAD (s_al + 32);
	  vs3 = LOAD (s_al + 48);
	  /*or test three chars. */
	  vs0 = OR (MIN (EQ (vs0, v1), EQ (v0, LOADU (s_al - 1))), EQ (vs0, vz)); /* todo last three nondestructive */
	  vs1 = OR (MIN (EQ (vs1, v1), EQ (v0, LOADU (s_al + 16 - 1))), EQ (vs1, vz));
	  vs2 = OR (MIN (EQ (vs2, v1), EQ (v0, LOADU (s_al + 32 - 1))), EQ (vs2, vz));
	  vs3 = OR (MIN (EQ (vs3, v1), EQ (v0, LOADU (s_al + 48 - 1))), EQ (vs3, vz));
	  tp_mask m = get_mask (vs0) | (get_mask (vs1) << 16) | (get_mask (vs2) << 32) | (get_mask (vs3) << 48);
	  while (m)
	    {
	      unsigned char *r = s + first_bit (m);
	      if (!*r)
		return NULL;

	      if (!strcmp2 (r + 1, n + 2, &buy))
		return r - 1;

	      if (buy > s - s_or)
		return strstr_string (s, n);

	      m = forget_first_bit (m);
	    }
	}
      s += 64;
    }
}
  

On Fri, Apr 17, 2015 at 12:09 AM, Rajalakshmi Srinivasaraghavan
<raji@linux.vnet.ibm.com> wrote:
> diff --git a/sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S b/sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S
> new file mode 100644
> index 0000000..68b93b0
> --- /dev/null
> +++ b/sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S
> @@ -0,0 +1,44 @@
> +/* Optimized strstr implementation for POWER7.
> +   Copyright (C) 2015-2016 Free Software Foundation, Inc.

Help me understand the 2016 copyright?
  

On 05/04/2015 05:21 AM, Matt Turner wrote:
> On Fri, Apr 17, 2015 at 12:09 AM, Rajalakshmi Srinivasaraghavan
> <raji@linux.vnet.ibm.com> wrote:
>> diff --git a/sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S b/sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S
>> new file mode 100644
>> index 0000000..68b93b0
>> --- /dev/null
>> +++ b/sysdeps/powerpc/powerpc64/multiarch/strstr-power7.S
>> @@ -0,0 +1,44 @@
>> +/* Optimized strstr implementation for POWER7.
>> +   Copyright (C) 2015-2016 Free Software Foundation, Inc.
> Help me understand the 2016 copyright?
This must be just 2015. I will correct it.
>
  

On 05/01/2015 05:35 PM, Ondřej Bílka wrote:
> On Fri, Apr 17, 2015 at 02:09:44AM -0500, Rajalakshmi Srinivasaraghavan wrote:
>> This patch optimizes strstr function for power >= 7 systems.  Performance
>> gain is obtained using doubleword aligned memory access and usage of cmpb
>> instruction for quicker comparison.  The average improvement of this
>> optimization is ~40%.
> As I did same with x64 I will add improvements, I didn't look at patch
> in detail.
>
> First problem looks there is  quadratic worst case. That is solved by
> buy-or-rent technique. You count number of comparisons and if that
> exceeds C*N where N is number of haystack bytes read so far and C
> suitable constant then you switch to slower generic algorithm.
>
> Main improvement in x64 case was checking for pair of characters. A pair
> of characters is less likely than single character even vectorized
> branch would be rarely triggered saving misprediction cost that
> dominates performance.
>
Though I did not understand your program completely, I agree with 
checking pair of characters
can improve the performance.

In my optimization there are totally three branches.
case 1# if needle len >= 8 (common case)
case 2# if needle < 8 (common case)
case 3# For page boundary cross haystack. (rare case)

For case 1, I always compare 8 characters at a time using cmpb instruction.
-> perform basic strlen, strnlen, checks. Move haystack based on strchr 
result.
-> Load first 8 bytes(taking care of aligned load)from haystack and 
needle and compare them.
If they are same proceed to next 8 bytes of haystack and needle.
Else load next doubleword from haystack.Form a doubleword with last 
seven characters from first load and first character from
second load and compare again with needle. Proceed in a similar way.
This gives good improvement.

For case2, always compare 'n'  characters at a time, 'n' is needle length.
-> Algorithm is same as case 1, however before doing cmpb,create input 
mask based on needle len.

For case 1 and case 2, input is always loaded as double word.

For case 3, its byte by byte comparison.
  

On Mon, May 04, 2015 at 11:03:21AM +0530, Rajalakshmi Srinivasaraghavan wrote:
> 
> 
> On 05/01/2015 05:35 PM, Ondřej Bílka wrote:
> >On Fri, Apr 17, 2015 at 02:09:44AM -0500, Rajalakshmi Srinivasaraghavan wrote:
> >>This patch optimizes strstr function for power >= 7 systems.  Performance
> >>gain is obtained using doubleword aligned memory access and usage of cmpb
> >>instruction for quicker comparison.  The average improvement of this
> >>optimization is ~40%.
> >As I did same with x64 I will add improvements, I didn't look at patch
> >in detail.
> >
> >First problem looks there is  quadratic worst case. That is solved by
> >buy-or-rent technique. You count number of comparisons and if that
> >exceeds C*N where N is number of haystack bytes read so far and C
> >suitable constant then you switch to slower generic algorithm.
> >
> >Main improvement in x64 case was checking for pair of characters. A pair
> >of characters is less likely than single character even vectorized
> >branch would be rarely triggered saving misprediction cost that
> >dominates performance.
> >
> Though I did not understand your program completely, I agree with
> checking pair of characters
> can improve the performance.
> 
It does. AFAIR for practical strings on x64 its only around 3 times slower than
theoretical lower bound. 

A lower bound is strlen call as you must find terminating null when
needle isn't present.

I hope that main idea was clear and you will
use it. Code I send is complex as it contains ten different speedups
that improve performance.


> In my optimization there are totally three branches.
> case 1# if needle len >= 8 (common case)
> case 2# if needle < 8 (common case)
> case 3# For page boundary cross haystack. (rare case)
>
Checking if its case 1 or 2 is relatively costy as in practice haystacks
tend to be short. Most apps that use strstr have 90% call haystack less than 64 bytes long.

You don't need to know needle size if you know that it doesn't contain
first pair. Also its rare that it contains first pair of characters twice.

> For case 1, I always compare 8 characters at a time using cmpb instruction.
> -> perform basic strlen, strnlen, checks. Move haystack based on
> strchr result.
> -> Load first 8 bytes(taking care of aligned load)from haystack and
> needle and compare them.
> If they are same proceed to next 8 bytes of haystack and needle.
> Else load next doubleword from haystack.Form a doubleword with last
> seven characters from first load and first character from
> second load and compare again with needle. Proceed in a similar way.
> This gives good improvement.
> 
Thats looks worse than naive algorithm on practical strings. Most
instructions you do are useless as you have mismatch at first character.

Following function should beat it.

char *strstr (char *s, char *n)
{
  if (n[0] == 0)
    return s;
  while (s = strchr (s, n[0]))
    {
      long i;
      for (i=1; n[i] && n[i] == s[i]; i++);
      if (n[i] == 0)
        return s;
      s++;
    }
}

Or use musl strstr idea. While implementation is terrible as it in
practice unnecessary spends 90% time on preprocessing their loop is
relatively good for portable implementation.

> For case2, always compare 'n'  characters at a time, 'n' is needle length.
> -> Algorithm is same as case 1, however before doing cmpb,create
> input mask based on needle len.
> 
> For case 1 and case 2, input is always loaded as double word.
> 
> For case 3, its byte by byte comparison.
>
  

On 05/06/2015 02:44 AM, Ondřej Bílka wrote:
>
> It does. AFAIR for practical strings on x64 its only around 3 times slower than
> theoretical lower bound.
>
> A lower bound is strlen call as you must find terminating null when
> needle isn't present.
>
> I hope that main idea was clear and you will
> use it. Code I send is complex as it contains ten different speedups
> that improve performance.
>
>
>> In my optimization there are totally three branches.
>> case 1# if needle len >= 8 (common case)
>> case 2# if needle < 8 (common case)
>> case 3# For page boundary cross haystack. (rare case)
>>
> Checking if its case 1 or 2 is relatively costy as in practice haystacks
> tend to be short. Most apps that use strstr have 90% call haystack less than 64 bytes long.
>
> You don't need to know needle size if you know that it doesn't contain
> first pair. Also its rare that it contains first pair of characters twice.
strlen of needle is needed in all the cases so as to make sure haystack 
is longer than needle
as part of initial check before proceeding to search. Once this check is 
passed, strchr is
called to find the  position of first character.

>
>> For case 1, I always compare 8 characters at a time using cmpb instruction.
>> -> perform basic strlen, strnlen, checks. Move haystack based on
>> strchr result.
>> -> Load first 8 bytes(taking care of aligned load)from haystack and
>> needle and compare them.
>> If they are same proceed to next 8 bytes of haystack and needle.
>> Else load next doubleword from haystack.Form a doubleword with last
>> seven characters from first load and first character from
>> second load and compare again with needle. Proceed in a similar way.
>> This gives good improvement.
>>
> Thats looks worse than naive algorithm on practical strings. Most
> instructions you do are useless as you have mismatch at first character.
>
> Following function should beat it.
>
> char *strstr (char *s, char *n)
> {
>    if (n[0] == 0)
>      return s;
>    while (s = strchr (s, n[0]))
>      {
>        long i;
>        for (i=1; n[i] && n[i] == s[i]; i++);
>        if (n[i] == 0)
>          return s;
>        s++;
>      }
> }
Calling strchr in a loop is not showing  improvement when compared to 
the proposed patch.
>
> Or use musl strstr idea. While implementation is terrible as it in
> practice unnecessary spends 90% time on preprocessing their loop is
> relatively good for portable implementation.
>
>
  

On Wed, 2015-05-06 at 18:58 +0530, Rajalakshmi Srinivasaraghavan wrote:
> 
> On 05/06/2015 02:44 AM, Ondřej Bílka wrote:
> >
> > It does. AFAIR for practical strings on x64 its only around 3 times slower than
> > theoretical lower bound.
> >
> > A lower bound is strlen call as you must find terminating null when
> > needle isn't present.
> >
> > I hope that main idea was clear and you will
> > use it. Code I send is complex as it contains ten different speedups
> > that improve performance.
> >
> >
> >> In my optimization there are totally three branches.
> >> case 1# if needle len >= 8 (common case)
> >> case 2# if needle < 8 (common case)
> >> case 3# For page boundary cross haystack. (rare case)
> >>
> > Checking if its case 1 or 2 is relatively costy as in practice haystacks
> > tend to be short. Most apps that use strstr have 90% call haystack less than 64 bytes long.
> >
> > You don't need to know needle size if you know that it doesn't contain
> > first pair. Also its rare that it contains first pair of characters twice.
> strlen of needle is needed in all the cases so as to make sure haystack 
> is longer than needle
> as part of initial check before proceeding to search. Once this check is 
> passed, strchr is
> called to find the  position of first character.
> 
I think we should move on with (commit) Raji's patch as is. 

While we appreciate you suggestions Ondrej, not all optimization apply
equally to all platforms. 

> >
> >> For case 1, I always compare 8 characters at a time using cmpb instruction.
> >> -> perform basic strlen, strnlen, checks. Move haystack based on
> >> strchr result.
> >> -> Load first 8 bytes(taking care of aligned load)from haystack and
> >> needle and compare them.
> >> If they are same proceed to next 8 bytes of haystack and needle.
> >> Else load next doubleword from haystack.Form a doubleword with last
> >> seven characters from first load and first character from
> >> second load and compare again with needle. Proceed in a similar way.
> >> This gives good improvement.
> >>
> > Thats looks worse than naive algorithm on practical strings. Most
> > instructions you do are useless as you have mismatch at first character.
> >
> > Following function should beat it.
> >
> > char *strstr (char *s, char *n)
> > {
> >    if (n[0] == 0)
> >      return s;
> >    while (s = strchr (s, n[0]))
> >      {
> >        long i;
> >        for (i=1; n[i] && n[i] == s[i]; i++);
> >        if (n[i] == 0)
> >          return s;
> >        s++;
> >      }
> > }
> Calling strchr in a loop is not showing  improvement when compared to 
> the proposed patch.
> >
> > Or use musl strstr idea. While implementation is terrible as it in
> > practice unnecessary spends 90% time on preprocessing their loop is
> > relatively good for portable implementation.
> >
> >
>
  

On Mon, 11 May 2015, Steven Munroe wrote:

> I think we should move on with (commit) Raji's patch as is. 

Does the patch avoid quadratic worst case?  Quadratic performance in 
strstr is an unambiguous regression, allowing for denial-of-service, that 
should not be introduced on any platform (cf bug 12100).  Indeed, gnulib 
has a configure test for quadratic strstr, so if you introduce quadratic 
worst case then the effect will be that all applications using gnulib 
automatically configure themselves to use gnulib's strstr and not glibc's 
at all.
  

On Mon, 2015-05-11 at 20:19 +0000, Joseph Myers wrote:
> On Mon, 11 May 2015, Steven Munroe wrote:
> 
> > I think we should move on with (commit) Raji's patch as is. 
> 
> Does the patch avoid quadratic worst case?  Quadratic performance in 
> strstr is an unambiguous regression, allowing for denial-of-service, that 
> should not be introduced on any platform (cf bug 12100).  Indeed, gnulib 
> has a configure test for quadratic strstr, so if you introduce quadratic 
> worst case then the effect will be that all applications using gnulib 
> automatically configure themselves to use gnulib's strstr and not glibc's 
> at all.
> 

There was an assertion that there "might be" a quadratic worse case. No
proof was offered that there was such.

Raji do you have the data for this?
  

On Wed, May 06, 2015 at 06:58:35PM +0530, Rajalakshmi Srinivasaraghavan wrote:
> 
> 
> On 05/06/2015 02:44 AM, Ondřej Bílka wrote:
> >
> >It does. AFAIR for practical strings on x64 its only around 3 times slower than
> >theoretical lower bound.
> >
> >A lower bound is strlen call as you must find terminating null when
> >needle isn't present.
> >
> >I hope that main idea was clear and you will
> >use it. Code I send is complex as it contains ten different speedups
> >that improve performance.
> >
> >
> >>In my optimization there are totally three branches.
> >>case 1# if needle len >= 8 (common case)
> >>case 2# if needle < 8 (common case)
> >>case 3# For page boundary cross haystack. (rare case)
> >>
> >Checking if its case 1 or 2 is relatively costy as in practice haystacks
> >tend to be short. Most apps that use strstr have 90% call haystack less than 64 bytes long.
> >
> >You don't need to know needle size if you know that it doesn't contain
> >first pair. Also its rare that it contains first pair of characters twice.
> strlen of needle is needed in all the cases so as to make sure
> haystack is longer than needle
> as part of initial check before proceeding to search. Once this
> check is passed, strchr is
> called to find the  position of first character.
>
No, strlen is entirely unnecessary. When haystack doesn't contain first
triple of characters (and if it contains match is relatively likely)
then question if needle or haystack are larger is irrelevant.
 
> >
> >>For case 1, I always compare 8 characters at a time using cmpb instruction.
> >>-> perform basic strlen, strnlen, checks. Move haystack based on
> >>strchr result.
> >>-> Load first 8 bytes(taking care of aligned load)from haystack and
> >>needle and compare them.
> >>If they are same proceed to next 8 bytes of haystack and needle.
> >>Else load next doubleword from haystack.Form a doubleword with last
> >>seven characters from first load and first character from
> >>second load and compare again with needle. Proceed in a similar way.
> >>This gives good improvement.
> >>
> >Thats looks worse than naive algorithm on practical strings. Most
> >instructions you do are useless as you have mismatch at first character.
> >
> >Following function should beat it.
> >
> >char *strstr (char *s, char *n)
> >{
> >   if (n[0] == 0)
> >     return s;
> >   while (s = strchr (s, n[0]))
> >     {
> >       long i;
> >       for (i=1; n[i] && n[i] == s[i]; i++);
> >       if (n[i] == 0)
> >         return s;
> >       s++;
> >     }
> >}
> Calling strchr in a loop is not showing  improvement when compared
> to the proposed patch.
> >
Evidence?
  

On Mon, May 11, 2015 at 01:10:48PM -0500, Steven Munroe wrote:
> On Wed, 2015-05-06 at 18:58 +0530, Rajalakshmi Srinivasaraghavan wrote:
> > 
> > On 05/06/2015 02:44 AM, Ondřej Bílka wrote:
> > >
> > > It does. AFAIR for practical strings on x64 its only around 3 times slower than
> > > theoretical lower bound.
> > >
> > > A lower bound is strlen call as you must find terminating null when
> > > needle isn't present.
> > >
> > > I hope that main idea was clear and you will
> > > use it. Code I send is complex as it contains ten different speedups
> > > that improve performance.
> > >
> > >
> > >> In my optimization there are totally three branches.
> > >> case 1# if needle len >= 8 (common case)
> > >> case 2# if needle < 8 (common case)
> > >> case 3# For page boundary cross haystack. (rare case)
> > >>
> > > Checking if its case 1 or 2 is relatively costy as in practice haystacks
> > > tend to be short. Most apps that use strstr have 90% call haystack less than 64 bytes long.
> > >
> > > You don't need to know needle size if you know that it doesn't contain
> > > first pair. Also its rare that it contains first pair of characters twice.
> > strlen of needle is needed in all the cases so as to make sure haystack 
> > is longer than needle
> > as part of initial check before proceeding to search. Once this check is 
> > passed, strchr is
> > called to find the  position of first character.
> > 
> I think we should move on with (commit) Raji's patch as is. 
> 
> While we appreciate you suggestions Ondrej, not all optimization apply
> equally to all platforms. 

No as you failed a basic item of contributor checklist. All performance
related patches need a benchmark to show its performance improvement and
not regression. A algorithm overview mentioned there is garbage. It
would likely cause performance regression in average case but I don't
have a powerpc machine to run a test and present numbers.
  

On 05/11/2015 04:19 PM, Joseph Myers wrote:
> On Mon, 11 May 2015, Steven Munroe wrote:
> 
>> I think we should move on with (commit) Raji's patch as is. 
> 
> Does the patch avoid quadratic worst case?  Quadratic performance in 
> strstr is an unambiguous regression, allowing for denial-of-service, that 
> should not be introduced on any platform (cf bug 12100).  Indeed, gnulib 
> has a configure test for quadratic strstr, so if you introduce quadratic 
> worst case then the effect will be that all applications using gnulib 
> automatically configure themselves to use gnulib's strstr and not glibc's 
> at all.
> 

We should add gnulib's test to the microbenchmarks.

c.
  

On 05/12/2015 04:49 AM, Ondřej Bílka wrote:
>>> Following function should beat it.
>>>
>>> char *strstr (char *s, char *n)
>>> {
>>>   if (n[0] == 0)
>>>     return s;
>>>   while (s = strchr (s, n[0]))
>>>     {
>>>       long i;
>>>       for (i=1; n[i] && n[i] == s[i]; i++);
>>>       if (n[i] == 0)
>>>         return s;
>>>       s++;
>>>     }
>>> }
>> Calling strchr in a loop is not showing  improvement when compared
>> to the proposed patch.
>>>
> Evidence?
> 

I agree with Ondrej here. What tests are you doing to show there is
no performance improvement? Can we see those tests? Can you contribute
them to the microbenchmark so other Power vendors can use them against
their particular hardware to validate performance?

Cheers,
Carlos.
  

On Thu, 2015-05-21 at 11:08 -0400, Carlos O'Donell wrote:
> On 05/12/2015 04:49 AM, Ondřej Bílka wrote:
> >>> Following function should beat it.
> >>>
> >>> char *strstr (char *s, char *n)
> >>> {
> >>>   if (n[0] == 0)
> >>>     return s;
> >>>   while (s = strchr (s, n[0]))
> >>>     {
> >>>       long i;
> >>>       for (i=1; n[i] && n[i] == s[i]; i++);
> >>>       if (n[i] == 0)
> >>>         return s;
> >>>       s++;
> >>>     }
> >>> }
> >> Calling strchr in a loop is not showing  improvement when compared
> >> to the proposed patch.
> >>>
> > Evidence?
> > 
> 
> I agree with Ondrej here. What tests are you doing to show there is
> no performance improvement? Can we see those tests? Can you contribute
> them to the microbenchmark so other Power vendors can use them against
> their particular hardware to validate performance?
> 

I thought this was addressed with
https://www.sourceware.org/ml/libc-alpha/2015-05/msg00276.html

Which includes results from benchtest/bench-strstr.c.

Why do we need another micro-benchmark for this?
  

On 05/21/2015 11:27 AM, Steven Munroe wrote:
> On Thu, 2015-05-21 at 11:08 -0400, Carlos O'Donell wrote:
>> On 05/12/2015 04:49 AM, Ondřej Bílka wrote:
>>>>> Following function should beat it.
>>>>>
>>>>> char *strstr (char *s, char *n)
>>>>> {
>>>>>   if (n[0] == 0)
>>>>>     return s;
>>>>>   while (s = strchr (s, n[0]))
>>>>>     {
>>>>>       long i;
>>>>>       for (i=1; n[i] && n[i] == s[i]; i++);
>>>>>       if (n[i] == 0)
>>>>>         return s;
>>>>>       s++;
>>>>>     }
>>>>> }
>>>> Calling strchr in a loop is not showing  improvement when compared
>>>> to the proposed patch.
>>>>>
>>> Evidence?
>>>
>>
>> I agree with Ondrej here. What tests are you doing to show there is
>> no performance improvement? Can we see those tests? Can you contribute
>> them to the microbenchmark so other Power vendors can use them against
>> their particular hardware to validate performance?
>>
> 
> I thought this was addressed with
> https://www.sourceware.org/ml/libc-alpha/2015-05/msg00276.html
> 
> Which includes results from benchtest/bench-strstr.c.
> 
> Why do we need another micro-benchmark for this?

You don't. The above addresses my complaints. I must have missed
the other post upthread.

Cheers,
Carlos.