* [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() @ 2018-07-22 17:37 Zhaoxiu Zeng 2018-07-22 18:37 ` Greg Kroah-Hartman 0 siblings, 1 reply; 8+ messages in thread From: Zhaoxiu Zeng @ 2018-07-22 17:37 UTC (permalink / raw) To: Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, Greg Kroah-Hartman Cc: linux-kernel, Zhaoxiu Zeng From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com> The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. For the Sunday algorithm, to see http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com> --- lib/string.c | 92 +++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 81 insertions(+), 11 deletions(-) diff --git a/lib/string.c b/lib/string.c index 2c0900a5d51a..ed4ab9ee3373 100644 --- a/lib/string.c +++ b/lib/string.c @@ -898,19 +898,51 @@ EXPORT_SYMBOL(memscan); */ char *strstr(const char *s1, const char *s2) { - size_t l1, l2; + size_t l2; + const char *pchk = s1; +#ifdef __HAVE_ARCH_STRLEN l2 = strlen(s2); +#else + for (l2 = 0; s2[l2] != 0; l2++) + /* nothing */; +#endif if (!l2) return (char *)s1; - l1 = strlen(s1); - while (l1 >= l2) { - l1--; - if (!memcmp(s1, s2, l2)) + + /* + * Sunday matching + */ + while (1) { + size_t i; + char k; + + /* compare */ + for (i = 0; i < l2; i++) { + if (s1[i] != s2[i]) + break; + } + if (i >= l2) return (char *)s1; - s1++; + + /* if s1 terminate early? */ + if (pchk < s1 + i) + pchk = s1 + i; + do { + k = *pchk; + if (k == 0) + return NULL; + } while (pchk++ != s1 + l2); + + /* find the k's last presence in s2 (k = s1[l2]) */ + for (i = l2; --i != (size_t)-1; ) { + if (k == s2[i]) + break; + } + + /* shift */ + s1 += l2 - i; } - return NULL; } EXPORT_SYMBOL(strstr); #endif @@ -925,16 +957,54 @@ EXPORT_SYMBOL(strstr); char *strnstr(const char *s1, const char *s2, size_t len) { size_t l2; + const char *pchk = s1; +#ifdef __HAVE_ARCH_STRLEN l2 = strlen(s2); +#else + for (l2 = 0; s2[l2] != 0; l2++) + /* nothing */; +#endif if (!l2) return (char *)s1; + + /* + * Sunday matching + */ while (len >= l2) { - len--; - if (!memcmp(s1, s2, l2)) - return (char *)s1; - s1++; + size_t i; + char k; + + /* compare */ + for (i = 0; i < l2; i++) { + if (s1[i] != s2[i]) + break; + } + if (i >= l2) + return (char *)s1; + if (len == l2) + break; + + /* if s1 terminate early? */ + if (pchk < s1 + i) + pchk = s1 + i; + do { + k = *pchk; + if (k == 0) + return NULL; + } while (pchk++ != s1 + l2); + + /* find the k's last presence in s2 (k = s1[l2]) */ + for (i = l2; --i != (size_t)-1; ) { + if (k == s2[i]) + break; + } + + /* shift */ + s1 += l2 - i; + len -= l2 - i; } + return NULL; } EXPORT_SYMBOL(strnstr); -- 2.17.1 ^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() 2018-07-22 17:37 [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() Zhaoxiu Zeng @ 2018-07-22 18:37 ` Greg Kroah-Hartman 2018-07-26 17:17 ` Zhaoxiu Zeng 0 siblings, 1 reply; 8+ messages in thread From: Greg Kroah-Hartman @ 2018-07-22 18:37 UTC (permalink / raw) To: Zhaoxiu Zeng Cc: Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, linux-kernel, Zhaoxiu Zeng On Mon, Jul 23, 2018 at 01:37:15AM +0800, Zhaoxiu Zeng wrote: > From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com> > > The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. > For the Sunday algorithm, to see > http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm So you say, but what does this really buy us? Why make this change? How was it tested? What is the downside of not taking this? thanks, greg k-h ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() 2018-07-22 18:37 ` Greg Kroah-Hartman @ 2018-07-26 17:17 ` Zhaoxiu Zeng 2018-07-27 5:48 ` Zhaoxiu Zeng 0 siblings, 1 reply; 8+ messages in thread From: Zhaoxiu Zeng @ 2018-07-26 17:17 UTC (permalink / raw) To: Greg Kroah-Hartman Cc: Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, linux-kernel, Zhaoxiu Zeng 在 2018/7/23 2:37, Greg Kroah-Hartman 写道: > On Mon, Jul 23, 2018 at 01:37:15AM +0800, Zhaoxiu Zeng wrote: >> From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com> >> >> The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. >> For the Sunday algorithm, to see >> http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm > > So you say, but what does this really buy us? Why make this change? > How was it tested? What is the downside of not taking this? > > thanks, > > greg k-h > I use the following program to test on fc28. Compile with O2, the new version is almost 2X faster than the original. The code size of the original is 0x80, the newer is 0xB0. #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <time.h> #include <unistd.h> /** * strstr - Find the first substring in a %NUL terminated string * @s1: The string to be searched * @s2: The string to search for */ char *strstr1(const char *s1, const char *s2) { size_t l1, l2; l2 = strlen(s2); if (!l2) return (char *)s1; l1 = strlen(s1); while (l1 >= l2) { l1--; if (!memcmp(s1, s2, l2)) return (char *)s1; s1++; } return NULL; } char *strstr2(const char *s1, const char *s2) { size_t l2; const char *pchk = s1; #if 1//def __HAVE_ARCH_STRLEN l2 = strlen(s2); #else for (l2 = 0; s2[l2] != 0; l2++) /* nothing */; #endif if (!l2) return (char *)s1; /* * Sunday matching */ while (1) { size_t i; char k; /* compare */ for (i = 0; i < l2; i++) { if (s1[i] != s2[i]) break; } if (i >= l2) return (char *)s1; /* if s1 terminate early? */ if (pchk < s1 + i) pchk = s1 + i; do { k = *pchk; if (k == 0) return NULL; } while (pchk++ != s1 + l2); /* find the k's last presence in s2 (k = s1[l2]) */ for (i = l2; --i != (size_t)-1; ) { if (k == s2[i]) break; } /* shift */ s1 += l2 - i; } } #ifdef __i386__ # define RDTSC_CLOBBER "%eax", "%ebx", "%ecx", "%edx" #elif __x86_64__ # define RDTSC_CLOBBER "%rax", "%rbx", "%rcx", "%rdx" #else # error unknown platform #endif #define RDTSC_START(cycles) \ do { \ register unsigned cyc_high, cyc_low; \ asm volatile("CPUID\n\t" \ "RDTSC\n\t" \ "mov %%edx, %0\n\t" \ "mov %%eax, %1\n\t" \ : "=r" (cyc_high), "=r" (cyc_low) \ :: RDTSC_CLOBBER); \ (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ } while (0) #define RDTSC_STOP(cycles) \ do { \ register unsigned cyc_high, cyc_low; \ asm volatile("RDTSCP\n\t" \ "mov %%edx, %0\n\t" \ "mov %%eax, %1\n\t" \ "CPUID\n\t" \ : "=r" (cyc_high), "=r" (cyc_low) \ :: RDTSC_CLOBBER); \ (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ } while (0) typedef unsigned long long TIME_T; #define start_time(start) RDTSC_START(start) #define stop_time(stop) RDTSC_STOP(stop) #define diff_time(start, stop) (stop - start) #define MAX_HAYSTACK_LENGTH 64 #define MAX_NEEDLE_LENGTH 16 #define TEST_LOOPS 1000 char haystack[MAX_HAYSTACK_LENGTH + 1]; char needle[MAX_NEEDLE_LENGTH + 1]; int main(int argc, char **argv) { size_t i, j, n; void *p1, *p2; srand(time(0)); for (i = 0; i < MAX_HAYSTACK_LENGTH; ) { haystack[i] = rand(); if (haystack[i] != 0) i++; } haystack[i] = 0; for (i = 0; i < MAX_HAYSTACK_LENGTH; i++) { TIME_T start, stop; unsigned long long elapsed1, elapsed2; j = rand() % MAX_NEEDLE_LENGTH; if (i <= MAX_HAYSTACK_LENGTH - (MAX_NEEDLE_LENGTH - j)) n = i; else n = MAX_HAYSTACK_LENGTH - (MAX_NEEDLE_LENGTH - j); memcpy(needle + j, haystack + n, MAX_NEEDLE_LENGTH - j); needle[MAX_NEEDLE_LENGTH] = 0; elapsed1 = ~0UL; for (n = 0; n < TEST_LOOPS; n++) { start_time(start); asm volatile("":::"memory"); p1 = strstr1(haystack, needle + j); asm volatile("":::"memory"); stop_time(stop); if (elapsed1 > diff_time(start, stop)) elapsed1 = diff_time(start, stop); } elapsed2 = ~0UL; for (n = 0; n < TEST_LOOPS; n++) { start_time(start); asm volatile("":::"memory"); p2 = strstr2(haystack, needle + j); asm volatile("":::"memory"); stop_time(stop); if (elapsed2 > diff_time(start, stop)) elapsed2 = diff_time(start, stop); } if (p1 != p2) fprintf(stderr, "Error: %p != %p\n", p1, p2); else fprintf(stdout, "%3d, %3d:\t%lld,\t%lld\n", i, j, elapsed1, elapsed2); } return 0; } The test result: [zzx@fedora strstr]$ ./test 0, 3: 68, 68 1, 13: 74, 66 2, 2: 88, 94 3, 5: 96, 88 4, 8: 108, 80 5, 13: 110, 76 6, 12: 132, 82 7, 9: 142, 82 8, 11: 152, 88 9, 13: 146, 90 10, 14: 154, 94 11, 15: 132, 104 12, 1: 196, 114 13, 8: 206, 108 14, 14: 186, 110 15, 13: 194, 112 16, 0: 260, 124 17, 10: 258, 124 18, 15: 208, 136 19, 11: 276, 136 20, 13: 256, 128 21, 12: 292, 144 22, 11: 300, 142 23, 13: 278, 144 24, 7: 334, 152 25, 1: 346, 166 26, 6: 368, 168 27, 15: 278, 182 28, 1: 374, 168 29, 3: 382, 188 30, 8: 398, 172 31, 4: 402, 188 32, 0: 430, 180 33, 10: 398, 184 34, 10: 410, 192 35, 8: 434, 180 36, 7: 444, 198 37, 6: 454, 204 38, 1: 464, 220 39, 2: 472, 206 40, 4: 482, 210 41, 15: 388, 262 42, 2: 502, 210 43, 5: 510, 220 44, 8: 520, 214 45, 0: 564, 236 46, 3: 550, 242 47, 8: 552, 262 48, 10: 528, 270 49, 2: 572, 256 50, 3: 586, 246 51, 7: 590, 278 52, 14: 506, 308 53, 14: 514, 298 54, 4: 602, 240 55, 5: 626, 284 56, 15: 506, 316 57, 10: 606, 326 58, 4: 606, 240 59, 0: 596, 240 60, 13: 570, 316 61, 13: 576, 328 62, 5: 618, 284 63, 13: 576, 328 Thanks! ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() 2018-07-26 17:17 ` Zhaoxiu Zeng @ 2018-07-27 5:48 ` Zhaoxiu Zeng 2018-07-27 10:39 ` Andy Shevchenko 0 siblings, 1 reply; 8+ messages in thread From: Zhaoxiu Zeng @ 2018-07-27 5:48 UTC (permalink / raw) To: Greg Kroah-Hartman Cc: Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, linux-kernel, Zhaoxiu Zeng 在 2018/7/27 1:17, Zhaoxiu Zeng 写道: > 在 2018/7/23 2:37, Greg Kroah-Hartman 写道: >> On Mon, Jul 23, 2018 at 01:37:15AM +0800, Zhaoxiu Zeng wrote: >>> From: Zhaoxiu Zeng <zhaoxiu.zeng@gmail.com> >>> >>> The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. >>> For the Sunday algorithm, to see >>> http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm >> >> So you say, but what does this really buy us? Why make this change? >> How was it tested? What is the downside of not taking this? >> >> thanks, >> >> greg k-h >> > > I use the following program to test on fc28. > Compile with O2, the new version is almost 2X faster than the original. > The code size of the original is 0x80, the newer is 0xB0. > > > #include <stdio.h> > #include <stdlib.h> > #include <stdint.h> > #include <string.h> > #include <time.h> > #include <unistd.h> > > /** > * strstr - Find the first substring in a %NUL terminated string > * @s1: The string to be searched > * @s2: The string to search for > */ > char *strstr1(const char *s1, const char *s2) > { > size_t l1, l2; > > l2 = strlen(s2); > if (!l2) > return (char *)s1; > l1 = strlen(s1); > while (l1 >= l2) { > l1--; > if (!memcmp(s1, s2, l2)) > return (char *)s1; > s1++; > } > return NULL; > } > > char *strstr2(const char *s1, const char *s2) > { > size_t l2; > const char *pchk = s1; > > #if 1//def __HAVE_ARCH_STRLEN > l2 = strlen(s2); > #else > for (l2 = 0; s2[l2] != 0; l2++) > /* nothing */; > #endif > if (!l2) > return (char *)s1; > > /* > * Sunday matching > */ > while (1) { > size_t i; > char k; > > /* compare */ > for (i = 0; i < l2; i++) { > if (s1[i] != s2[i]) > break; > } > if (i >= l2) > return (char *)s1; > > /* if s1 terminate early? */ > if (pchk < s1 + i) > pchk = s1 + i; > do { > k = *pchk; > if (k == 0) > return NULL; > } while (pchk++ != s1 + l2); > > /* find the k's last presence in s2 (k = s1[l2]) */ > for (i = l2; --i != (size_t)-1; ) { > if (k == s2[i]) > break; > } > > /* shift */ > s1 += l2 - i; > } > } > > #ifdef __i386__ > # define RDTSC_CLOBBER "%eax", "%ebx", "%ecx", "%edx" > #elif __x86_64__ > # define RDTSC_CLOBBER "%rax", "%rbx", "%rcx", "%rdx" > #else > # error unknown platform > #endif > > #define RDTSC_START(cycles) \ > do { \ > register unsigned cyc_high, cyc_low; \ > asm volatile("CPUID\n\t" \ > "RDTSC\n\t" \ > "mov %%edx, %0\n\t" \ > "mov %%eax, %1\n\t" \ > : "=r" (cyc_high), "=r" (cyc_low) \ > :: RDTSC_CLOBBER); \ > (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ > } while (0) > > #define RDTSC_STOP(cycles) \ > do { \ > register unsigned cyc_high, cyc_low; \ > asm volatile("RDTSCP\n\t" \ > "mov %%edx, %0\n\t" \ > "mov %%eax, %1\n\t" \ > "CPUID\n\t" \ > : "=r" (cyc_high), "=r" (cyc_low) \ > :: RDTSC_CLOBBER); \ > (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ > } while (0) > > typedef unsigned long long TIME_T; > #define start_time(start) RDTSC_START(start) > #define stop_time(stop) RDTSC_STOP(stop) > #define diff_time(start, stop) (stop - start) > > #define MAX_HAYSTACK_LENGTH 64 > #define MAX_NEEDLE_LENGTH 16 > #define TEST_LOOPS 1000 > > char haystack[MAX_HAYSTACK_LENGTH + 1]; > char needle[MAX_NEEDLE_LENGTH + 1]; > > int main(int argc, char **argv) > { > size_t i, j, n; > void *p1, *p2; > > srand(time(0)); > > for (i = 0; i < MAX_HAYSTACK_LENGTH; ) { > haystack[i] = rand(); > if (haystack[i] != 0) > i++; > } > haystack[i] = 0; > > for (i = 0; i < MAX_HAYSTACK_LENGTH; i++) { > TIME_T start, stop; > unsigned long long elapsed1, elapsed2; > > j = rand() % MAX_NEEDLE_LENGTH; > if (i <= MAX_HAYSTACK_LENGTH - (MAX_NEEDLE_LENGTH - j)) > n = i; > else > n = MAX_HAYSTACK_LENGTH - (MAX_NEEDLE_LENGTH - j); > memcpy(needle + j, haystack + n, MAX_NEEDLE_LENGTH - j); > needle[MAX_NEEDLE_LENGTH] = 0; > > elapsed1 = ~0UL; > for (n = 0; n < TEST_LOOPS; n++) { > start_time(start); > asm volatile("":::"memory"); > p1 = strstr1(haystack, needle + j); > asm volatile("":::"memory"); > stop_time(stop); > > if (elapsed1 > diff_time(start, stop)) > elapsed1 = diff_time(start, stop); > } > > elapsed2 = ~0UL; > for (n = 0; n < TEST_LOOPS; n++) { > start_time(start); > asm volatile("":::"memory"); > p2 = strstr2(haystack, needle + j); > asm volatile("":::"memory"); > stop_time(stop); > > if (elapsed2 > diff_time(start, stop)) > elapsed2 = diff_time(start, stop); > } > > if (p1 != p2) > fprintf(stderr, "Error: %p != %p\n", p1, p2); > else > fprintf(stdout, "%3d, %3d:\t%lld,\t%lld\n", i, j, elapsed1, elapsed2); > } > > return 0; > } > > The test result: > [zzx@fedora strstr]$ ./test > 0, 3: 68, 68 > 1, 13: 74, 66 > 2, 2: 88, 94 > 3, 5: 96, 88 > 4, 8: 108, 80 > 5, 13: 110, 76 > 6, 12: 132, 82 > 7, 9: 142, 82 > 8, 11: 152, 88 > 9, 13: 146, 90 > 10, 14: 154, 94 > 11, 15: 132, 104 > 12, 1: 196, 114 > 13, 8: 206, 108 > 14, 14: 186, 110 > 15, 13: 194, 112 > 16, 0: 260, 124 > 17, 10: 258, 124 > 18, 15: 208, 136 > 19, 11: 276, 136 > 20, 13: 256, 128 > 21, 12: 292, 144 > 22, 11: 300, 142 > 23, 13: 278, 144 > 24, 7: 334, 152 > 25, 1: 346, 166 > 26, 6: 368, 168 > 27, 15: 278, 182 > 28, 1: 374, 168 > 29, 3: 382, 188 > 30, 8: 398, 172 > 31, 4: 402, 188 > 32, 0: 430, 180 > 33, 10: 398, 184 > 34, 10: 410, 192 > 35, 8: 434, 180 > 36, 7: 444, 198 > 37, 6: 454, 204 > 38, 1: 464, 220 > 39, 2: 472, 206 > 40, 4: 482, 210 > 41, 15: 388, 262 > 42, 2: 502, 210 > 43, 5: 510, 220 > 44, 8: 520, 214 > 45, 0: 564, 236 > 46, 3: 550, 242 > 47, 8: 552, 262 > 48, 10: 528, 270 > 49, 2: 572, 256 > 50, 3: 586, 246 > 51, 7: 590, 278 > 52, 14: 506, 308 > 53, 14: 514, 298 > 54, 4: 602, 240 > 55, 5: 626, 284 > 56, 15: 506, 316 > 57, 10: 606, 326 > 58, 4: 606, 240 > 59, 0: 596, 240 > 60, 13: 570, 316 > 61, 13: 576, 328 > 62, 5: 618, 284 > 63, 13: 576, 328 > > Thanks! > The original strnstr might has a bug too! For example, assume s1 is "123\0abc...." and s2 is "abc\0", call strnstr(s1, s2, 7) will return &s1[4], but the correct result is NULL. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() 2018-07-27 5:48 ` Zhaoxiu Zeng @ 2018-07-27 10:39 ` Andy Shevchenko 2018-07-28 14:02 ` Zhaoxiu Zeng 0 siblings, 1 reply; 8+ messages in thread From: Andy Shevchenko @ 2018-07-27 10:39 UTC (permalink / raw) To: Zhaoxiu Zeng Cc: Greg Kroah-Hartman, Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, Linux Kernel Mailing List, Zhaoxiu Zeng On Fri, Jul 27, 2018 at 8:48 AM, Zhaoxiu Zeng <zengzhaoxiu@163.com> wrote: > 在 2018/7/27 1:17, Zhaoxiu Zeng 写道: >> 在 2018/7/23 2:37, Greg Kroah-Hartman 写道: >>> On Mon, Jul 23, 2018 at 01:37:15AM +0800, Zhaoxiu Zeng wrote: >>>> The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. >>>> For the Sunday algorithm, to see >>>> http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm >>> >>> So you say, but what does this really buy us? Why make this change? >>> How was it tested? What is the downside of not taking this? >> I use the following program to test on fc28. >> Compile with O2, the new version is almost 2X faster than the original. >> The code size of the original is 0x80, the newer is 0xB0. So, output of bloat-o-meter would be good to have in commit message. >> The test result: Compact performance statistics as well. >> Thanks! > The original strnstr might has a bug too! > For example, assume s1 is "123\0abc...." and s2 is "abc\0", > call strnstr(s1, s2, 7) will return &s1[4], but the correct result is NULL. If there is a bug, send another patch to fix the bug first. -- With Best Regards, Andy Shevchenko ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() 2018-07-27 10:39 ` Andy Shevchenko @ 2018-07-28 14:02 ` Zhaoxiu Zeng 2018-07-28 14:38 ` Greg Kroah-Hartman 0 siblings, 1 reply; 8+ messages in thread From: Zhaoxiu Zeng @ 2018-07-28 14:02 UTC (permalink / raw) To: Andy Shevchenko Cc: Greg Kroah-Hartman, Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, Linux Kernel Mailing List, Zhaoxiu Zeng 在 2018/7/27 18:39, Andy Shevchenko 写道: > On Fri, Jul 27, 2018 at 8:48 AM, Zhaoxiu Zeng <zengzhaoxiu@163.com> wrote: >> 在 2018/7/27 1:17, Zhaoxiu Zeng 写道: >>> 在 2018/7/23 2:37, Greg Kroah-Hartman 写道: >>>> On Mon, Jul 23, 2018 at 01:37:15AM +0800, Zhaoxiu Zeng wrote: > >>>>> The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. >>>>> For the Sunday algorithm, to see >>>>> http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm >>>> >>>> So you say, but what does this really buy us? Why make this change? >>>> How was it tested? What is the downside of not taking this? > >>> I use the following program to test on fc28. >>> Compile with O2, the new version is almost 2X faster than the original. > >>> The code size of the original is 0x80, the newer is 0xB0. > > So, output of bloat-o-meter would be good to have in commit message. > >>> The test result: > > Compact performance statistics as well. > >>> Thanks! > >> The original strnstr might has a bug too! >> For example, assume s1 is "123\0abc...." and s2 is "abc\0", >> call strnstr(s1, s2, 7) will return &s1[4], but the correct result is NULL. > > If there is a bug, send another patch to fix the bug first. > The bug could be fixed by this patch. ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() 2018-07-28 14:02 ` Zhaoxiu Zeng @ 2018-07-28 14:38 ` Greg Kroah-Hartman 2018-07-29 7:37 ` Zhaoxiu Zeng 0 siblings, 1 reply; 8+ messages in thread From: Greg Kroah-Hartman @ 2018-07-28 14:38 UTC (permalink / raw) To: Zhaoxiu Zeng Cc: Andy Shevchenko, Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, Linux Kernel Mailing List, Zhaoxiu Zeng On Sat, Jul 28, 2018 at 10:02:51PM +0800, Zhaoxiu Zeng wrote: > 在 2018/7/27 18:39, Andy Shevchenko 写道: > > On Fri, Jul 27, 2018 at 8:48 AM, Zhaoxiu Zeng <zengzhaoxiu@163.com> wrote: > >> 在 2018/7/27 1:17, Zhaoxiu Zeng 写道: > >>> 在 2018/7/23 2:37, Greg Kroah-Hartman 写道: > >>>> On Mon, Jul 23, 2018 at 01:37:15AM +0800, Zhaoxiu Zeng wrote: > > > >>>>> The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. > >>>>> For the Sunday algorithm, to see > >>>>> http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm > >>>> > >>>> So you say, but what does this really buy us? Why make this change? > >>>> How was it tested? What is the downside of not taking this? > > > >>> I use the following program to test on fc28. > >>> Compile with O2, the new version is almost 2X faster than the original. > > > >>> The code size of the original is 0x80, the newer is 0xB0. > > > > So, output of bloat-o-meter would be good to have in commit message. > > > >>> The test result: > > > > Compact performance statistics as well. > > > >>> Thanks! > > > >> The original strnstr might has a bug too! > >> For example, assume s1 is "123\0abc...." and s2 is "abc\0", > >> call strnstr(s1, s2, 7) will return &s1[4], but the correct result is NULL. > > > > If there is a bug, send another patch to fix the bug first. > > > > The bug could be fixed by this patch. Given that there doesn't seem to be a good reason to take your patch yet, that might be hard :) You need to convince us that the patch is a valid thing to accept, by writing a correct changelog and showing proof of its correctness as this is modifying a core function in the kernel. thanks, greg k-h ^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() 2018-07-28 14:38 ` Greg Kroah-Hartman @ 2018-07-29 7:37 ` Zhaoxiu Zeng 0 siblings, 0 replies; 8+ messages in thread From: Zhaoxiu Zeng @ 2018-07-29 7:37 UTC (permalink / raw) To: Greg Kroah-Hartman Cc: Andy Shevchenko, Andrew Morton, Matthew Wilcox, Dan Carpenter, Geert Uytterhoeven, Thomas Gleixner, Andrey Ryabinin, Linux Kernel Mailing List, Zhaoxiu Zeng 在 2018/7/28 22:38, Greg Kroah-Hartman 写道: > On Sat, Jul 28, 2018 at 10:02:51PM +0800, Zhaoxiu Zeng wrote: >> 在 2018/7/27 18:39, Andy Shevchenko 写道: >>> On Fri, Jul 27, 2018 at 8:48 AM, Zhaoxiu Zeng <zengzhaoxiu@163.com> wrote: >>>> 在 2018/7/27 1:17, Zhaoxiu Zeng 写道: >>>>> 在 2018/7/23 2:37, Greg Kroah-Hartman 写道: >>>>>> On Mon, Jul 23, 2018 at 01:37:15AM +0800, Zhaoxiu Zeng wrote: >>> >>>>>>> The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. >>>>>>> For the Sunday algorithm, to see >>>>>>> http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm >>>>>> >>>>>> So you say, but what does this really buy us? Why make this change? >>>>>> How was it tested? What is the downside of not taking this? >>> >>>>> I use the following program to test on fc28. >>>>> Compile with O2, the new version is almost 2X faster than the original. >>> >>>>> The code size of the original is 0x80, the newer is 0xB0. >>> >>> So, output of bloat-o-meter would be good to have in commit message. >>> >>>>> The test result: >>> >>> Compact performance statistics as well. >>> >>>>> Thanks! >>> >>>> The original strnstr might has a bug too! >>>> For example, assume s1 is "123\0abc...." and s2 is "abc\0", >>>> call strnstr(s1, s2, 7) will return &s1[4], but the correct result is NULL. >>> >>> If there is a bug, send another patch to fix the bug first. >>> >> >> The bug could be fixed by this patch. > > Given that there doesn't seem to be a good reason to take your patch > yet, that might be hard :) > > You need to convince us that the patch is a valid thing to accept, by > writing a correct changelog and showing proof of its correctness as this > is modifying a core function in the kernel. > > thanks, > > greg k-h > Thanks for responses! I wrote a new changelog as described below. If it's ok, I will commit a new patch. The details are as follow: The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast. For the Sunday algorithm, to see http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm The new strstr implementation steps: 1) Gets the pattern length, and is denoted as l2. 2) Compares the first l2 bytes of the text with the pattern. If the comparison has matched, returns the pointer to starting of the text. Else, gets the index of the symbol which causes a mismatch, and is denoted as i. 3) Scans the text from index i to l2, to test whether the text is terminated. If the text is terminated early, returns NULL. Else, gets the symbol at index l2, and is denoted K. 4) Finds the index of K's last presence in the pattern, and is denoted as j. If there is no occurence of K in the pattern, j is -1. 5) Shifts the text window "l2 - j" bytes, and repeats step 2. The original strstr scans the text two times. The 1st time gets the text length, the 2nd time does the matches. The new strstr scans the text only one time. The original strnstr has a bug. If the text length is smaller than the argument "len", it maybe returns a wrong result. The bug could be fixed by this patch too. I have tested using the following program on fc28.x86_64. When compile with O2, the new version is almost 2X faster than the original, the code size of the original strstr is 0x80 and the newer is 0xB0. #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <time.h> #include <unistd.h> /** * strstr - Find the first substring in a %NUL terminated string * @s1: The string to be searched * @s2: The string to search for */ char *strstr1(const char *s1, const char *s2) { size_t l1, l2; l2 = strlen(s2); if (!l2) return (char *)s1; l1 = strlen(s1); while (l1 >= l2) { l1--; if (!memcmp(s1, s2, l2)) return (char *)s1; s1++; } return NULL; } char *strstr2(const char *s1, const char *s2) { size_t l2; const char *pchk = s1; #if 1//def __HAVE_ARCH_STRLEN l2 = strlen(s2); #else for (l2 = 0; s2[l2] != 0; l2++) /* nothing */; #endif if (!l2) return (char *)s1; /* * Sunday matching */ while (1) { size_t i; char k; /* compare */ for (i = 0; i < l2; i++) { if (s1[i] != s2[i]) break; } if (i >= l2) return (char *)s1; /* if s1 terminate early? */ if (pchk < s1 + i) pchk = s1 + i; do { k = *pchk; if (k == 0) return NULL; } while (pchk++ != s1 + l2); /* find the k's last presence in s2 (k = s1[l2]) */ for (i = l2; --i != (size_t)-1; ) { if (k == s2[i]) break; } /* shift */ s1 += l2 - i; } } #ifdef __i386__ # define RDTSC_CLOBBER "%eax", "%ebx", "%ecx", "%edx" #elif __x86_64__ # define RDTSC_CLOBBER "%rax", "%rbx", "%rcx", "%rdx" #else # error unknown platform #endif #define RDTSC_START(cycles) \ do { \ register unsigned cyc_high, cyc_low; \ asm volatile("CPUID\n\t" \ "RDTSC\n\t" \ "mov %%edx, %0\n\t" \ "mov %%eax, %1\n\t" \ : "=r" (cyc_high), "=r" (cyc_low) \ :: RDTSC_CLOBBER); \ (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ } while (0) #define RDTSC_STOP(cycles) \ do { \ register unsigned cyc_high, cyc_low; \ asm volatile("RDTSCP\n\t" \ "mov %%edx, %0\n\t" \ "mov %%eax, %1\n\t" \ "CPUID\n\t" \ : "=r" (cyc_high), "=r" (cyc_low) \ :: RDTSC_CLOBBER); \ (cycles) = ((uint64_t)cyc_high << 32) | cyc_low; \ } while (0) typedef unsigned long long TIME_T; #define start_time(start) RDTSC_START(start) #define stop_time(stop) RDTSC_STOP(stop) #define diff_time(start, stop) (stop - start) #define MAX_HAYSTACK_LENGTH 64 #define MAX_NEEDLE_LENGTH 16 #define TEST_LOOPS 1000 char haystack[MAX_HAYSTACK_LENGTH + 1]; char needle[MAX_NEEDLE_LENGTH + 1]; int main(int argc, char **argv) { size_t i, j, n; void *p1, *p2; srand(time(0)); for (i = 0; i < MAX_HAYSTACK_LENGTH; ) { haystack[i] = rand(); if (haystack[i] != 0) i++; } haystack[i] = 0; for (i = 0; i < MAX_HAYSTACK_LENGTH; i++) { TIME_T start, stop; unsigned long long elapsed1, elapsed2; j = rand() % MAX_NEEDLE_LENGTH; if (i <= MAX_HAYSTACK_LENGTH - (MAX_NEEDLE_LENGTH - j)) n = i; else n = MAX_HAYSTACK_LENGTH - (MAX_NEEDLE_LENGTH - j); memcpy(needle + j, haystack + n, MAX_NEEDLE_LENGTH - j); needle[MAX_NEEDLE_LENGTH] = 0; elapsed1 = ~0UL; for (n = 0; n < TEST_LOOPS; n++) { start_time(start); asm volatile("":::"memory"); p1 = strstr1(haystack, needle + j); asm volatile("":::"memory"); stop_time(stop); if (elapsed1 > diff_time(start, stop)) elapsed1 = diff_time(start, stop); } elapsed2 = ~0UL; for (n = 0; n < TEST_LOOPS; n++) { start_time(start); asm volatile("":::"memory"); p2 = strstr2(haystack, needle + j); asm volatile("":::"memory"); stop_time(stop); if (elapsed2 > diff_time(start, stop)) elapsed2 = diff_time(start, stop); } if (p1 != p2) fprintf(stderr, "Error: %p != %p\n", p1, p2); else fprintf(stdout, "%3d, %3d:\t%lld,\t%lld\n", i, j, elapsed1, elapsed2); } return 0; } ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2018-07-29 7:40 UTC | newest] Thread overview: 8+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2018-07-22 17:37 [PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr() Zhaoxiu Zeng 2018-07-22 18:37 ` Greg Kroah-Hartman 2018-07-26 17:17 ` Zhaoxiu Zeng 2018-07-27 5:48 ` Zhaoxiu Zeng 2018-07-27 10:39 ` Andy Shevchenko 2018-07-28 14:02 ` Zhaoxiu Zeng 2018-07-28 14:38 ` Greg Kroah-Hartman 2018-07-29 7:37 ` Zhaoxiu Zeng
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox