From: Nathan Moinvaziri <nathan@nathanm.com>
To: Andy Shevchenko <andy.shevchenko@gmail.com>
Cc: Andy Shevchenko <andy@kernel.org>,
"linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>
Subject: Re: [PATCH] lib/string.c: Improve strcasecmp speed by not lowering if chars match
Date: Thu, 27 Oct 2022 03:29:07 +0000 [thread overview]
Message-ID: <d9c73675-1060-fd8b-958f-50793dca4db4@nathanm.com> (raw)
In-Reply-To: <CAHp75VeNwvAppVdn+wqAYkzDS115ZuJqm9=gu0hyVoz14qWQkA@mail.gmail.com>
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.
...
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.
I've put together a Quick Benchmark that shows the comparison between
the different methods:
https://quick-bench.com/q/l5DkYQO-CcMxQUu5MjZiqZ8M-Y0
Nathan
next prev parent reply other threads:[~2022-10-27 3:30 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-25 1:46 [PATCH] lib/string.c: Improve strcasecmp speed by not lowering if chars match Nathan Moinvaziri
2022-10-25 8:00 ` Andy Shevchenko
2022-10-25 9:03 ` Andy Shevchenko
2022-10-25 17:53 ` Nathan Moinvaziri
2022-10-25 19:19 ` Andy Shevchenko
2022-10-27 3:29 ` Nathan Moinvaziri [this message]
2022-10-27 6:31 ` Andy Shevchenko
2022-10-25 19:32 ` Christophe JAILLET
2022-10-25 23:27 ` Nathan Moinvaziri
2022-10-25 19:55 ` Rasmus Villemoes
2022-10-25 22:37 ` Nathan Moinvaziri
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=d9c73675-1060-fd8b-958f-50793dca4db4@nathanm.com \
--to=nathan@nathanm.com \
--cc=andy.shevchenko@gmail.com \
--cc=andy@kernel.org \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.