This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v3] powerpc: strstr optimization
- From: "Tulio Magno Quites Machado Filho" <tuliom at linux dot vnet dot ibm dot com>
- To: "Carlos O'Donell" <carlos at redhat dot com>, OndÅej BÃlka <neleai at seznam dot cz>
- Cc: GNU C Library <libc-alpha at sourceware dot org>, Steve Munroe <sjmunroe at us dot ibm dot com>, Rajalakshmi Srinivasaraghavan <raji at linux dot vnet dot ibm dot com>
- Cc:
- Date: Thu, 16 Jul 2015 18:05:10 -0300
- 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>
"Carlos O'Donell" <carlos@redhat.com> writes:
> On 07/16/2015 03:55 PM, OndÅej BÃlka wrote:
>> 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.
No. That isn't true.
I reviewed this patch myself. All the 4 versions.
So did Steven.
>> I pointed out that it could have possibly quadratic behaviour which
>> still does. So please don't accept unreviewed patches next time.
Yes, this patch does have a quadratic worst case as does quicksort.
But for both algorithms, they're clearly an improvement over what was
available before them.
Is this algorithm perfect? No. I don't believe such a thing exist. I
believe in iterative improvements.
> 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.
That's our intention.
An improvement to this implementation is already in our backlog (i.e. we
haven't started yet) and I'd be glad if someone is interested to help us with
this.
> 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?
IMHO, the overall improvement brought by this patch is more important than
the worst case scenario OndÅej is showing.
Which doesn't mean we're neglecting the quadratic worst case.
--
Tulio Magno