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: Rich Felker <dalias at aerifal dot cx>
- To: OndÅej BÃlka <neleai at seznam dot cz>
- Cc: libc-alpha at sourceware dot org
- Date: Tue, 27 Aug 2013 09:31:42 -0400
- 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> <20130826070925 dot GA4292 at domone dot kolej dot mff dot cuni dot cz> <20130826162446 dot GZ20515 at brightrain dot aerifal dot cx> <20130827020414 dot GA8611 at domone dot kolej dot mff dot cuni dot cz> <20130827022042 dot GH20515 at brightrain dot aerifal dot cx> <20130827083048 dot GA12761 at domone dot kolej dot mff dot cuni dot cz> <20130827084500 dot GL20515 at brightrain dot aerifal dot cx> <20130827121641 dot GA14077 at domone dot kolej dot mff dot cuni dot cz>
On Tue, Aug 27, 2013 at 02:16:41PM +0200, OndÅej BÃlka wrote:
> On Tue, Aug 27, 2013 at 04:45:00AM -0400, Rich Felker wrote:
> > On Tue, Aug 27, 2013 at 10:30:48AM +0200, OndÅej BÃlka wrote:
> > > > winning on random testcases is meaningless since it has quadratic
> > > > performance in the worst-case.
> > > > For strstr random input is always the
> > > > easy case.
> > >
> > > How good is it on binary alphabeth?
> >
> > Two-way is very good on binary alphabet, and on 4-letter alphabet
> > (e.g. DNA). The bad character table optimization is rather useless on
> > small alphabets, of course, but that's not a core part of the
> > algorithm, just an optimization that helps achieve sublinear
> > performance in many real-world usages (while maintaining worst-case
> > linear performance).
> >
> > Note that having an optimized search for the next occurrance of the
> > first character or two is also rather useless in a binary alphabet...
> >
> A binary alphabet tends to be worst case for optimized implementations.
It's even worse for unoptimized implementations, since long prefix
matches and periodicity in needles becomes the norm rather than the
pathological case.
> > > Its not worth doing from my perspective as factorization step cost
> > > around 20 cycles per needle byte. In that time I could often find three
> > > times that there is no match.
> >
> > I think we'd need to see more empirical data to determine this. Your
> > switchover threshold is not exactly cheap. If the intent is just to
> > give good performance for "typical" (e.g. English text) uses of
> > strstr, and otherwise only avoid pathologically bad performance that
> > could be used for DoS, then your approach may be reasonable. On the
>
> Indent was get best possible performance for typical cases and
> reasonable for all cases.
I don't think you're _too_ far off from that intent.
Rich