Message ID | AM5PR0802MB261099B09A5D7B2111854DB1839D0@AM5PR0802MB2610.eurprd08.prod.outlook.com |
---|---|
State | New |
Headers | show |
LGTM. On 15/12/2016 17:00, Wilco Dijkstra wrote: > This version renames a use of strsep that may cause a linknamespace > failure (https://sourceware.org/ml/libc-alpha/2016-12/msg00469.html). > > This patch cleans up the strsep implementation and improves performance. > Currently strsep calls strpbrk is is now a veneer to strcspn. Calling > strcspn directly is faster. Since it handles a delimiter string of size > 1 as a special case, this is not needed in strsep itself. Although this > means there is a slightly higher overhead if the delimiter size is 1, > all other cases are slightly faster. The overall performance gain is 5-10% > on AArch64. > > The string/bits/string2.h header contains optimizations for constant > delimiters of size 1-3. Benchmarking these showed similar performance for > size 1 (since in all cases strchr/strchrnul is used), while size 2 and 3 > can give up to 2x speedup for small input strings. However if these cases > are common it seems much better to add this optimization to strcspn. > So move these header optimizations to string-inlines.c. > > Improve the strsep benchmark so that it actually benchmarks something. > The current version contains a delimiter character at every position in the > input string, so there is very little work to do, and the extremely inefficent > simple_strsep implementation appears fastest in every case. The new version > has either no match in the input for the fail case and a match halfway in the > input for the success case. The input is then restored so that each iteration > does exactly the same amount of work. Reduce the number of testcases since > simple_strsep takes a lot of time now. > > Passes GLIBC tests, OK for commit? > > ChangeLog: > 2015-12-15 Wilco Dijkstra <wdijkstr@arm.com> > > * benchtests/bench-strsep.c (oldstrsep): Add old implementation. > (do_one_test) Restore original string so iteration works. > * string/string-inlines.c (do_test): Create better input strings. > (test_main) Reduce number of testruns. > * string/string-inlines.c (__old_strsep_1c): New function. > (__old_strsep_2c): Likewise. > (__old_strsep_3c): Likewise. > * string/strsep.c (__strsep): Remove case of small delim string. > Call strcspn directly rather than strpbrk. > * string/bits/string2.h (__strsep): Remove define. > (__strsep_1c): Remove. > (__strsep_2c): Remove. > (__strsep_3c): Remove. > (strsep): Remove. > * sysdeps/unix/sysv/linux/internal_statvfs.c > (__statvfs_getflags): Rename to __strsep. > > -- > diff --git a/benchtests/bench-strsep.c b/benchtests/bench-strsep.c > index 70dbb377563232a43895abc940d396f2c65237c6..3eda70f1d6b4bf295e2341e45ef2403b1e7d52a4 100644 > --- a/benchtests/bench-strsep.c > +++ b/benchtests/bench-strsep.c > @@ -49,10 +49,56 @@ simple_strsep (char **s1, char *s2) > return begin; > } > > +char * > +oldstrsep (char **stringp, const char *delim) > +{ > + char *begin, *end; > + > + begin = *stringp; > + if (begin == NULL) > + return NULL; > + > + /* A frequent case is when the delimiter string contains only one > + character. Here we don't need to call the expensive `strpbrk' > + function and instead work using `strchr'. */ > + if (delim[0] == '\0' || delim[1] == '\0') > + { > + char ch = delim[0]; > + > + if (ch == '\0') > + end = NULL; > + else > + { > + if (*begin == ch) > + end = begin; > + else if (*begin == '\0') > + end = NULL; > + else > + end = strchr (begin + 1, ch); > + } > + } > + else > + /* Find the end of the token. */ > + end = strpbrk (begin, delim); > + > + if (end) > + { > + /* Terminate the token and set *STRINGP past NUL character. */ > + *end++ = '\0'; > + *stringp = end; > + } > + else > + /* No more delimiters; this is the last token. */ > + *stringp = NULL; > + > + return begin; > +} > + > typedef char *(*proto_t) (const char **, const char *); > > IMPL (simple_strsep, 0) > IMPL (strsep, 1) > +IMPL (oldstrsep, 2) > > static void > do_one_test (impl_t * impl, const char *s1, const char *s2) > @@ -63,7 +109,10 @@ do_one_test (impl_t * impl, const char *s1, const char *s2) > TIMING_NOW (start); > for (i = 0; i < iters; ++i) > { > - CALL (impl, &s1, s2); > + const char *s1a = s1; > + CALL (impl, &s1a, s2); > + if (s1a != NULL) > + ((char*)s1a)[-1] = '1'; > } > TIMING_NOW (stop); > > @@ -76,7 +125,10 @@ static void > do_test (size_t align1, size_t align2, size_t len1, size_t len2, int fail) > { > char *s2 = (char *) (buf2 + align2); > - static const char d[] = "1234567890abcdef"; > + > + /* Search for a delimiter in a string containing mostly '0', so don't > + use '0' as a delimiter. */ > + static const char d[] = "123456789abcdefg"; > #define dl (sizeof (d) - 1) > char *ss2 = s2; > for (size_t l = len2; l > 0; l = l > dl ? l - dl : 0) > @@ -92,24 +144,9 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2, int fail) > FOR_EACH_IMPL (impl, 0) > { > char *s1 = (char *) (buf1 + align1); > - if (fail) > - { > - char *ss1 = s1; > - for (size_t l = len1; l > 0; l = l > dl ? l - dl : 0) > - { > - size_t t = l > dl ? dl : l; > - memcpy (ss1, d, t); > - ++ss1[len2 > 7 ? 7 : len2 - 1]; > - ss1 += t; > - } > - } > - else > - { > - memset (s1, '0', len1); > - memcpy (s1 + (len1 - len2) - 2, s2, len2); > - if ((len1 / len2) > 4) > - memcpy (s1 + (len1 - len2) - (3 * len2), s2, len2); > - } > + memset (s1, '0', len1); > + if (!fail) > + s1[len1 / 2] = '1'; > s1[len1] = '\0'; > do_one_test (impl, s1, s2); > } > @@ -127,7 +164,7 @@ test_main (void) > putchar ('\n'); > > for (size_t klen = 2; klen < 32; ++klen) > - for (size_t hlen = 2 * klen; hlen < 16 * klen; hlen += klen) > + for (size_t hlen = 4 * klen; hlen < 8 * klen; hlen += klen) > { > do_test (0, 0, hlen, klen, 0); > do_test (0, 0, hlen, klen, 1); > diff --git a/string/bits/string2.h b/string/bits/string2.h > index 5acdb7866e4e70a6c3aa050b0427b31aed8943ec..03af22cc27a33c81f36d56ddc52fce0a5ea81ece 100644 > --- a/string/bits/string2.h > +++ b/string/bits/string2.h > @@ -118,96 +118,6 @@ > #endif > > > -#if !defined _HAVE_STRING_ARCH_strsep || defined _FORCE_INLINES > -# ifndef _HAVE_STRING_ARCH_strsep > - > -extern char *__strsep_g (char **__stringp, const char *__delim); > -# define __strsep(s, reject) \ > - __extension__ \ > - ({ char __r0, __r1, __r2; \ > - (__builtin_constant_p (reject) && __string2_1bptr_p (reject) \ > - && (__r0 = ((const char *) (reject))[0], \ > - ((const char *) (reject))[0] != '\0') \ > - ? ((__r1 = ((const char *) (reject))[1], \ > - ((const char *) (reject))[1] == '\0') \ > - ? __strsep_1c (s, __r0) \ > - : ((__r2 = ((const char *) (reject))[2], __r2 == '\0') \ > - ? __strsep_2c (s, __r0, __r1) \ > - : (((const char *) (reject))[3] == '\0' \ > - ? __strsep_3c (s, __r0, __r1, __r2) \ > - : __strsep_g (s, reject)))) \ > - : __strsep_g (s, reject)); }) > -# endif > - > -__STRING_INLINE char *__strsep_1c (char **__s, char __reject); > -__STRING_INLINE char * > -__strsep_1c (char **__s, char __reject) > -{ > - char *__retval = *__s; > - if (__retval != NULL && (*__s = strchr (__retval, __reject)) != NULL) > - *(*__s)++ = '\0'; > - return __retval; > -} > - > -__STRING_INLINE char *__strsep_2c (char **__s, char __reject1, char __reject2); > -__STRING_INLINE char * > -__strsep_2c (char **__s, char __reject1, char __reject2) > -{ > - char *__retval = *__s; > - if (__retval != NULL) > - { > - char *__cp = __retval; > - while (1) > - { > - if (*__cp == '\0') > - { > - __cp = NULL; > - break; > - } > - if (*__cp == __reject1 || *__cp == __reject2) > - { > - *__cp++ = '\0'; > - break; > - } > - ++__cp; > - } > - *__s = __cp; > - } > - return __retval; > -} > - > -__STRING_INLINE char *__strsep_3c (char **__s, char __reject1, char __reject2, > - char __reject3); > -__STRING_INLINE char * > -__strsep_3c (char **__s, char __reject1, char __reject2, char __reject3) > -{ > - char *__retval = *__s; > - if (__retval != NULL) > - { > - char *__cp = __retval; > - while (1) > - { > - if (*__cp == '\0') > - { > - __cp = NULL; > - break; > - } > - if (*__cp == __reject1 || *__cp == __reject2 || *__cp == __reject3) > - { > - *__cp++ = '\0'; > - break; > - } > - ++__cp; > - } > - *__s = __cp; > - } > - return __retval; > -} > -# ifdef __USE_MISC > -# define strsep(s, reject) __strsep (s, reject) > -# endif > -#endif > - > /* We need the memory allocation functions for inline strdup(). > Referring to stdlib.h (even minimally) is not allowed > in any of the tight standards compliant modes. */ > diff --git a/string/string-inlines.c b/string/string-inlines.c > index f6f56c56f875a89fbc05dec61a7603c2a869607c..6d0c0c51b3027f99d26aace85523d7f337df8308 100644 > --- a/string/string-inlines.c > +++ b/string/string-inlines.c > @@ -62,6 +62,70 @@ __old_strtok_r_1c (char *__s, char __sep, char **__nextp) > return __result; > } > compat_symbol (libc, __old_strtok_r_1c, __strtok_r_1c, GLIBC_2_1_1); > + > +char * > +__old_strsep_1c (char **__s, char __reject) > +{ > + char *__retval = *__s; > + if (__retval != NULL && (*__s = strchr (__retval, __reject)) != NULL) > + *(*__s)++ = '\0'; > + return __retval; > +} > +compat_symbol (libc, __old_strsep_1c, __strsep_1c, GLIBC_2_1_1); > + > +char * > +__old_strsep_2c (char **__s, char __reject1, char __reject2) > +{ > + char *__retval = *__s; > + if (__retval != NULL) > + { > + char *__cp = __retval; > + while (1) > + { > + if (*__cp == '\0') > + { > + __cp = NULL; > + break; > + } > + if (*__cp == __reject1 || *__cp == __reject2) > + { > + *__cp++ = '\0'; > + break; > + } > + ++__cp; > + } > + *__s = __cp; > + } > + return __retval; > +} > +compat_symbol (libc, __old_strsep_2c, __strsep_2c, GLIBC_2_1_1); > + > +char * > +__old_strsep_3c (char **__s, char __reject1, char __reject2, char __reject3) > +{ > + char *__retval = *__s; > + if (__retval != NULL) > + { > + char *__cp = __retval; > + while (1) > + { > + if (*__cp == '\0') > + { > + __cp = NULL; > + break; > + } > + if (*__cp == __reject1 || *__cp == __reject2 || *__cp == __reject3) > + { > + *__cp++ = '\0'; > + break; > + } > + ++__cp; > + } > + *__s = __cp; > + } > + return __retval; > +} > +compat_symbol (libc, __old_strsep_3c, __strsep_3c, GLIBC_2_1_1); > #endif > > #if SHLIB_COMPAT (libc, GLIBC_2_1_1, GLIBC_2_24) > diff --git a/string/strsep.c b/string/strsep.c > index 10547740481bed8f7a065f76eccfe7b320c3c49c..68581c863980c1e86ae8559400ca0d1cec80d95e 100644 > --- a/string/strsep.c > +++ b/string/strsep.c > @@ -29,30 +29,10 @@ __strsep (char **stringp, const char *delim) > if (begin == NULL) > return NULL; > > - /* A frequent case is when the delimiter string contains only one > - character. Here we don't need to call the expensive `strpbrk' > - function and instead work using `strchr'. */ > - if (delim[0] == '\0' || delim[1] == '\0') > - { > - char ch = delim[0]; > - > - if (ch == '\0') > - end = NULL; > - else > - { > - if (*begin == ch) > - end = begin; > - else if (*begin == '\0') > - end = NULL; > - else > - end = strchr (begin + 1, ch); > - } > - } > - else > - /* Find the end of the token. */ > - end = strpbrk (begin, delim); > + /* Find the end of the token. */ > + end = begin + strcspn (begin, delim); > > - if (end) > + if (*end) > { > /* Terminate the token and set *STRINGP past NUL character. */ > *end++ = '\0'; > diff --git a/sysdeps/unix/sysv/linux/internal_statvfs.c b/sysdeps/unix/sysv/linux/internal_statvfs.c > index 012f93fe66bde9958d4d5d3432859a33e778f69b..ce649cd28d9edd7ed4eef55ee336da21115a944a 100644 > --- a/sysdeps/unix/sysv/linux/internal_statvfs.c > +++ b/sysdeps/unix/sysv/linux/internal_statvfs.c > @@ -168,7 +168,7 @@ __statvfs_getflags (const char *name, int fstype, int fd) > char *cp = mntbuf.mnt_opts; > char *opt; > > - while ((opt = strsep (&cp, ",")) != NULL) > + while ((opt = __strsep (&cp, ",")) != NULL) > if (strcmp (opt, "ro") == 0) > result |= ST_RDONLY; > else if (strcmp (opt, "nosuid") == 0) >
diff --git a/benchtests/bench-strsep.c b/benchtests/bench-strsep.c index 70dbb377563232a43895abc940d396f2c65237c6..3eda70f1d6b4bf295e2341e45ef2403b1e7d52a4 100644 --- a/benchtests/bench-strsep.c +++ b/benchtests/bench-strsep.c @@ -49,10 +49,56 @@ simple_strsep (char **s1, char *s2) return begin; } +char * +oldstrsep (char **stringp, const char *delim) +{ + char *begin, *end; + + begin = *stringp; + if (begin == NULL) + return NULL; + + /* A frequent case is when the delimiter string contains only one + character. Here we don't need to call the expensive `strpbrk' + function and instead work using `strchr'. */ + if (delim[0] == '\0' || delim[1] == '\0') + { + char ch = delim[0]; + + if (ch == '\0') + end = NULL; + else + { + if (*begin == ch) + end = begin; + else if (*begin == '\0') + end = NULL; + else + end = strchr (begin + 1, ch); + } + } + else + /* Find the end of the token. */ + end = strpbrk (begin, delim); + + if (end) + { + /* Terminate the token and set *STRINGP past NUL character. */ + *end++ = '\0'; + *stringp = end; + } + else + /* No more delimiters; this is the last token. */ + *stringp = NULL; + + return begin; +} + typedef char *(*proto_t) (const char **, const char *); IMPL (simple_strsep, 0) IMPL (strsep, 1) +IMPL (oldstrsep, 2) static void do_one_test (impl_t * impl, const char *s1, const char *s2) @@ -63,7 +109,10 @@ do_one_test (impl_t * impl, const char *s1, const char *s2) TIMING_NOW (start); for (i = 0; i < iters; ++i) { - CALL (impl, &s1, s2); + const char *s1a = s1; + CALL (impl, &s1a, s2); + if (s1a != NULL) + ((char*)s1a)[-1] = '1'; } TIMING_NOW (stop); @@ -76,7 +125,10 @@ static void do_test (size_t align1, size_t align2, size_t len1, size_t len2, int fail) { char *s2 = (char *) (buf2 + align2); - static const char d[] = "1234567890abcdef"; + + /* Search for a delimiter in a string containing mostly '0', so don't + use '0' as a delimiter. */ + static const char d[] = "123456789abcdefg"; #define dl (sizeof (d) - 1) char *ss2 = s2; for (size_t l = len2; l > 0; l = l > dl ? l - dl : 0) @@ -92,24 +144,9 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2, int fail) FOR_EACH_IMPL (impl, 0) { char *s1 = (char *) (buf1 + align1); - if (fail) - { - char *ss1 = s1; - for (size_t l = len1; l > 0; l = l > dl ? l - dl : 0) - { - size_t t = l > dl ? dl : l; - memcpy (ss1, d, t); - ++ss1[len2 > 7 ? 7 : len2 - 1]; - ss1 += t; - } - } - else - { - memset (s1, '0', len1); - memcpy (s1 + (len1 - len2) - 2, s2, len2); - if ((len1 / len2) > 4) - memcpy (s1 + (len1 - len2) - (3 * len2), s2, len2); - } + memset (s1, '0', len1); + if (!fail) + s1[len1 / 2] = '1'; s1[len1] = '\0'; do_one_test (impl, s1, s2); } @@ -127,7 +164,7 @@ test_main (void) putchar ('\n'); for (size_t klen = 2; klen < 32; ++klen) - for (size_t hlen = 2 * klen; hlen < 16 * klen; hlen += klen) + for (size_t hlen = 4 * klen; hlen < 8 * klen; hlen += klen) { do_test (0, 0, hlen, klen, 0); do_test (0, 0, hlen, klen, 1); diff --git a/string/bits/string2.h b/string/bits/string2.h index 5acdb7866e4e70a6c3aa050b0427b31aed8943ec..03af22cc27a33c81f36d56ddc52fce0a5ea81ece 100644 --- a/string/bits/string2.h +++ b/string/bits/string2.h @@ -118,96 +118,6 @@ #endif -#if !defined _HAVE_STRING_ARCH_strsep || defined _FORCE_INLINES -# ifndef _HAVE_STRING_ARCH_strsep - -extern char *__strsep_g (char **__stringp, const char *__delim); -# define __strsep(s, reject) \ - __extension__ \ - ({ char __r0, __r1, __r2; \ - (__builtin_constant_p (reject) && __string2_1bptr_p (reject) \ - && (__r0 = ((const char *) (reject))[0], \ - ((const char *) (reject))[0] != '\0') \ - ? ((__r1 = ((const char *) (reject))[1], \ - ((const char *) (reject))[1] == '\0') \ - ? __strsep_1c (s, __r0) \ - : ((__r2 = ((const char *) (reject))[2], __r2 == '\0') \ - ? __strsep_2c (s, __r0, __r1) \ - : (((const char *) (reject))[3] == '\0' \ - ? __strsep_3c (s, __r0, __r1, __r2) \ - : __strsep_g (s, reject)))) \ - : __strsep_g (s, reject)); }) -# endif - -__STRING_INLINE char *__strsep_1c (char **__s, char __reject); -__STRING_INLINE char * -__strsep_1c (char **__s, char __reject) -{ - char *__retval = *__s; - if (__retval != NULL && (*__s = strchr (__retval, __reject)) != NULL) - *(*__s)++ = '\0'; - return __retval; -} - -__STRING_INLINE char *__strsep_2c (char **__s, char __reject1, char __reject2); -__STRING_INLINE char * -__strsep_2c (char **__s, char __reject1, char __reject2) -{ - char *__retval = *__s; - if (__retval != NULL) - { - char *__cp = __retval; - while (1) - { - if (*__cp == '\0') - { - __cp = NULL; - break; - } - if (*__cp == __reject1 || *__cp == __reject2) - { - *__cp++ = '\0'; - break; - } - ++__cp; - } - *__s = __cp; - } - return __retval; -} - -__STRING_INLINE char *__strsep_3c (char **__s, char __reject1, char __reject2, - char __reject3); -__STRING_INLINE char * -__strsep_3c (char **__s, char __reject1, char __reject2, char __reject3) -{ - char *__retval = *__s; - if (__retval != NULL) - { - char *__cp = __retval; - while (1) - { - if (*__cp == '\0') - { - __cp = NULL; - break; - } - if (*__cp == __reject1 || *__cp == __reject2 || *__cp == __reject3) - { - *__cp++ = '\0'; - break; - } - ++__cp; - } - *__s = __cp; - } - return __retval; -} -# ifdef __USE_MISC -# define strsep(s, reject) __strsep (s, reject) -# endif -#endif - /* We need the memory allocation functions for inline strdup(). Referring to stdlib.h (even minimally) is not allowed in any of the tight standards compliant modes. */ diff --git a/string/string-inlines.c b/string/string-inlines.c index f6f56c56f875a89fbc05dec61a7603c2a869607c..6d0c0c51b3027f99d26aace85523d7f337df8308 100644 --- a/string/string-inlines.c +++ b/string/string-inlines.c @@ -62,6 +62,70 @@ __old_strtok_r_1c (char *__s, char __sep, char **__nextp) return __result; } compat_symbol (libc, __old_strtok_r_1c, __strtok_r_1c, GLIBC_2_1_1); + +char * +__old_strsep_1c (char **__s, char __reject) +{ + char *__retval = *__s; + if (__retval != NULL && (*__s = strchr (__retval, __reject)) != NULL) + *(*__s)++ = '\0'; + return __retval; +} +compat_symbol (libc, __old_strsep_1c, __strsep_1c, GLIBC_2_1_1); + +char * +__old_strsep_2c (char **__s, char __reject1, char __reject2) +{ + char *__retval = *__s; + if (__retval != NULL) + { + char *__cp = __retval; + while (1) + { + if (*__cp == '\0') + { + __cp = NULL; + break; + } + if (*__cp == __reject1 || *__cp == __reject2) + { + *__cp++ = '\0'; + break; + } + ++__cp; + } + *__s = __cp; + } + return __retval; +} +compat_symbol (libc, __old_strsep_2c, __strsep_2c, GLIBC_2_1_1); + +char * +__old_strsep_3c (char **__s, char __reject1, char __reject2, char __reject3) +{ + char *__retval = *__s; + if (__retval != NULL) + { + char *__cp = __retval; + while (1) + { + if (*__cp == '\0') + { + __cp = NULL; + break; + } + if (*__cp == __reject1 || *__cp == __reject2 || *__cp == __reject3) + { + *__cp++ = '\0'; + break; + } + ++__cp; + } + *__s = __cp; + } + return __retval; +} +compat_symbol (libc, __old_strsep_3c, __strsep_3c, GLIBC_2_1_1); #endif #if SHLIB_COMPAT (libc, GLIBC_2_1_1, GLIBC_2_24) diff --git a/string/strsep.c b/string/strsep.c index 10547740481bed8f7a065f76eccfe7b320c3c49c..68581c863980c1e86ae8559400ca0d1cec80d95e 100644 --- a/string/strsep.c +++ b/string/strsep.c @@ -29,30 +29,10 @@ __strsep (char **stringp, const char *delim) if (begin == NULL) return NULL; - /* A frequent case is when the delimiter string contains only one - character. Here we don't need to call the expensive `strpbrk' - function and instead work using `strchr'. */ - if (delim[0] == '\0' || delim[1] == '\0') - { - char ch = delim[0]; - - if (ch == '\0') - end = NULL; - else - { - if (*begin == ch) - end = begin; - else if (*begin == '\0') - end = NULL; - else - end = strchr (begin + 1, ch); - } - } - else - /* Find the end of the token. */ - end = strpbrk (begin, delim); + /* Find the end of the token. */ + end = begin + strcspn (begin, delim); - if (end) + if (*end) { /* Terminate the token and set *STRINGP past NUL character. */ *end++ = '\0'; diff --git a/sysdeps/unix/sysv/linux/internal_statvfs.c b/sysdeps/unix/sysv/linux/internal_statvfs.c index 012f93fe66bde9958d4d5d3432859a33e778f69b..ce649cd28d9edd7ed4eef55ee336da21115a944a 100644 --- a/sysdeps/unix/sysv/linux/internal_statvfs.c +++ b/sysdeps/unix/sysv/linux/internal_statvfs.c @@ -168,7 +168,7 @@ __statvfs_getflags (const char *name, int fstype, int fd) char *cp = mntbuf.mnt_opts; char *opt; - while ((opt = strsep (&cp, ",")) != NULL) + while ((opt = __strsep (&cp, ",")) != NULL) if (strcmp (opt, "ro") == 0) result |= ST_RDONLY; else if (strcmp (opt, "nosuid") == 0)