This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v3] powerpc: strstr optimization
- From: "Carlos O'Donell" <carlos at redhat dot com>
- To: Tulio Magno Quites Machado Filho <tuliom at linux dot vnet dot ibm dot com>, Joseph Myers <joseph at codesourcery dot com>
- Cc: 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 14:57:22 -0400
- 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>
On 07/22/2015 02:29 PM, Tulio Magno Quites Machado Filho wrote:
> "Carlos O'Donell" <carlos@redhat.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.
While we have striven to remove quadratic worst case from the string ops, there
has been policy against it if the machine maintainer, knowing their machine
best thinks a particular algorithm with such behaviour works best.
It seems like we need some consensus on the requirements of string operations,
but such consensus will take sufficient time that 2.22 will be released by
then.
I am OK to leave the patches in place and to resolve the discussion of
quadratic behaviour and algorithm acceptability for 2.23.
Cheers,
Carlos.