[PATCH 0/2] lib/string: Improve performance for both strstarts() and str_has_prefix()

[PATCH 0/2] lib/string: Improve performance for both strstarts() and str_has_prefix()

[Zijun Hu]

Signed-off-by: Zijun Hu <quic_zijuhu@quicinc.com>
---
Zijun Hu (2):
      lib/string: Improve strstarts() performance
      lib/string: Improve str_has_prefix() performance

 include/linux/string.h | 31 ++--------------------------
 lib/string.c           | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+), 29 deletions(-)
---
base-commit: 0af2f6be1b4281385b618cb86ad946eded089ac8
change-id: 20250407-imp_str_perf-183d81d27311

Best regards,
-- 
Zijun Hu <quic_zijuhu@quicinc.com>

[PATCH 1/2] lib/string: Improve strstarts() performance

[Zijun Hu]

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.

Link: https://lore.kernel.org/all/20250113234643.GA3631169-robh@kernel.org
Signed-off-by: Zijun Hu <quic_zijuhu@quicinc.com>
Cc: Rob Herring (Arm) <robh@kernel.org>
---
 include/linux/string.h | 10 +---------
 lib/string.c           | 22 ++++++++++++++++++++++
 2 files changed, 23 insertions(+), 9 deletions(-)

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

-- 
2.34.1

[PATCH 2/2] lib/string: Improve str_has_prefix() performance

[Zijun Hu]

From: Zijun Hu <quic_zijuhu@quicinc.com>

str_has_prefix() is frequently invoked to return length of the prefix
string 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.

Link: https://lore.kernel.org/all/20250113234643.GA3631169-robh@kernel.org
Signed-off-by: Zijun Hu <quic_zijuhu@quicinc.com>
Cc: Rob Herring (Arm) <robh@kernel.org>
---
 include/linux/string.h | 21 +--------------------
 lib/string.c           | 33 +++++++++++++++++++++++++++++++++
 2 files changed, 34 insertions(+), 20 deletions(-)

diff --git a/include/linux/string.h b/include/linux/string.h
index e5f7defa277572719e1dbfdd264f3de6ef8544f1..394b76666ece0924c50264aaca39784d5630a2fe 100644
--- a/include/linux/string.h
+++ b/include/linux/string.h
@@ -533,25 +533,6 @@ void memcpy_and_pad(void *dest, size_t dest_len, const void *src, size_t count,
 	       sizeof(*(obj)) - offsetof(typeof(*(obj)), member));	\
 })
 
-/**
- * str_has_prefix - Test if a string has a given prefix
- * @str: The string to test
- * @prefix: The string to see if @str starts with
- *
- * A common way to test a prefix of a string is to do:
- *  strncmp(str, prefix, sizeof(prefix) - 1)
- *
- * But this can lead to bugs due to typos, or if prefix is a pointer
- * and not a constant. Instead use str_has_prefix().
- *
- * Returns:
- * * strlen(@prefix) if @str starts with @prefix
- * * 0 if @str does not start with @prefix
- */
-static __always_inline size_t str_has_prefix(const char *str, const char *prefix)
-{
-	size_t len = strlen(prefix);
-	return strncmp(str, prefix, len) == 0 ? len : 0;
-}
+size_t str_has_prefix(const char *str, const char *prefix);
 
 #endif /* _LINUX_STRING_H_ */
diff --git a/lib/string.c b/lib/string.c
index ea52c8509328358e436766b1186a82419d45089d..17f1a070b190debc3eaeff6d1ae45b55bae69b29 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -332,6 +332,39 @@ int strncmp(const char *cs, const char *ct, size_t count)
 EXPORT_SYMBOL(strncmp);
 #endif
 
+/**
+ * str_has_prefix - Test if a string has a given prefix
+ * @str: The string to test
+ * @prefix: The string to see if @str starts with
+ *
+ * A common way to test a prefix of a string is to do:
+ *  strncmp(str, prefix, sizeof(prefix) - 1)
+ *
+ * But this can lead to bugs due to typos, or if prefix is a pointer
+ * and not a constant. Instead use str_has_prefix().
+ *
+ * Returns:
+ * * strlen(@prefix) if @str starts with @prefix
+ * * 0 if @str does not start with @prefix
+ */
+size_t str_has_prefix(const char *str, const char *prefix)
+{
+	const char *p = prefix;
+	unsigned char c1, c2;
+
+	do {
+		c1 = *str++;
+		c2 = *p++;
+
+		if (c1 != c2)
+			return c2 == '\0' ? p - 1 - prefix : 0;
+
+	} while (c2 != '\0');
+
+	return p - 1 - prefix;
+}
+EXPORT_SYMBOL(str_has_prefix);
+
 #ifndef __HAVE_ARCH_STRCHR
 /**
  * strchr - Find the first occurrence of a character in a string

-- 
2.34.1

Re: [PATCH 0/2] lib/string: Improve performance for both strstarts() and str_has_prefix()

[Andy Shevchenko]

On Mon, Apr 07, 2025 at 09:15:03PM +0800, Zijun Hu wrote:

No information?!
Please, add the performance tests (link to them?) and results here at bare
minimum.

> Signed-off-by: Zijun Hu <quic_zijuhu@quicinc.com>

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/2] lib/string: Improve strstarts() performance

[Andy Shevchenko]

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.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 2/2] lib/string: Improve str_has_prefix() performance

[Andy Shevchenko]

On Mon, Apr 07, 2025 at 09:15:05PM +0800, Zijun Hu wrote:
> From: Zijun Hu <quic_zijuhu@quicinc.com>
> 
> str_has_prefix() is frequently invoked to return length of the prefix
> string 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.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/2] lib/string: Improve strstarts() performance

[Zijun Hu]

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.

Re: [PATCH 1/2] lib/string: Improve strstarts() performance

[Andy Shevchenko]

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.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/2] lib/string: Improve strstarts() performance

[Zijun Hu]

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").

Re: [PATCH 1/2] lib/string: Improve strstarts() performance

[Kees Cook]

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

-- 
Kees Cook

Re: [PATCH 1/2] lib/string: Improve strstarts() performance

[Zijun Hu]

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

Re: [PATCH 1/2] lib/string: Improve strstarts() performance

[kernel test robot]

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

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki