This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH] powerpc: strstr optimization
- From: Steven Munroe <munroesj at linux dot vnet dot ibm dot comcom>
- To: Joseph Myers <joseph at codesourcery dot com>
- Cc: munroesj at linux dot vnet dot ibm dot com, Rajalakshmi Srinivasaraghavan <raji at linux dot vnet dot ibm dot com>, OndÅej BÃlka <neleai at seznam dot cz>, libc-alpha at sourceware dot org, sjmunroe at us dot ibm dot com
- Date: Mon, 11 May 2015 16:03:52 -0500
- Subject: Re: [PATCH] powerpc: strstr optimization
- Authentication-results: sourceware.org; auth=none
- References: <1429254584-124997-1-git-send-email-raji at linux dot vnet dot ibm dot com> <20150501120510 dot GB2203 at domone> <554704A1 dot 3010007 at linux dot vnet dot ibm dot com> <20150505211414 dot GA18085 at domone> <554A1703 dot 5090707 at linux dot vnet dot ibm dot com> <1431367848 dot 14012 dot 3 dot camel at sjmunroe-ThinkPad-W500> <alpine dot DEB dot 2 dot 10 dot 1505112012540 dot 1960 at digraph dot polyomino dot org dot uk>
- Reply-to: munroesj at linux dot vnet dot ibm dot com
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?