linux-kernel - Re: [PATCH] lib/string.c: Improve strcasecmp speed by not lowering if chars match

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAHp75Vd4Vk0v-T3kfxApGHb-H26KTHgH59DGP3Wm4qBgunDt6A@mail.gmail.com>
Date:   Tue, 25 Oct 2022 11:00:36 +0300
From:   Andy Shevchenko <andy.shevchenko@...il.com>
To:     Nathan Moinvaziri <nathan@...hanm.com>
Cc:     "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andy Shevchenko <andy@...nel.org>
Subject: Re: [PATCH] lib/string.c: Improve strcasecmp speed by not lowering if
 chars match

On Tue, Oct 25, 2022 at 4:46 AM Nathan Moinvaziri <nathan@...hanm.com> wrote:
>
> From fcb0159ee74908f92adc34143657d8ca56e9a811 Mon Sep 17 00:00:00 2001
> From: Nathan Moinvaziri <nathan@...hanm.com>
> Date: Mon, 24 Oct 2022 16:37:59 -0700
> Subject: [PATCH] lib/string.c: Improve strcasecmp speed by not lowering if
>  chars match.

Why is the above in the commit message?

> With strings where many characters match exactly each character is needlessly
> converted to lowercase before comparing. This patch improves the comparison
> by only converting to lowercase after checking that the characters don't match.
>
> The more characters that match exactly the better performance we expect versus
> the old function.
>
> When running tests using Quick Benchmark with two matching 256 character
> strings these changes result in anywhere between ~6-9x speed improvement.
>
> * We use unsigned char instead of int similar to strncasecmp.
> * We only subtract c1 - c2 when they are not equal.

Nobody can take it. Please, read Submitting Patches documentation and
fix your contribution accordingly.

...

>         do {
> -               c1 = tolower(*s1++);
> -               c2 = tolower(*s2++);
> -       } while (c1 == c2 && c1 != 0);
> -       return c1 - c2;
> +               c1 = *s1++;
> +               c2 = *s2++;
> +               if (c1 != c2) {
> +                       c1 = tolower(c1);
> +                       c2 = tolower(c2);
> +                       if (c1 != c2)
> +                               return (int)c1 - (int)c2;
> +               }
> +       } while (c1 != 0);

You tell us that this is more preformant, but have not provided the
numbers. Can we see those, please?

Note, that you basically trash CPU cache lines when characters are not
equal, and before doing that you have a branching. I'm unsure that
your way is more performant than the original one.

-- 
With Best Regards,
Andy Shevchenko