[PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[Wilco Dijkstra]

Hi James,

This looks correct to me, but what about performance?

+  if (isalpha(*needle)) {
+    const char a[] = { tolower(*needle), toupper(*needle), '\0'};
+    haystack = strpbrk(haystack, a);

strpbrk has a high startup overhead and is slow overall. A basic
while loop checking tolower (haystack[0]) will be faster here.

+  } else {
+    haystack = strchr(haystack, *needle);
+  }
+  if (haystack == NULL || needle[1] == '\0')
+    return (char *)haystack;

This should help a bit in some cases, but searching for the first
character match improves performance the most if you check for
a full match before the expensive initialization of the main algorithm
(similar to what strstr does).

Note that using strchr on a large haystack may actually result in a
slowdown given that the matching algorithms are faster than strchr
on typical inputs (due to being superlinear).

Cheers,
Wilco

[PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[James Tirta Halim]

---
 string/strcasestr.c | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

diff --git a/string/strcasestr.c b/string/strcasestr.c
index 2f6b4f8641..aca41211dd 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -55,6 +55,30 @@
 #endif
 
 
+static inline char *__attribute__ ((always_inline))
+strcasechr (const char *s, char c)
+{
+  if (isalpha(c)) {
+    /* May have optimized strcspn? */
+#if defined __sparc__ || defined __sparc || defined __x86_64__ || defined _M_X64 || defined __s390x__ || defined i386 || defined __i386__ || defined __i386 || defined _M_IX86 || defined __PPC64__ || defined __ppc64__ || defined _ARCH_PPC64 || _ARCH_PWR8
+    const char a[] = {tolower(c), toupper(c), '\0'};
+    s = (char *)strcspn(s, a);
+#else
+    c = tolower(c);
+    while (*s && tolower(*s) != c)
+      ++s;
+#endif
+    if (*s != '\0')
+      return (char *)s;
+  } else {
+    s = strchr(s, c);
+    if (s != NULL)
+      return (char *)s;
+  }
+  return NULL;
+}
+
+
 /* Find the first occurrence of NEEDLE in HAYSTACK, using
    case-insensitive comparison.  This function gives unspecified
    results in multibyte locales.  */
@@ -68,6 +92,10 @@ STRCASESTR (const char *haystack, const char *needle)
   if (needle[0] == '\0')
     return (char *) haystack;
 
+  haystack = strcasechr (haystack, *needle);
+  if (haystack == NULL || needle[1] == '\0')
+	  return (char *) haystack;
+
   /* Ensure HAYSTACK length is at least as long as NEEDLE length.
      Since a match may occur early on in a huge HAYSTACK, use strnlen
      and read ahead a few cachelines for improved performance.  */
@@ -75,6 +103,9 @@ STRCASESTR (const char *haystack, const char *needle)
   haystack_len = __strnlen (haystack, needle_len + 256);
   if (haystack_len < needle_len)
     return NULL;
+  
+  if (strncasecmp (haystack, needle, needle_len) == 0)
+    return (char *) haystack;
 
   /* Perform the search.  Abstract memory is considered to be an array
      of 'unsigned char' values, not an array of 'char' values.  See
-- 
2.42.0

[PATCH 1/2] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[James Tirta Halim]

---
 string/strcasestr.c | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

diff --git a/string/strcasestr.c b/string/strcasestr.c
index 2f6b4f8641..aca41211dd 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -55,6 +55,30 @@
 #endif
 
 
+static inline char *__attribute__ ((always_inline))
+strcasechr (const char *s, char c)
+{
+  if (isalpha(c)) {
+    /* May have optimized strcspn? */
+#if defined __sparc__ || defined __sparc || defined __x86_64__ || defined _M_X64 || defined __s390x__ || defined i386 || defined __i386__ || defined __i386 || defined _M_IX86 || defined __PPC64__ || defined __ppc64__ || defined _ARCH_PPC64 || defined _ARCH_PWR8
+    const char a[] = {tolower(c), toupper(c), '\0'};
+    s = (char *)strcspn(s, a);
+#else
+    c = tolower(c);
+    while (*s && tolower(*s) != c)
+      ++s;
+#endif
+    if (*s != '\0')
+      return (char *)s;
+  } else {
+    s = strchr(s, c);
+    if (s != NULL)
+      return (char *)s;
+  }
+  return NULL;
+}
+
+
 /* Find the first occurrence of NEEDLE in HAYSTACK, using
    case-insensitive comparison.  This function gives unspecified
    results in multibyte locales.  */
