* [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
@ 2023-09-07 22:14 Wilco Dijkstra
2023-10-14 8:32 ` James Tirta Halim
` (2 more replies)
0 siblings, 3 replies; 10+ messages in thread
From: Wilco Dijkstra @ 2023-09-07 22:14 UTC (permalink / raw)
To: tirtajames45; +Cc: 'GNU C Library'
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
2023-09-07 22:14 [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr Wilco Dijkstra
@ 2023-10-14 8:32 ` James Tirta Halim
2023-10-16 12:59 ` Adhemerval Zanella Netto
2023-10-14 8:56 ` [PATCH 1/2] " James Tirta Halim
2023-11-28 14:01 ` [PATCH] strcasestr: try to find non-alpha char in NEEDLE James Tirta Halim
2 siblings, 1 reply; 10+ messages in thread
From: James Tirta Halim @ 2023-10-14 8:32 UTC (permalink / raw)
To: wilco.dijkstra; +Cc: libc-alpha, tirtajames45
---
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH 1/2] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
2023-09-07 22:14 [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr Wilco Dijkstra
2023-10-14 8:32 ` James Tirta Halim
@ 2023-10-14 8:56 ` James Tirta Halim
2023-11-28 14:01 ` [PATCH] strcasestr: try to find non-alpha char in NEEDLE James Tirta Halim
2 siblings, 0 replies; 10+ messages in thread
From: James Tirta Halim @ 2023-10-14 8:56 UTC (permalink / raw)
To: wilco.dijkstra; +Cc: libc-alpha, tirtajames45
---
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
2023-10-14 8:32 ` James Tirta Halim
@ 2023-10-16 12:59 ` Adhemerval Zanella Netto
2023-10-16 13:52 ` Wilco Dijkstra
0 siblings, 1 reply; 10+ messages in thread
From: Adhemerval Zanella Netto @ 2023-10-16 12:59 UTC (permalink / raw)
To: James Tirta Halim, wilco.dijkstra; +Cc: libc-alpha
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
2023-10-16 12:59 ` Adhemerval Zanella Netto
@ 2023-10-16 13:52 ` Wilco Dijkstra
2023-10-16 16:56 ` Noah Goldstein
0 siblings, 1 reply; 10+ messages in thread
From: Wilco Dijkstra @ 2023-10-16 13:52 UTC (permalink / raw)
To: Adhemerval Zanella Netto, James Tirta Halim; +Cc: libc-alpha
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
2023-10-16 13:52 ` Wilco Dijkstra
@ 2023-10-16 16:56 ` Noah Goldstein
2023-10-17 9:57 ` Wilco Dijkstra
0 siblings, 1 reply; 10+ messages in thread
From: Noah Goldstein @ 2023-10-16 16:56 UTC (permalink / raw)
To: Wilco Dijkstra; +Cc: Adhemerval Zanella Netto, James Tirta Halim, libc-alpha
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
2023-10-16 16:56 ` Noah Goldstein
@ 2023-10-17 9:57 ` Wilco Dijkstra
0 siblings, 0 replies; 10+ messages in thread
From: Wilco Dijkstra @ 2023-10-17 9:57 UTC (permalink / raw)
To: Noah Goldstein; +Cc: Adhemerval Zanella Netto, James Tirta Halim, libc-alpha
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH] strcasestr: try to find non-alpha char in NEEDLE
2023-09-07 22:14 [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr Wilco Dijkstra
2023-10-14 8:32 ` James Tirta Halim
2023-10-14 8:56 ` [PATCH 1/2] " James Tirta Halim
@ 2023-11-28 14:01 ` James Tirta Halim
2023-12-04 14:44 ` Carlos O'Donell
2 siblings, 1 reply; 10+ messages in thread
From: James Tirta Halim @ 2023-11-28 14:01 UTC (permalink / raw)
To: wilco.dijkstra; +Cc: libc-alpha, tirtajames45
---
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] strcasestr: try to find non-alpha char in NEEDLE
2023-11-28 14:01 ` [PATCH] strcasestr: try to find non-alpha char in NEEDLE James Tirta Halim
@ 2023-12-04 14:44 ` Carlos O'Donell
0 siblings, 0 replies; 10+ messages in thread
From: Carlos O'Donell @ 2023-12-04 14:44 UTC (permalink / raw)
To: James Tirta Halim, wilco.dijkstra, Adhemerval Zanella; +Cc: libc-alpha
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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr
@ 2023-09-06 17:42 James Tirta Halim
0 siblings, 0 replies; 10+ messages in thread
From: James Tirta Halim @ 2023-09-06 17:42 UTC (permalink / raw)
To: libc-alpha; +Cc: 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
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2023-12-04 14:44 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-07 22:14 [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr Wilco Dijkstra
2023-10-14 8:32 ` James Tirta Halim
2023-10-16 12:59 ` Adhemerval Zanella Netto
2023-10-16 13:52 ` Wilco Dijkstra
2023-10-16 16:56 ` Noah Goldstein
2023-10-17 9:57 ` Wilco Dijkstra
2023-10-14 8:56 ` [PATCH 1/2] " James Tirta Halim
2023-11-28 14:01 ` [PATCH] strcasestr: try to find non-alpha char in NEEDLE James Tirta Halim
2023-12-04 14:44 ` Carlos O'Donell
-- strict thread matches above, loose matches on Subject: below --
2023-09-06 17:42 [PATCH] strcasestr: check if ne[0] is in hs with strchr or strpbrk as does strstr James Tirta Halim
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).