[PATCH] powerpc: strcasestr optimization

[Ondřej Bílka]

On Wed, Jun 24, 2015 at 12:47:23PM +0530, Rajalakshmi Srinivasaraghavan wrote:
> 
> 
> On 06/18/2015 06:28 PM, Ondřej Bílka wrote:
> >On Thu, Jun 18, 2015 at 03:59:55PM +0530, Rajalakshmi Srinivasaraghavan wrote:
> >>>>2048 number is chosen by checking various length inputs and
> >>>>comparing the performance. So for 2047 case, there wont be worst
> >>>>performance.
> >>>>
> >>>What are you talking about? I am saying that aaaa haystack with aaa...ab
> >>>  needle of size 2047 is worst case for your algorithm performance.
> >>>
> >>I ran the attached test.c in a loop 10000 times.
> >>proposed patch took 19s and existing code took 20s on power machine.
> >>
> >How could you ran it? You have two problems with it
> >1. It doesn't compile, its missing final } to end main
> >2. It doesn't measure strstr at all. Its pure function so gcc optimized
> >that away.
> >
> >As when I fixed these two issues just 100 iterations take 1.002s with my
> >x64 vector implementation and 44.538s on generic implemenation your test
> >couldn't take just 20s for existing code.
> >
> >
> >>The reason I mentioned them as different is, in strstr() patch the
> >>input is loaded as double word ie. 8 bytes at a time by byte and in
> >>strcasestr its byte by byte load.The input is handled in different
> >>way.
> >>
> >
> >I see now that you wrote basically
> >
> >long i=0;
> >n0 = tolower(n[0])
> >while (s[i])
> >   {
> >     int j=1;
> >     if (tolower(s[i])==n0)
> >       while (n[j] && tolower(n[j]) == tolower(s[i+j]))
> >         j++;
> >     if (n[j]=='\0')
> >       return s+i;
> >     i++;
> >   }
> >return NULL;
> >
> >For some reason I skimmed that patch and though that you did obvious
> >optimization once you have vector strstr. You use vectorized tolower to
> >convert 8 bytes at once. Example of conversion is in
> >  sysdeps/x86_64/multiarch/strcmp-sse42.S
> >
> For strcasestr() optimization I am trying to use tolower to convert
> 8 bytes and will send the modified patch.
> For strstr() I have sent the new version
> https://sourceware.org/ml/libc-alpha/2015-06/msg00788.html

Doing tolower is still bit slow. You should improve strspn. Then you only need to convert first byte
of needle and call strspn.

> >>>
> >>>Second is about average case perforance. There worst case is irrelevant
> >>>as you use buy-or-rent techniques to handle it. I sumbitted following
> >>>patch with easy way to handle that.
> >>>
> >>>[PATCH] Improve generic strstr performance.
> >>>
> >>I applied your proposed patches and the benchtests and I could see
> >>proposed patch(__strstr_power7) is better than existing code
> >>(__strstr_ppc).
> >>13363 out of 13442 combinations shows improvement.
> >>Attached benchtest results.
> >>
> >I said use that patch. Next line of my previous mail explains that.
> >
> >>>its currently superseeded by generic vector bigraph search but it should
> >>>beat your strstr.
> >
> >So you should do also comparison with that.
> >
> >
> >Your benchmark is invalid for simple reason, I guard vector patch with:
> >
> >if (__BYTE_ORDER == __LITTLE_ENDIAN)
> >   {
> >
> Modified new version works better for both LE and BE. Results
> attached in
> https://sourceware.org/ml/libc-alpha/2015-06/msg00788.html
> 
Yes I was saying all time that you should use that.

> >So as powerpc is big endian my patch does nothing at all and you are
> >just measuring generic strstr again. If you want test bigraph search to
> >that on power64le.
> >
> Used your proposed code on powerpc64le and observed that quadratic
> worst case still takes more time with your proposed code.
> It took more than 2 minutes when the needle size is 100000 and
> haystack is of size 1000000.
>
You still didn't answer how big degradation has your implementation. For
mine its a typo disabled quadratic detection at all. All that needs to
change would be
rent += i + 10;
into
*rent += i + 10;
 
> >>>What overall performance gain? Did you try to find application and
> >>>measure performance difference before and after? Big sizes are not very
> >>>relevant in practice. You look behind 32'th byte of haystack only in
> >>>1.5% of calls so 10% regression at these sizes is much worse that 30%
> >>>gain on 256 byte range. In my profiler a simple collection shows
> >>>following
> >>No I don't check on any specific application and I use the glibc
> >>benchtests for performance measurement which is considered to be the
> >>standard way of performance measurement before proposing a patch.
> >
> >Then you have problem that you don't know which data are important and
> >which are not.
> >
> >Proof by numbers is quite suspect. Input ranges are completely
> >arbitrary. So I could decide that I want to check for sizes 1..64 all
> >possible 64byte needle and haystack alignments. That generates 262144
> >test cases which should be enough.
> >
> >
> 
> -- 
> Thanks
> Rajalakshmi S