@@ -68,6 +92,10 @@ STRCASESTR (const char *haystack, const char *needle)
   if (needle[0] == '\0')
     return (char *) haystack;
 
+  haystack = strcasechr (haystack, *needle);
+  if (haystack == NULL || needle[1] == '\0')
+	  return (char *) haystack;
+
   /* Ensure HAYSTACK length is at least as long as NEEDLE length.
      Since a match may occur early on in a huge HAYSTACK, use strnlen
      and read ahead a few cachelines for improved performance.  */
@@ -75,6 +103,9 @@ STRCASESTR (const char *haystack, const char *needle)
-  haystack_len = __strnlen (haystack, needle_len + 256);
+  haystack_len = __strnlen (haystack, needle_len);
   if (haystack_len < needle_len)
     return NULL;
+  
+  if (strncasecmp (haystack, needle, needle_len) == 0)
+    return (char *) haystack;
+  haystack_len += __strnlen(haystack + haystack_len, 256);
 
   /* Perform the search.  Abstract memory is considered to be an array
      of 'unsigned char' values, not an array of 'char' values.  See
-- 
2.42.0

Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[Adhemerval Zanella Netto]

On 14/10/23 05:32, James Tirta Halim wrote:
> ---
>  string/strcasestr.c | 31 +++++++++++++++++++++++++++++++
>  1 file changed, 31 insertions(+)
> 
> diff --git a/string/strcasestr.c b/string/strcasestr.c
> index 2f6b4f8641..aca41211dd 100644
> --- a/string/strcasestr.c
> +++ b/string/strcasestr.c
> @@ -55,6 +55,30 @@
>  #endif
>  
>  
> +static inline char *__attribute__ ((always_inline))
> +strcasechr (const char *s, char c)
> +{
> +  if (isalpha(c)) {
> +    /* May have optimized strcspn? */
> +#if defined __sparc__ || defined __sparc || defined __x86_64__ || defined _M_X64 || defined __s390x__ || defined i386 || defined __i386__ || defined __i386 || defined _M_IX86 || defined __PPC64__ || defined __ppc64__ || defined _ARCH_PPC64 || _ARCH_PWR8
> +    const char a[] = {tolower(c), toupper(c), '\0'};

We have the sysdep folder exactly to provide such macros if requires, for instance
the file sysdeps/generic/string-fzi.h.

So if this optimization is really worth, the best way to provide would be through
a generic implementation like:

  static __always_inline char *
  strcasechr (const char *s, char c)
  {
    /* Generic implementation.  */
  }

And then on each architecture where using strcspn is better to add a string-xxx.h
override.

