]>
Commit | Line | Data |
---|---|---|
97020474 | 1 | /* Measure strstr functions. |
04277e02 | 2 | Copyright (C) 2013-2019 Free Software Foundation, Inc. |
97020474 SP |
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 | <http://www.gnu.org/licenses/>. */ | |
18 | ||
93eebae5 | 19 | #define MIN_PAGE_SIZE 131072 |
97020474 SP |
20 | #define TEST_MAIN |
21 | #define TEST_NAME "strstr" | |
22 | #include "bench-string.h" | |
23 | ||
93eebae5 WD |
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. */ | |
97020474 | 50 | static char * |
93eebae5 | 51 | basic_strstr (const char *s1, const char *s2) |
97020474 | 52 | { |
93eebae5 WD |
53 | size_t i; |
54 | int c = s2[0]; | |
97020474 | 55 | |
93eebae5 WD |
56 | if (c == 0) |
57 | return (char*)s1; | |
97020474 | 58 | |
93eebae5 | 59 | for ( ; s1[0] != '\0'; s1++) |
97020474 | 60 | { |
93eebae5 WD |
61 | if (s1[0] != c) |
62 | continue; | |
63 | for (i = 1; s2[i] != 0; i++) | |
64 | if (s1[i] != s2[i]) | |
97020474 | 65 | break; |
93eebae5 WD |
66 | if (s2[i] == '\0') |
67 | return (char*)s1; | |
97020474 SP |
68 | } |
69 | ||
70 | return NULL; | |
71 | } | |
72 | ||
93eebae5 WD |
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 * | |
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 | } | |
97020474 SP |
124 | |
125 | typedef char *(*proto_t) (const char *, const char *); | |
126 | ||
97020474 | 127 | IMPL (strstr, 1) |
93eebae5 WD |
128 | IMPL (twoway_strstr, 0) |
129 | IMPL (basic_strstr, 0) | |
97020474 SP |
130 | |
131 | static void | |
132 | do_one_test (impl_t *impl, const char *s1, const char *s2, char *exp_result) | |
133 | { | |
46ae0732 | 134 | size_t i, iters = INNER_LOOP_ITERS_SMALL; |
44558701 | 135 | timing_t start, stop, cur; |
93eebae5 | 136 | char *res; |
44558701 WN |
137 | |
138 | TIMING_NOW (start); | |
139 | for (i = 0; i < iters; ++i) | |
93eebae5 | 140 | res = CALL (impl, s1, s2); |
44558701 | 141 | TIMING_NOW (stop); |
97020474 | 142 | |
44558701 | 143 | TIMING_DIFF (cur, start, stop); |
97020474 | 144 | |
44558701 | 145 | TIMING_PRINT_MEAN ((double) cur, (double) iters); |
93eebae5 WD |
146 | |
147 | if (res != exp_result) | |
148 | { | |
149 | error (0, 0, "Wrong result in function %s %s %s", impl->name, | |
f0c5a803 SL |
150 | (res == NULL) ? "(null)" : res, |
151 | (exp_result == NULL) ? "(null)" : exp_result); | |
93eebae5 WD |
152 | ret = 1; |
153 | } | |
97020474 SP |
154 | } |
155 | ||
156 | ||
157 | static void | |
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 | ||
93eebae5 WD |
164 | size_t size = sizeof (input) - 1; |
165 | size_t pos = (len1 + len2) % size; | |
97020474 | 166 | |
93eebae5 WD |
167 | char *ss2 = s2; |
168 | for (size_t l = len2; l > 0; l = l > size ? l - size : 0) | |
97020474 | 169 | { |
93eebae5 WD |
170 | size_t t = l > size ? size : l; |
171 | if (pos + t <= size) | |
172 | ss2 = mempcpy (ss2, input + pos, t); | |
173 | else | |
97020474 | 174 | { |
93eebae5 WD |
175 | ss2 = mempcpy (ss2, input + pos, size - pos); |
176 | ss2 = mempcpy (ss2, input, t - (size - pos)); | |
97020474 SP |
177 | } |
178 | } | |
93eebae5 WD |
179 | s2[len2] = '\0'; |
180 | ||
181 | char *ss1 = s1; | |
182 | for (size_t l = len1; l > 0; l = l > size ? l - size : 0) | |
97020474 | 183 | { |
93eebae5 WD |
184 | size_t t = l > size ? size : l; |
185 | memcpy (ss1, input, t); | |
186 | ss1 += t; | |
97020474 | 187 | } |
93eebae5 WD |
188 | |
189 | if (!fail) | |
190 | memcpy (s1 + len1 - len2, s2, len2); | |
97020474 SP |
191 | s1[len1] = '\0'; |
192 | ||
93eebae5 WD |
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"); | |
97020474 SP |
200 | |
201 | FOR_EACH_IMPL (impl, 0) | |
202 | do_one_test (impl, s1, s2, fail ? NULL : s1 + len1 - len2); | |
203 | ||
44558701 | 204 | putchar ('\n'); |
97020474 SP |
205 | } |
206 | ||
80b2bfb5 WD |
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 | |
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 | ||
97020474 SP |
282 | static int |
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 | ||
93eebae5 WD |
292 | for (size_t hlen = 64; hlen <= 256; hlen += 32) |
293 | for (size_t klen = 1; klen <= 16; klen++) | |
97020474 | 294 | { |
93eebae5 | 295 | do_test (1, 3, hlen, klen, 0); |
97020474 | 296 | do_test (0, 9, hlen, klen, 1); |
97020474 SP |
297 | } |
298 | ||
93eebae5 WD |
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 | } | |
97020474 | 305 | |
80b2bfb5 WD |
306 | test_hard_needle (64, 65536); |
307 | test_hard_needle (256, 65536); | |
308 | test_hard_needle (1024, 65536); | |
309 | ||
97020474 SP |
310 | return ret; |
311 | } | |
312 | ||
b598e134 | 313 | #include <support/test-driver.c> |