From: Adhemerval Zanella <adhemerval.zanella@linaro.org>
To: libc-alpha@sourceware.org
Cc: Wilco Dijkstra <wdijkstr@arm.com>
Subject: [PATCH 1/4] Improve generic strcspn performance
Date: Thu, 31 Mar 2016 14:01:00 -0000 [thread overview]
Message-ID: <1459432863-20749-2-git-send-email-adhemerval.zanella@linaro.org> (raw)
In-Reply-To: <1459432863-20749-1-git-send-email-adhemerval.zanella@linaro.org>
From: Wilco Dijkstra <wdijkstr@arm.com>
Improve strcspn performance using a much faster algorithm. It is kept simple
so it works well on most targets. It is generally at least 10 times faster
than the existing implementation on bench-strcspn on a few AArch64
implementations, and for some tests 100 times as fast (repeatedly calling
strchr on a small string is extremely slow...).
In fact the string/bits/string2.h inlines make no longer sense, as GCC
already uses strlen if reject is an empty string, strchrnul is 5 times as
fast as __strcspn_c1, while __strcspn_c2 and __strcspn_c3 are slower than
the strcspn main loop for large strings (though reject length 2-4 could be
special cased in the future to gain even more performance).
Tested on x86_64, i686, and aarch64.
* string/Version (libc): Add GLIBC_2.24.
* string/strcspn.c (strcspn): Rewrite function.
* string/bits/string2.h (strcspn): Use __builtin_strcspn.
(__strcspn_c1): Remove inline function.
(__strcspn_c2): Likewise.
(__strcspn_c3): Likewise.
* string/string-inline.c
[SHLIB_COMPAT(libc, GLIBC_2_1_1, GLIBC_2_24)] (__strcspn_c1): Add
compatibility symbol.
[SHLIB_COMPAT(libc, GLIBC_2_1_1, GLIBC_2_24)] (__strcspn_c2):
Likewise.
[SHLIB_COMPAT(libc, GLIBC_2_1_1, GLIBC_2_24)] (__strcspn_c3):
Likewise.
---
ChangeLog | 17 ++++++++++
string/Versions | 2 ++
string/bits/string2.h | 73 ++-----------------------------------------
string/strcspn.c | 44 +++++++++++++++++++++-----
string/string-inlines.c | 40 ++++++++++++++++++++++++
sysdeps/i386/string-inlines.c | 19 +----------
6 files changed, 99 insertions(+), 96 deletions(-)
diff --git a/string/Versions b/string/Versions
index 59bf35a..475c1fd 100644
--- a/string/Versions
+++ b/string/Versions
@@ -80,4 +80,6 @@ libc {
GLIBC_2.6 {
strerror_l;
}
+ GLIBC_2.24 {
+ }
}
diff --git a/string/bits/string2.h b/string/bits/string2.h
index 8200ef1..a8df0db 100644
--- a/string/bits/string2.h
+++ b/string/bits/string2.h
@@ -905,77 +905,10 @@ __stpcpy_small (char *__dest,
/* Return the length of the initial segment of S which
consists entirely of characters not in REJECT. */
-#if !defined _HAVE_STRING_ARCH_strcspn || defined _FORCE_INLINES
-# ifndef _HAVE_STRING_ARCH_strcspn
-# if __GNUC_PREREQ (3, 2)
-# define strcspn(s, reject) \
- __extension__ \
- ({ char __r0, __r1, __r2; \
- (__builtin_constant_p (reject) && __string2_1bptr_p (reject) \
- ? ((__builtin_constant_p (s) && __string2_1bptr_p (s)) \
- ? __builtin_strcspn (s, reject) \
- : ((__r0 = ((const char *) (reject))[0], __r0 == '\0') \
- ? strlen (s) \
- : ((__r1 = ((const char *) (reject))[1], __r1 == '\0') \
- ? __strcspn_c1 (s, __r0) \
- : ((__r2 = ((const char *) (reject))[2], __r2 == '\0') \
- ? __strcspn_c2 (s, __r0, __r1) \
- : (((const char *) (reject))[3] == '\0' \
- ? __strcspn_c3 (s, __r0, __r1, __r2) \
- : __builtin_strcspn (s, reject)))))) \
- : __builtin_strcspn (s, reject)); })
-# else
-# define strcspn(s, reject) \
- __extension__ \
- ({ char __r0, __r1, __r2; \
- (__builtin_constant_p (reject) && __string2_1bptr_p (reject) \
- ? ((__r0 = ((const char *) (reject))[0], __r0 == '\0') \
- ? strlen (s) \
- : ((__r1 = ((const char *) (reject))[1], __r1 == '\0') \
- ? __strcspn_c1 (s, __r0) \
- : ((__r2 = ((const char *) (reject))[2], __r2 == '\0') \
- ? __strcspn_c2 (s, __r0, __r1) \
- : (((const char *) (reject))[3] == '\0' \
- ? __strcspn_c3 (s, __r0, __r1, __r2) \
- : strcspn (s, reject))))) \
- : strcspn (s, reject)); })
-# endif
+#ifndef _HAVE_STRING_ARCH_strcspn
+# if __GNUC_PREREQ (3, 2)
+# define strcspn(s, reject) __builtin_strcspn (s, reject)
# endif
-
-__STRING_INLINE size_t __strcspn_c1 (const char *__s, int __reject);
-__STRING_INLINE size_t
-__strcspn_c1 (const char *__s, int __reject)
-{
- size_t __result = 0;
- while (__s[__result] != '\0' && __s[__result] != __reject)
- ++__result;
- return __result;
-}
-
-__STRING_INLINE size_t __strcspn_c2 (const char *__s, int __reject1,
- int __reject2);
-__STRING_INLINE size_t
-__strcspn_c2 (const char *__s, int __reject1, int __reject2)
-{
- size_t __result = 0;
- while (__s[__result] != '\0' && __s[__result] != __reject1
- && __s[__result] != __reject2)
- ++__result;
- return __result;
-}
-
-__STRING_INLINE size_t __strcspn_c3 (const char *__s, int __reject1,
- int __reject2, int __reject3);
-__STRING_INLINE size_t
-__strcspn_c3 (const char *__s, int __reject1, int __reject2,
- int __reject3)
-{
- size_t __result = 0;
- while (__s[__result] != '\0' && __s[__result] != __reject1
- && __s[__result] != __reject2 && __s[__result] != __reject3)
- ++__result;
- return __result;
-}
#endif
diff --git a/string/strcspn.c b/string/strcspn.c
index 8888919..89ba4ca 100644
--- a/string/strcspn.c
+++ b/string/strcspn.c
@@ -26,16 +26,44 @@
/* Return the length of the maximum initial segment of S
which contains no characters from REJECT. */
size_t
-STRCSPN (const char *s, const char *reject)
+STRCSPN (const char *str, const char *reject)
{
- size_t count = 0;
+ if (reject[0] == '\0' || reject[1] == '\0')
+ return __strchrnul (str, reject [0]) - str;
- while (*s != '\0')
- if (strchr (reject, *s++) == NULL)
- ++count;
- else
- return count;
+ /* Use multiple small memsets to enable inlining on most targets. */
+ unsigned char table[256];
+ unsigned char *p = memset (table, 0, 64);
+ memset (p + 64, 0, 64);
+ memset (p + 128, 0, 64);
+ memset (p + 192, 0, 64);
- return count;
+ unsigned char *s = (unsigned char*) reject;
+ unsigned char tmp;
+ do
+ p[tmp = *s++] = 1;
+ while (tmp);
+
+ s = (unsigned char*) str;
+ if (p[s[0]]) return 0;
+ if (p[s[1]]) return 1;
+ if (p[s[2]]) return 2;
+ if (p[s[3]]) return 3;
+
+ s = (unsigned char *) ((size_t)s & ~3);
+
+ unsigned int c0, c1, c2, c3;
+ do
+ {
+ s += 4;
+ c0 = p[s[0]];
+ c1 = p[s[1]];
+ c2 = p[s[2]];
+ c3 = p[s[3]];
+ }
+ while ((c0 | c1 | c2 | c3) == 0);
+
+ size_t count = s - (unsigned char *) str;
+ return (c0 | c1) != 0 ? count - c0 + 1 : count - c2 + 3;
}
libc_hidden_builtin_def (strcspn)
diff --git a/string/string-inlines.c b/string/string-inlines.c
index 16db3ea..83bdd6c 100644
--- a/string/string-inlines.c
+++ b/string/string-inlines.c
@@ -32,3 +32,43 @@
#undef __NO_INLINE__
#include <bits/string.h>
#include <bits/string2.h>
+
+#include "shlib-compat.h"
+
+#if SHLIB_COMPAT (libc, GLIBC_2_1_1, GLIBC_2_24)
+/* The inline functions are not used from GLIBC 2.24 and forward, however
+ they are required to provide the symbols through string-inlines.c
+ (if inlining is not possible for compatibility reasons). */
+size_t
+__old_strcspn_c1 (const char *__s, int __reject)
+{
+ size_t __result = 0;
+ while (__s[__result] != '\0' && __s[__result] != __reject)
+ ++__result;
+ return __result;
+}
+compat_symbol (libc, __old_strcspn_c1, __strcspn_c1, GLIBC_2_1_1);
+
+size_t
+__old_strcspn_c2 (const char *__s, int __reject1, int __reject2)
+{
+ size_t __result = 0;
+ while (__s[__result] != '\0' && __s[__result] != __reject1
+ && __s[__result] != __reject2)
+ ++__result;
+ return __result;
+}
+compat_symbol (libc, __old_strcspn_c2, __strcspn_c2, GLIBC_2_1_1);
+
+size_t
+__old_strcspn_c3 (const char *__s, int __reject1, int __reject2,
+ int __reject3)
+{
+ size_t __result = 0;
+ while (__s[__result] != '\0' && __s[__result] != __reject1
+ && __s[__result] != __reject2 && __s[__result] != __reject3)
+ ++__result;
+ return __result;
+}
+compat_symbol (libc, __old_strcspn_c3, __strcspn_c3, GLIBC_2_1_1);
+#endif
diff --git a/sysdeps/i386/string-inlines.c b/sysdeps/i386/string-inlines.c
index c7de270..64d80e8 100644
--- a/sysdeps/i386/string-inlines.c
+++ b/sysdeps/i386/string-inlines.c
@@ -15,27 +15,10 @@
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
-/* <bits/string.h> and <bits/string2.h> declare some extern inline
- functions. These functions are declared additionally here if
- inlining is not possible. */
-
-#undef __USE_STRING_INLINES
-#define __USE_STRING_INLINES
-#define _FORCE_INLINES
-#define __STRING_INLINE /* empty */
-#define __NO_INLINE__
-
/* This is to avoid PLT entries for the x86 version. */
#define __memcpy_g __memcpy_g_internal
#define __strchr_g __strchr_g_internal
-
-#include <string.h>
-#undef index
-#undef rindex
-
-#undef __NO_INLINE__
-#include <bits/string.h>
-#include <bits/string2.h>
+#include <string/string-inlines.c>
void *
(__memcpy_c) (void *d, const void *s, size_t n)
--
1.9.1
next prev parent reply other threads:[~2016-03-31 14:01 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-03-31 14:01 [PATCH 0/4] Improve generic strspn/strcspn/strpbrk Adhemerval Zanella
2016-03-31 14:01 ` [PATCH 2/4] Improve generic strspn performance Adhemerval Zanella
2016-03-31 14:01 ` [PATCH 4/4] Remove powerpc64 strspn, strcspn, and strpbrk implementation Adhemerval Zanella
2016-03-31 14:01 ` [PATCH 3/4] Improve generic strpbrk performance Adhemerval Zanella
2016-03-31 14:01 ` Adhemerval Zanella [this message]
2016-03-31 14:49 ` [PATCH 1/4] Improve generic strcspn performance Wilco Dijkstra
2016-03-31 18:28 ` Adhemerval Zanella
2016-03-31 18:29 ` [PATCH 0/4] Improve generic strspn/strcspn/strpbrk Adhemerval Zanella
-- strict thread matches above, loose matches on Subject: below --
2016-03-28 15:20 Adhemerval Zanella
2016-03-28 15:20 ` [PATCH 1/4] Improve generic strcspn performance Adhemerval Zanella
2016-03-30 17:47 ` Richard Henderson
2016-03-30 18:01 ` Wilco Dijkstra
2016-03-30 18:24 ` Adhemerval Zanella
2016-03-30 18:46 ` Richard Henderson
2016-03-31 17:00 ` Richard Henderson
2016-04-01 20:44 ` Roland McGrath
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=1459432863-20749-2-git-send-email-adhemerval.zanella@linaro.org \
--to=adhemerval.zanella@linaro.org \
--cc=libc-alpha@sourceware.org \
--cc=wdijkstr@arm.com \
/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 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).