> +    s = (char *)strcspn(s, a);
> +#else
> +    c = tolower(c);
> +    while (*s && tolower(*s) != c)
> +      ++s;
> +#endif
> +    if (*s != '\0')
> +      return (char *)s;
> +  } else {
> +    s = strchr(s, c);
> +    if (s != NULL)
> +      return (char *)s;
> +  }
> +  return NULL;
> +}
> +
> +
>  /* Find the first occurrence of NEEDLE in HAYSTACK, using
>     case-insensitive comparison.  This function gives unspecified
>     results in multibyte locales.  */
> @@ -68,6 +92,10 @@ STRCASESTR (const char *haystack, const char *needle)
>    if (needle[0] == '\0')
>      return (char *) haystack;
>  
> +  haystack = strcasechr (haystack, *needle);
> +  if (haystack == NULL || needle[1] == '\0')
> +	  return (char *) haystack;
> +
>    /* Ensure HAYSTACK length is at least as long as NEEDLE length.
>       Since a match may occur early on in a huge HAYSTACK, use strnlen
>       and read ahead a few cachelines for improved performance.  */
> @@ -75,6 +103,9 @@ STRCASESTR (const char *haystack, const char *needle)
>    haystack_len = __strnlen (haystack, needle_len + 256);
>    if (haystack_len < needle_len)
>      return NULL;
> +  
> +  if (strncasecmp (haystack, needle, needle_len) == 0)
> +    return (char *) haystack;
>  
>    /* Perform the search.  Abstract memory is considered to be an array
>       of 'unsigned char' values, not an array of 'char' values.  See

Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[Wilco Dijkstra]

Hi Adhemerval/James,

> We have the sysdep folder exactly to provide such macros if requires, for instance
> the file sysdeps/generic/string-fzi.h.
>
> So if this optimization is really worth, the best way to provide would be through
> a generic implementation like:

I ran it on my x86 machine (with proper AVX-512), and the "optimized" strcspn is
slower than the simple byte loop on bench-strcasestr. While the benchmark could
likely be improved, it shows this target specific optimization isn't worth doing.

Cheers,
Wilco

Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[Noah Goldstein]

On Mon, Oct 16, 2023 at 8:52 AM Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
>
> Hi Adhemerval/James,
>
> > We have the sysdep folder exactly to provide such macros if requires, for instance
> > the file sysdeps/generic/string-fzi.h.
> >
> > So if this optimization is really worth, the best way to provide would be through
> > a generic implementation like:
>
> I ran it on my x86 machine (with proper AVX-512), and the "optimized" strcspn is
> slower than the simple byte loop on bench-strcasestr.

"optimized" being the sse4 version?

> While the benchmark could
> likely be improved, it shows this target specific optimization isn't worth doing.
>
> Cheers,
> Wilco

Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[Wilco Dijkstra]

Hi Noah,

>> I ran it on my x86 machine (with proper AVX-512), and the "optimized" strcspn is
>> slower than the simple byte loop on bench-strcasestr.
>
> "optimized" being the sse4 version?

No idea, I just ran the benchmark as a smoke test. However this code looks wrong:

+    s = (char *)strcspn(s, a);

Cheers,
Wilco

[PATCH] strcasestr: try to find non-alpha char in NEEDLE

[James Tirta Halim]

---
 string/strcasestr.c | 37 ++++++++++++++++++++++++++++++-------
 1 file changed, 30 insertions(+), 7 deletions(-)

diff --git a/string/strcasestr.c b/string/strcasestr.c
index 2f6b4f8641..65eae2f047 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -54,7 +54,6 @@
 #define STRCASESTR __strcasestr
 #endif
 
-
 /* Find the first occurrence of NEEDLE in HAYSTACK, using
    case-insensitive comparison.  This function gives unspecified
    results in multibyte locales.  */
