Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <BYAPR06MB557347406F22FBA1E400A5BFD8319@BYAPR06MB5573.namprd06.prod.outlook.com>
 <CAHp75Vd4Vk0v-T3kfxApGHb-H26KTHgH59DGP3Wm4qBgunDt6A@mail.gmail.com>
 <Y1embP5sEp/NPxK0@smile.fi.intel.com> <BYAPR06MB557390C5F741300BDE2BAA8BD8319@BYAPR06MB5573.namprd06.prod.outlook.com>
 <CAHp75VeNwvAppVdn+wqAYkzDS115ZuJqm9=gu0hyVoz14qWQkA@mail.gmail.com> <d9c73675-1060-fd8b-958f-50793dca4db4@nathanm.com>
In-Reply-To: <d9c73675-1060-fd8b-958f-50793dca4db4@nathanm.com>
From:   Andy Shevchenko <andy.shevchenko@gmail.com>
Date:   Thu, 27 Oct 2022 09:31:13 +0300
Message-ID: <CAHp75Vec=VOP=9+hNOqa_PCmHp7Qtjq8AykeJkHd0rdz-EKT1Q@mail.gmail.com>
Subject: Re: [PATCH] lib/string.c: Improve strcasecmp speed by not lowering if
 chars match
To:     Nathan Moinvaziri <nathan@nathanm.com>
Cc:     Andy Shevchenko <andy@kernel.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

On Thu, Oct 27, 2022 at 6:29 AM Nathan Moinvaziri <nathan@nathanm.com> wrote:
> On 10/25/2022 12:19 PM, Andy Shevchenko wrote:
> > Looks promising, but may I suggest a few things:
> > 1) have you considered the word-at-a-time use (like strscpy() does)?
>
> Only briefly at the beginning of the function to check for an identical
> comparison and the added check hurt performance for strings that were
> not identical.
>
> On 10/25/2022 12:19 PM, Andy Shevchenko wrote:
>
> > 2) instead of using tolower() on both sides,  have you considered
> > (with the above in mind) to use XOR over words and if they are not 0,
> > check if the result is one of possible combinations of 0x20 and then
> > by excluding the non-letters from the range you may find the
> > difference?
>
> I'm not sure what you mean about the possible combinations of the space
> character. I have not investigated this method.

'a' xor 'A' == 0x20 (same for all the letters.
That's why we have a specific _tolower() in vsprintf.c.

> According to my previous findings the check for c1 != c2 does perform
> better for strings that are at least 25% or more the same. I was able to
> get even more performance out of it by changing tolower() to use a
> different hash table than the one used for the is*() functions. By using
> a pre-generated hash table for both islower() and isupper() it is
> possible to remove the branch where ever those functions are used,
> including in strcasecmp. This method I've seen employed in the Android
> code base and also in cURL. Using it would add additional 2x256 bytes to
> the code size for the tables.

Rasmus raised a good question, where do we actually need the
performant strcasecmp()?

-- 
With Best Regards,
Andy Shevchenko