| Message ID | 20250407-imp_str_perf-v1-1-ed95d52964a4@quicinc.com (mailing list archive) |
|---|---|
| State | Rejected |
| Headers | show |
| Series | lib/string: Improve performance for both strstarts() and str_has_prefix() | expand |
On Mon, Apr 07, 2025 at 09:15:04PM +0800, Zijun Hu wrote: > From: Zijun Hu <quic_zijuhu@quicinc.com> > > strstarts() is frequently invoked to test if a string has another string > as prefix, but its performance is degraded by the strlen() loop contained. > > Improve its performance by eliminating the strlen() loop. NAK. First of all, this function is supposed to be run against constant string literals. Second, this commit message has zero proofs to tell if there is actual performance downgrage even in the case when prefix is not a constant string literal.
On 2025/4/7 21:51, Andy Shevchenko wrote: > First of all, this function is supposed to be run against constant string literals. for strstarts(s, "prefix"), strlen("prefix") should *NOT* be compile time constant. it is a loop and unavoidable to have strlen("prefix") iterations. > Second, this commit message has zero proofs to tell if there is actual performance > downgrage even in the case when prefix is not a constant string literal. for either constant string or non constant string. this patch eliminating a loop which have strlen()iterations. i feel it is obvious it can improve performance.
On Mon, Apr 07, 2025 at 10:33:34PM +0800, Zijun Hu wrote: > On 2025/4/7 21:51, Andy Shevchenko wrote: > > First of all, this function is supposed to be run against constant string literals. > > for strstarts(s, "prefix"), strlen("prefix") should *NOT* be compile > time constant. it is a loop and unavoidable to have strlen("prefix") > iterations. What do you mean by that? Compiler uses __builtin_strlen() and it *IS* a compile-time constant. Just check it. > > Second, this commit message has zero proofs to tell if there is actual performance > > downgrage even in the case when prefix is not a constant string literal. > > for either constant string or non constant string. this patch > eliminating a loop which have strlen()iterations. i feel it is obvious > it can improve performance. No, it's not.
On 2025/4/7 22:39, Andy Shevchenko wrote: >> for strstarts(s, "prefix"), strlen("prefix") should *NOT* be compile >> time constant. it is a loop and unavoidable to have strlen("prefix") >> iterations. > What do you mean by that? Compiler uses __builtin_strlen() and it *IS* > a compile-time constant. Just check it. thank you Andy for this hints. let me do more investigation about strlen() within strstarts(s, "prefix").
On Mon, Apr 07, 2025 at 09:15:04PM +0800, Zijun Hu wrote: > From: Zijun Hu <quic_zijuhu@quicinc.com> > > strstarts() is frequently invoked to test if a string has another string > as prefix, but its performance is degraded by the strlen() loop contained. > > Improve its performance by eliminating the strlen() loop. So, as Andy already said: no, this is very unlikely to be a performance improvement, and if it is, you'll need to show the numbers (and likely the reason _why_, in the form of assembly output, etc). The reason this isn't going to be an improvement is because strlen($string_constant) is optimized by the compiler into a integral constant value. So you'd be replacing a potentially inline constant with an explicit function call. That will be much more expensive. With almost 300 users: $ git grep 'strstarts' | wc -l 198 Only 38 are _not_ using a string constant: $ git grep 'strstarts' | grep -v '"' | wc -l 38 Additionally, there is no "loop". strlen() of a runtime string would be evaluated once. -Kees
On 2025/4/8 00:17, Kees Cook wrote: >> strstarts() is frequently invoked to test if a string has another string >> as prefix, but its performance is degraded by the strlen() loop contained. >> >> Improve its performance by eliminating the strlen() loop. > So, as Andy already said: no, this is very unlikely to be a performance > improvement, and if it is, you'll need to show the numbers (and likely > the reason _why_, in the form of assembly output, etc). > agree. > The reason this isn't going to be an improvement is because > strlen($string_constant) is optimized by the compiler into a integral > constant value. So you'd be replacing a potentially inline constant with will confirm if strlen() within strstarts() is compile-time constant. > an explicit function call. That will be much more expensive. strstarts() has a strncmp() function call as well even if it is inline > > With almost 300 users: > $ git grep 'strstarts' | wc -l > 198 > > Only 38 are _not_ using a string constant: > $ git grep 'strstarts' | grep -v '"' | wc -l > 38 > > Additionally, there is no "loop". strlen() of a runtime string would be > evaluated once. > strlen() contains a loop which has strlen() char comparisons > -Kees
Hi Zijun, kernel test robot noticed the following build errors: [auto build test ERROR on 0af2f6be1b4281385b618cb86ad946eded089ac8] url: https://github.com/intel-lab-lkp/linux/commits/Zijun-Hu/lib-string-Improve-strstarts-performance/20250407-212519 base: 0af2f6be1b4281385b618cb86ad946eded089ac8 patch link: https://lore.kernel.org/r/20250407-imp_str_perf-v1-1-ed95d52964a4%40quicinc.com patch subject: [PATCH 1/2] lib/string: Improve strstarts() performance config: riscv-randconfig-002-20250408 (https://download.01.org/0day-ci/archive/20250408/202504082037.VtV65Bnb-lkp@intel.com/config) compiler: clang version 21.0.0git (https://github.com/llvm/llvm-project 92c93f5286b9ff33f27ff694d2dc33da1c07afdd) reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250408/202504082037.VtV65Bnb-lkp@intel.com/reproduce) If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags | Reported-by: kernel test robot <lkp@intel.com> | Closes: https://lore.kernel.org/oe-kbuild-all/202504082037.VtV65Bnb-lkp@intel.com/ All errors (new ones prefixed by >>): >> ld.lld: error: undefined hidden symbol: __efistub_strstarts >>> referenced by gop.c:119 (drivers/firmware/efi/libstub/gop.c:119) >>> gop.stub.o:(__efistub_efi_parse_option_graphics) in archive ./drivers/firmware/efi/libstub/lib.a >>> referenced by gop.c:42 (drivers/firmware/efi/libstub/gop.c:42) >>> gop.stub.o:(__efistub_efi_parse_option_graphics) in archive ./drivers/firmware/efi/libstub/lib.a >>> referenced by gop.c:42 (drivers/firmware/efi/libstub/gop.c:42) >>> gop.stub.o:(__efistub_efi_parse_option_graphics) in archive ./drivers/firmware/efi/libstub/lib.a >>> referenced 3 more times
diff --git a/include/linux/string.h b/include/linux/string.h index 01621ad0f598ccdfae819b1a5058607e79d8a751..e5f7defa277572719e1dbfdd264f3de6ef8544f1 100644 --- a/include/linux/string.h +++ b/include/linux/string.h @@ -345,15 +345,7 @@ extern ssize_t memory_read_from_buffer(void *to, size_t count, loff_t *ppos, int ptr_to_hashval(const void *ptr, unsigned long *hashval_out); -/** - * strstarts - does @str start with @prefix? - * @str: string to examine - * @prefix: prefix to look for. - */ -static inline bool strstarts(const char *str, const char *prefix) -{ - return strncmp(str, prefix, strlen(prefix)) == 0; -} +bool strstarts(const char *str, const char *prefix); size_t memweight(const void *ptr, size_t bytes); diff --git a/lib/string.c b/lib/string.c index eb4486ed40d259e43dfb63d76c2bd57ef74e2fd1..ea52c8509328358e436766b1186a82419d45089d 100644 --- a/lib/string.c +++ b/lib/string.c @@ -285,6 +285,28 @@ int strcmp(const char *cs, const char *ct) EXPORT_SYMBOL(strcmp); #endif +/** + * strstarts - does @str start with @prefix? + * @str: string to examine + * @prefix: prefix to look for. + */ +bool strstarts(const char *str, const char *prefix) +{ + unsigned char c1, c2; + + do { + c1 = *str++; + c2 = *prefix++; + + if (c1 != c2) + return c2 == '\0'; + + } while (c2 != '\0'); + + return true; +} +EXPORT_SYMBOL(strstarts); + #ifndef __HAVE_ARCH_STRNCMP /** * strncmp - Compare two length-limited strings