This is the mail archive of the
mailing list for the glibc project.
Re: [PATCH v3] powerpc: strstr optimization
- From: Steven Munroe <munroesj at linux dot vnet dot ibm dot comcom>
- To: Tulio Magno Quites Machado Filho <tuliom at linux dot vnet dot ibm dot com>
- Cc: "Carlos O'Donell" <carlos at redhat dot com>, Joseph Myers <joseph at codesourcery dot com>, Steve Munroe <sjmunroe at us dot ibm dot com>, Florian Weimer <fweimer at redhat dot com>, OndÅej BÃlka <neleai at seznam dot cz>, GNU C Library <libc-alpha at sourceware dot org>, Rajalakshmi Srinivasaraghavan <raji at linux dot vnet dot ibm dot com>
- Date: Wed, 22 Jul 2015 13:58:52 -0500
- Subject: Re: [PATCH v3] powerpc: strstr optimization
- Authentication-results: sourceware.org; auth=none
- References: <558A5642 dot 5020107 at linux dot vnet dot ibm dot com> <558A5761 dot 2000409 at linux dot vnet dot ibm dot com> <87oajpm8nc dot fsf at totoro dot br dot ibm dot com> <871tgijuri dot fsf at linux dot vnet dot ibm dot com> <55A6FE3F dot 6090701 at redhat dot com> <55A70B70 dot 6090607 at redhat dot com> <20150716195538 dot GA5140 at domone> <55A8110C dot 7000209 at redhat dot com> <alpine dot DEB dot 2 dot 10 dot 1507221607370 dot 21570 at digraph dot polyomino dot org dot uk> <55AFD91C dot 30404 at redhat dot com> <87d1zk9hc7 dot fsf at linux dot vnet dot ibm dot com>
- Reply-to: munroesj at linux dot vnet dot ibm dot com
On Wed, 2015-07-22 at 15:29 -0300, Tulio Magno Quites Machado Filho
> "Carlos O'Donell" <email@example.com> writes:
> > On 07/22/2015 12:12 PM, Joseph Myers wrote:
> >> On Thu, 16 Jul 2015, Carlos O'Donell wrote:
> >>> On 07/16/2015 03:55 PM, OndÅej BÃlka wrote:
> >>>> On Wed, Jul 15, 2015 at 09:40:00PM -0400, Carlos O'Donell wrote:
> >>>>> On 07/15/2015 08:43 PM, Carlos O'Donell wrote:
> >>>>>>> May I proceed with this commit?
> >>>>>> Yes, please commit this for 2.22.
> >>>>> For the record I trust IBM to make sure these patches make incremental
> >>>>> improvements in performance even if they are not the best possible
> >>>>> performance as pointed out by Ondrej Bilka.
> >>>> Sorry Carlos, your trust is misplaced. This patch wasn't reviewed at
> >>>> all. I did that as test how much we could test IBM to verify patches.
> >>>> I pointed out that it could have possibly quadratic behaviour which
> >>>> still does. So please don't accept unreviewed patches next time.
> >>> They showed cases for which the code does go faster and objectively
> >>> so using the microbenchmark, and that's a win for now. Please continue
> >>> to work with IBM to remove the quadratic worst case.
> >>> Tulio, You will need to work out why you have quadratic worst case.
> >>> It's certainly something we try to avoid. Did you make a particular
> >>> decision not to avoid it?
> >> If there's a quadratic worst case newly introduced for 2.22, I'd consider
> >> that a security hole (denial of service) that needs to block the release
> >> of 2.22 until it's fixed (possibly by removing the implementation in
> >> question).
> Could you elaborate why a quadratic worst case in a string function can be
> considered a denial of service, please?
> > Tulio,
> > Could you please review the possibility of quadratic behaviour and respond
> > prompty? I don't want this to hold up the release.
> I confirm this algorithm does have a quadratic worst case, which appears if
> needle <= 2048.
> If the needle > 2048, it falls back to the previous implementation.
Well it is somewhat worse, but does this meet the definition of Denial
of service, is the debate.
Also we can reduce this by changing the cross over point for needle
size, but at some loss of overall performance for legitimate cases.
This gets back to my request for an objective standard. No one knows.