This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH][BZ #12100] strstr with unaligned loads.


On Sun, Aug 25, 2013 at 11:54:06AM -0400, Rich Felker wrote:
> tatus: O
> Content-Length: 651
> Lines: 17
> 
> On Sun, Aug 25, 2013 at 11:07:58AM +0200, OndÅej BÃlka wrote:
> > Hi, 
> > 
> > This patch continues to remove ineffective sse4.2 functions. Now we
> > focus on strstr.
> > 
> > I use a techique of doing vectorized search for first pair of characters
> > which is fastest in practice.
> 
> What do you do after finding the first pair? As far as I can tell,

It enumerates all occurences of first pair. 

> this approach is only useful at the start of the string. Once you've
> gotten into two-way, searching for the next occurrence of the first
> two characters is not a useful operation. Of course it looks to me

Not very useful? A two way algorithm spend most time in ineffective
looking for these (or calculating critical factorization which is also
slow.). Actual code is following

          phaystack = &haystack[i + j];
          while (i < needle_len && (CANON_ELEMENT (*pneedle++)
                                    == CANON_ELEMENT (*phaystack++)))
            ++i;
          if (needle_len <= i)
	    snip
          else
            {
              j += i - suffix + 1;
              memory = 0;
            }

And most time first character will not match and in cases when it will
second won't most of time. 

> like the hideous quadratic-runtime SSE4.2 code is still present...


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]