1 /* Measure strstr functions.
2 Copyright (C) 2013-2021 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
19 #define MIN_PAGE_SIZE 131072
21 #define TEST_NAME "strstr"
22 #include "bench-string.h"
24 static const char input[] =
25 "This manual is written with the assumption that you are at least "
26 "somewhat familiar with the C programming language and basic programming "
27 "concepts. Specifically, familiarity with ISO standard C (*note ISO "
28 "C::), rather than “traditional” pre-ISO C dialects, is assumed.\n"
30 " The GNU C Library includes several “header files”, each of which "
31 "provides definitions and declarations for a group of related facilities; "
32 "this information is used by the C compiler when processing your program. "
33 "For example, the header file ‘stdio.h’ declares facilities for "
34 "performing input and output, and the header file ‘string.h’ declares "
35 "string processing utilities. The organization of this manual generally "
36 "follows the same division as the header files.\n"
38 " If you are reading this manual for the first time, you should read "
39 "all of the introductory material and skim the remaining chapters. There "
40 "are a _lot_ of functions in the GNU C Library and it’s not realistic to "
41 "expect that you will be able to remember exactly _how_ to use each and "
42 "every one of them. It’s more important to become generally familiar "
43 "with the kinds of facilities that the library provides, so that when you "
44 "are writing your programs you can recognize _when_ to make use of "
45 "library functions, and _where_ in this manual you can find more specific "
46 "information about them.\n";
48 /* Simple yet efficient strstr - for needles < 32 bytes it is 2-4 times
49 faster than the optimized twoway_strstr. */
51 basic_strstr (const char *s1, const char *s2)
59 for ( ; s1[0] != '\0'; s1++)
63 for (i = 1; s2[i] != 0; i++)
73 #define RETURN_TYPE char *
74 #define AVAILABLE(h, h_l, j, n_l) \
75 (((j) + (n_l) <= (h_l)) \
76 || ((h_l) += __strnlen ((void*)((h) + (h_l)), (n_l) + 512), \
77 (j) + (n_l) <= (h_l)))
79 #define RET0_IF_0(a) if (!a) goto ret0
80 #define FASTSEARCH(S,C,N) (void*) strchr ((void*)(S), (C))
81 #define LONG_NEEDLE_THRESHOLD 32U
82 #define __strnlen strnlen
83 #include "string/str-two-way.h"
85 /* Optimized Two-way implementation from GLIBC 2.29. */
87 twoway_strstr (const char *haystack, const char *needle)
89 size_t needle_len; /* Length of NEEDLE. */
90 size_t haystack_len; /* Known minimum length of HAYSTACK. */
92 /* Handle empty NEEDLE special case. */
93 if (needle[0] == '\0')
94 return (char *) haystack;
96 /* Skip until we find the first matching char from NEEDLE. */
97 haystack = strchr (haystack, needle[0]);
98 if (haystack == NULL || needle[1] == '\0')
99 return (char *) haystack;
101 /* Ensure HAYSTACK length is at least as long as NEEDLE length.
102 Since a match may occur early on in a huge HAYSTACK, use strnlen
103 and read ahead a few cachelines for improved performance. */
104 needle_len = strlen (needle);
105 haystack_len = __strnlen (haystack, needle_len + 256);
106 if (haystack_len < needle_len)
109 /* Check whether we have a match. This improves performance since we avoid
110 the initialization overhead of the two-way algorithm. */
111 if (memcmp (haystack, needle, needle_len) == 0)
112 return (char *) haystack;
114 /* Perform the search. Abstract memory is considered to be an array
115 of 'unsigned char' values, not an array of 'char' values. See
116 ISO C 99 section 6.2.6.1. */
117 if (needle_len < LONG_NEEDLE_THRESHOLD)
118 return two_way_short_needle ((const unsigned char *) haystack,
120 (const unsigned char *) needle, needle_len);
121 return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
122 (const unsigned char *) needle, needle_len);
125 typedef char *(*proto_t) (const char *, const char *);
128 IMPL (twoway_strstr, 0)
129 IMPL (basic_strstr, 0)
132 do_one_test (impl_t *impl, const char *s1, const char *s2, char *exp_result)
134 size_t i, iters = INNER_LOOP_ITERS_SMALL / 8;
135 timing_t start, stop, cur;
139 for (i = 0; i < iters; ++i)
140 res = CALL (impl, s1, s2);
143 TIMING_DIFF (cur, start, stop);
145 TIMING_PRINT_MEAN ((double) cur, (double) iters);
147 if (res != exp_result)
149 error (0, 0, "Wrong result in function %s %s %s", impl->name,
150 (res == NULL) ? "(null)" : res,
151 (exp_result == NULL) ? "(null)" : exp_result);
158 do_test (size_t align1, size_t align2, size_t len1, size_t len2,
161 char *s1 = (char *) (buf1 + align1);
162 char *s2 = (char *) (buf2 + align2);
164 size_t size = sizeof (input) - 1;
165 size_t pos = (len1 + len2) % size;
168 for (size_t l = len2; l > 0; l = l > size ? l - size : 0)
170 size_t t = l > size ? size : l;
172 ss2 = mempcpy (ss2, input + pos, t);
175 ss2 = mempcpy (ss2, input + pos, size - pos);
176 ss2 = mempcpy (ss2, input, t - (size - pos));
182 for (size_t l = len1; l > 0; l = l > size ? l - size : 0)
184 size_t t = l > size ? size : l;
185 memcpy (ss1, input, t);
190 memcpy (s1 + len1 - len2, s2, len2);
193 /* Remove any accidental matches except for the last if !fail. */
194 for (ss1 = basic_strstr (s1, s2); ss1; ss1 = basic_strstr (ss1 + 1, s2))
195 if (fail || ss1 != s1 + len1 - len2)
198 printf ("Length %4zd/%3zd, alignment %2zd/%2zd, %s:",
199 len1, len2, align1, align2, fail ? "fail " : "found");
201 FOR_EACH_IMPL (impl, 0)
202 do_one_test (impl, s1, s2, fail ? NULL : s1 + len1 - len2);
207 /* Test needles which exhibit worst-case performance. This shows that
208 basic_strstr is quadratic and thus unsuitable for large needles.
209 On the other hand Two-way and skip table implementations are linear with
210 increasing needle sizes. The slowest cases of the two implementations are
211 within a factor of 2 on several different microarchitectures. */
214 test_hard_needle (size_t ne_len, size_t hs_len)
216 char *ne = (char *) buf1;
217 char *hs = (char *) buf2;
219 /* Hard needle for strstr algorithm using skip table. This results in many
220 memcmp calls comparing most of the needle. */
222 memset (ne, 'a', ne_len);
224 ne[ne_len - 14] = 'b';
226 memset (hs, 'a', hs_len);
227 for (size_t i = ne_len; i <= hs_len; i += ne_len)
233 printf ("Length %4zd/%3zd, complex needle 1:", hs_len, ne_len);
235 FOR_EACH_IMPL (impl, 0)
236 do_one_test (impl, hs, ne, NULL);
240 /* 2nd hard needle for strstr algorithm using skip table. This results in
241 many memcmp calls comparing most of the needle. */
243 memset (ne, 'a', ne_len);
245 ne[ne_len - 6] = 'b';
247 memset (hs, 'a', hs_len);
248 for (size_t i = ne_len; i <= hs_len; i += ne_len)
254 printf ("Length %4zd/%3zd, complex needle 2:", hs_len, ne_len);
256 FOR_EACH_IMPL (impl, 0)
257 do_one_test (impl, hs, ne, NULL);
261 /* Hard needle for Two-way algorithm - the random input causes a large number
262 of branch mispredictions which significantly reduces performance on modern
263 micro architectures. */
265 for (int i = 0; i < hs_len; i++)
266 hs[i] = (rand () & 255) > 155 ? 'a' : 'b';
269 memset (ne, 'a', ne_len);
274 printf ("Length %4zd/%3zd, complex needle 3:", hs_len, ne_len);
276 FOR_EACH_IMPL (impl, 0)
277 do_one_test (impl, hs, ne, NULL);
288 FOR_EACH_IMPL (impl, 0)
289 printf ("\t%s", impl->name);
292 for (size_t hlen = 64; hlen <= 256; hlen += 32)
293 for (size_t klen = 1; klen <= 16; klen++)
295 do_test (1, 3, hlen, klen, 0);
296 do_test (0, 9, hlen, klen, 1);
299 for (size_t hlen = 256; hlen <= 65536; hlen *= 2)
300 for (size_t klen = 16; klen <= 256; klen *= 2)
302 do_test (1, 11, hlen, klen, 0);
303 do_test (14, 5, hlen, klen, 1);
306 test_hard_needle (64, 65536);
307 test_hard_needle (256, 65536);
308 test_hard_needle (1024, 65536);
313 #include <support/test-driver.c>