@@ -63,18 +62,42 @@ STRCASESTR (const char *haystack, const char *needle)
 {
   size_t needle_len; /* Length of NEEDLE.  */
   size_t haystack_len; /* Known minimum length of HAYSTACK.  */
+  const char *h, *n;
 
   /* Handle empty NEEDLE special case.  */
   if (needle[0] == '\0')
     return (char *) haystack;
 
-  /* Ensure HAYSTACK length is at least as long as NEEDLE length.
-     Since a match may occur early on in a huge HAYSTACK, use strnlen
-     and read ahead a few cachelines for improved performance.  */
-  needle_len = strlen (needle);
-  haystack_len = __strnlen (haystack, needle_len + 256);
-  if (haystack_len < needle_len)
+  /* Try to find a non-alphanumeric character in NEEDLE to pass to
+     strchr() while checking if HAYSTACK is as long as NEEDLE.  */
+  for (h = haystack, n = needle; *h && isalpha (*n); ++h, ++n);
+  if (__glibc_unlikely (*h == '\0'))
     return NULL;
+  if (*n) {
+    size_t shift;
+    shift = n - needle;
+    haystack = strchr (h + shift, *n);
+    if (__glibc_unlikely (haystack == NULL))
+      return NULL;
+    haystack -= shift;
+    /* Check if we have an early match. */
+    for (h = haystack, n = needle; TOLOWER (*h) == TOLOWER (*n) && *h; ++h, ++n);
+    if (*n == '\0')
+      return (char *)haystack;
+    if (__glibc_unlikely (*h == '\0'))
+      return NULL;
+    if ((size_t) (n - needle) > shift)
+      shift = n - needle;
+  /* Since a match may occur early on in a huge HAYSTACK, use strnlen
+     and read ahead a few cachelines for improved performance.  */
+    needle_len = shift + strlen (needle + shift);
+    haystack_len = shift + __strnlen (h + shift, 256);
+    if (__glibc_unlikely (haystack_len < needle_len))
+      return NULL;
+  } else {
+    needle_len = n - needle;
+    haystack_len = needle_len + __strnlen (haystack + needle_len, 256);
+  }
 
   /* Perform the search.  Abstract memory is considered to be an array
      of 'unsigned char' values, not an array of 'char' values.  See
-- 
2.43.0

Re: [PATCH] strcasestr: try to find non-alpha char in NEEDLE

[Carlos O'Donell]

On 11/28/23 09:01, James Tirta Halim wrote:
> ---

James,

May you please clarify your copyright assignment status?

Please review "2.1. Copyright FSF or disclaimer" in the contribution checklist:
https://sourceware.org/glibc/wiki/Contribution%20checklist#Copyright_FSF_or_disclaimer


>  string/strcasestr.c | 37 ++++++++++++++++++++++++++++++-------
>  1 file changed, 30 insertions(+), 7 deletions(-)
> 
> diff --git a/string/strcasestr.c b/string/strcasestr.c
> index 2f6b4f8641..65eae2f047 100644
> --- a/string/strcasestr.c
> +++ b/string/strcasestr.c
> @@ -54,7 +54,6 @@
>  #define STRCASESTR __strcasestr
>  #endif
>  
> -
>  /* Find the first occurrence of NEEDLE in HAYSTACK, using
>     case-insensitive comparison.  This function gives unspecified
>     results in multibyte locales.  */
> @@ -63,18 +62,42 @@ STRCASESTR (const char *haystack, const char *needle)
>  {
>    size_t needle_len; /* Length of NEEDLE.  */
>    size_t haystack_len; /* Known minimum length of HAYSTACK.  */
> +  const char *h, *n;
>  
>    /* Handle empty NEEDLE special case.  */
>    if (needle[0] == '\0')
>      return (char *) haystack;
>  
> -  /* Ensure HAYSTACK length is at least as long as NEEDLE length.
> -     Since a match may occur early on in a huge HAYSTACK, use strnlen
> -     and read ahead a few cachelines for improved performance.  */
> -  needle_len = strlen (needle);
> -  haystack_len = __strnlen (haystack, needle_len + 256);
> -  if (haystack_len < needle_len)
> +  /* Try to find a non-alphanumeric character in NEEDLE to pass to
> +     strchr() while checking if HAYSTACK is as long as NEEDLE.  */
> +  for (h = haystack, n = needle; *h && isalpha (*n); ++h, ++n);
> +  if (__glibc_unlikely (*h == '\0'))
>      return NULL;
> +  if (*n) {
> +    size_t shift;
> +    shift = n - needle;
> +    haystack = strchr (h + shift, *n);
> +    if (__glibc_unlikely (haystack == NULL))
> +      return NULL;
> +    haystack -= shift;
> +    /* Check if we have an early match. */
> +    for (h = haystack, n = needle; TOLOWER (*h) == TOLOWER (*n) && *h; ++h, ++n);
> +    if (*n == '\0')
> +      return (char *)haystack;
> +    if (__glibc_unlikely (*h == '\0'))
> +      return NULL;
> +    if ((size_t) (n - needle) > shift)
> +      shift = n - needle;
> +  /* Since a match may occur early on in a huge HAYSTACK, use strnlen
> +     and read ahead a few cachelines for improved performance.  */
> +    needle_len = shift + strlen (needle + shift);
> +    haystack_len = shift + __strnlen (h + shift, 256);
> +    if (__glibc_unlikely (haystack_len < needle_len))
> +      return NULL;
> +  } else {
> +    needle_len = n - needle;
> +    haystack_len = needle_len + __strnlen (haystack + needle_len, 256);
> +  }
>  
>    /* Perform the search.  Abstract memory is considered to be an array
>       of 'unsigned char' values, not an array of 'char' values.  See

-- 
Cheers,
Carlos.

[PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr

[James Tirta Halim]

---
 string/strcasestr.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/string/strcasestr.c b/string/strcasestr.c
index 2f6b4f8641..295cbf364d 100644
--- a/string/strcasestr.c
+++ b/string/strcasestr.c
@@ -67,6 +67,14 @@ STRCASESTR (const char *haystack, const char *needle)
   /* Handle empty NEEDLE special case.  */
   if (needle[0] == '\0')
     return (char *) haystack;
+  if (isalpha(*needle)) {
+    const char a[] = { tolower(*needle), toupper(*needle), '\0'};
+    haystack = strpbrk(haystack, a);
+  } else {
+    haystack = strchr(haystack, *needle);
+  }
+  if (haystack == NULL || needle[1] == '\0')
+    return (char *)haystack;
 
   /* Ensure HAYSTACK length is at least as long as NEEDLE length.
      Since a match may occur early on in a huge HAYSTACK, use strnlen
-- 
2.42.0