This is the mail archive of the mailing list for the glibc project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH v3] powerpc: strstr optimization

On 07/22/2015 02:29 PM, Tulio Magno Quites Machado Filho wrote:
> "Carlos O'Donell" <> 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

I am OK to leave the patches in place and to resolve the discussion of
quadratic behaviour and algorithm acceptability for 2.23.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]