This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH][BZ #12100] strstr with unaligned loads.
- From: OndÅej BÃlka <neleai at seznam dot cz>
- To: Rich Felker <dalias at aerifal dot cx>
- Cc: libc-alpha at sourceware dot org
- Date: Mon, 26 Aug 2013 09:09:25 +0200
- Subject: Re: [PATCH][BZ #12100] strstr with unaligned loads.
- Authentication-results: sourceware.org; auth=none
- References: <20130825090758 dot GA23686 at domone dot kolej dot mff dot cuni dot cz> <20130825155406 dot GV20515 at brightrain dot aerifal dot cx>
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...