1 /* Measure strstr functions.
2 Copyright (C) 2013-2021 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
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.
9
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.
14
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/>. */
18
19 #define MIN_PAGE_SIZE 131072
20 #define TEST_MAIN
21 #define TEST_NAME "strstr"
22 #include "bench-string.h"
23
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"
29
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"
37
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";
47
48 /* Simple yet efficient strstr - for needles < 32 bytes it is 2-4 times
49 faster than the optimized twoway_strstr. */
50 static char *
basic_strstr(const char * s1,const char * s2)51 basic_strstr (const char *s1, const char *s2)
52 {
53 size_t i;
54 int c = s2[0];
55
56 if (c == 0)
57 return (char*)s1;
58
59 for ( ; s1[0] != '\0'; s1++)
60 {
61 if (s1[0] != c)
62 continue;
63 for (i = 1; s2[i] != 0; i++)
64 if (s1[i] != s2[i])
65 break;
66 if (s2[i] == '\0')
67 return (char*)s1;
68 }
69
70 return NULL;
71 }
72
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)))
78 #define CHECK_EOL (1)
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"
84
85 /* Optimized Two-way implementation from GLIBC 2.29. */
86 static char *
twoway_strstr(const char * haystack,const char * needle)87 twoway_strstr (const char *haystack, const char *needle)
88 {
89 size_t needle_len; /* Length of NEEDLE. */
90 size_t haystack_len; /* Known minimum length of HAYSTACK. */
91
92 /* Handle empty NEEDLE special case. */
93 if (needle[0] == '\0')
94 return (char *) haystack;
95
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;
100
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)
107 return NULL;
108
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;
113
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,
119 haystack_len,
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);
123 }
124
125 typedef char *(*proto_t) (const char *, const char *);
126
127 IMPL (strstr, 1)
128 IMPL (twoway_strstr, 0)
129 IMPL (basic_strstr, 0)
130
131 static void
do_one_test(impl_t * impl,const char * s1,const char * s2,char * exp_result)132 do_one_test (impl_t *impl, const char *s1, const char *s2, char *exp_result)
133 {
134 size_t i, iters = INNER_LOOP_ITERS_SMALL / 8;
135 timing_t start, stop, cur;
136 char *res;
137
138 TIMING_NOW (start);
139 for (i = 0; i < iters; ++i)
140 res = CALL (impl, s1, s2);
141 TIMING_NOW (stop);
142
143 TIMING_DIFF (cur, start, stop);
144
145 TIMING_PRINT_MEAN ((double) cur, (double) iters);
146
147 if (res != exp_result)
148 {
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);
152 ret = 1;
153 }
154 }
155
156
157 static void
do_test(size_t align1,size_t align2,size_t len1,size_t len2,int fail)158 do_test (size_t align1, size_t align2, size_t len1, size_t len2,
159 int fail)
160 {
161 char *s1 = (char *) (buf1 + align1);
162 char *s2 = (char *) (buf2 + align2);
163
164 size_t size = sizeof (input) - 1;
165 size_t pos = (len1 + len2) % size;
166
167 char *ss2 = s2;
168 for (size_t l = len2; l > 0; l = l > size ? l - size : 0)
169 {
170 size_t t = l > size ? size : l;
171 if (pos + t <= size)
172 ss2 = mempcpy (ss2, input + pos, t);
173 else
174 {
175 ss2 = mempcpy (ss2, input + pos, size - pos);
176 ss2 = mempcpy (ss2, input, t - (size - pos));
177 }
178 }
179 s2[len2] = '\0';
180
181 char *ss1 = s1;
182 for (size_t l = len1; l > 0; l = l > size ? l - size : 0)
183 {
184 size_t t = l > size ? size : l;
185 memcpy (ss1, input, t);
186 ss1 += t;
187 }
188
189 if (!fail)
190 memcpy (s1 + len1 - len2, s2, len2);
191 s1[len1] = '\0';
192
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)
196 ++ss1[len2 / 2];
197
198 printf ("Length %4zd/%3zd, alignment %2zd/%2zd, %s:",
199 len1, len2, align1, align2, fail ? "fail " : "found");
200
201 FOR_EACH_IMPL (impl, 0)
202 do_one_test (impl, s1, s2, fail ? NULL : s1 + len1 - len2);
203
204 putchar ('\n');
205 }
206
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. */
212
213 static void
test_hard_needle(size_t ne_len,size_t hs_len)214 test_hard_needle (size_t ne_len, size_t hs_len)
215 {
216 char *ne = (char *) buf1;
217 char *hs = (char *) buf2;
218
219 /* Hard needle for strstr algorithm using skip table. This results in many
220 memcmp calls comparing most of the needle. */
221 {
222 memset (ne, 'a', ne_len);
223 ne[ne_len] = '\0';
224 ne[ne_len - 14] = 'b';
225
226 memset (hs, 'a', hs_len);
227 for (size_t i = ne_len; i <= hs_len; i += ne_len)
228 {
229 hs[i-5] = 'b';
230 hs[i-62] = 'b';
231 }
232
233 printf ("Length %4zd/%3zd, complex needle 1:", hs_len, ne_len);
234
235 FOR_EACH_IMPL (impl, 0)
236 do_one_test (impl, hs, ne, NULL);
237 putchar ('\n');
238 }
239
240 /* 2nd hard needle for strstr algorithm using skip table. This results in
241 many memcmp calls comparing most of the needle. */
242 {
243 memset (ne, 'a', ne_len);
244 ne[ne_len] = '\0';
245 ne[ne_len - 6] = 'b';
246
247 memset (hs, 'a', hs_len);
248 for (size_t i = ne_len; i <= hs_len; i += ne_len)
249 {
250 hs[i-5] = 'b';
251 hs[i-6] = 'b';
252 }
253
254 printf ("Length %4zd/%3zd, complex needle 2:", hs_len, ne_len);
255
256 FOR_EACH_IMPL (impl, 0)
257 do_one_test (impl, hs, ne, NULL);
258 putchar ('\n');
259 }
260
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. */
264 {
265 for (int i = 0; i < hs_len; i++)
266 hs[i] = (rand () & 255) > 155 ? 'a' : 'b';
267 hs[hs_len] = 0;
268
269 memset (ne, 'a', ne_len);
270 ne[ne_len-2] = 'b';
271 ne[0] = 'b';
272 ne[ne_len] = 0;
273
274 printf ("Length %4zd/%3zd, complex needle 3:", hs_len, ne_len);
275
276 FOR_EACH_IMPL (impl, 0)
277 do_one_test (impl, hs, ne, NULL);
278 putchar ('\n');
279 }
280 }
281
282 static int
test_main(void)283 test_main (void)
284 {
285 test_init ();
286
287 printf ("%23s", "");
288 FOR_EACH_IMPL (impl, 0)
289 printf ("\t%s", impl->name);
290 putchar ('\n');
291
292 for (size_t hlen = 64; hlen <= 256; hlen += 32)
293 for (size_t klen = 1; klen <= 16; klen++)
294 {
295 do_test (1, 3, hlen, klen, 0);
296 do_test (0, 9, hlen, klen, 1);
297 }
298
299 for (size_t hlen = 256; hlen <= 65536; hlen *= 2)
300 for (size_t klen = 16; klen <= 256; klen *= 2)
301 {
302 do_test (1, 11, hlen, klen, 0);
303 do_test (14, 5, hlen, klen, 1);
304 }
305
306 test_hard_needle (64, 65536);
307 test_hard_needle (256, 65536);
308 test_hard_needle (1024, 65536);
309
310 return ret;
311 }
312
313 #include <support/test-driver.c>
314