1 | /* Measure strstr functions. |
2 | Copyright (C) 2013-2022 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 * |
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 * |
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 (haystack: (const unsigned char *) haystack, |
119 | haystack_len, |
120 | needle: (const unsigned char *) needle, needle_len); |
121 | return two_way_long_needle (haystack: (const unsigned char *) haystack, haystack_len, |
122 | needle: (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 |
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 (status: 0, errnum: 0, format: "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 |
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 (s1: ss1 + 1, s2)) |
195 | if (fail || ss1 != s1 + len1 - len2) |
196 | ++ss1[len2 / 2]; |
197 | |
198 | printf (format: "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, exp_result: fail ? NULL : s1 + len1 - len2); |
203 | |
204 | putchar (c: '\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 |
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 (format: "Length %4zd/%3zd, complex needle 1:" , hs_len, ne_len); |
234 | |
235 | FOR_EACH_IMPL (impl, 0) |
236 | do_one_test (impl, s1: hs, s2: ne, NULL); |
237 | putchar (c: '\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 (format: "Length %4zd/%3zd, complex needle 2:" , hs_len, ne_len); |
255 | |
256 | FOR_EACH_IMPL (impl, 0) |
257 | do_one_test (impl, s1: hs, s2: ne, NULL); |
258 | putchar (c: '\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 (format: "Length %4zd/%3zd, complex needle 3:" , hs_len, ne_len); |
275 | |
276 | FOR_EACH_IMPL (impl, 0) |
277 | do_one_test (impl, s1: hs, s2: ne, NULL); |
278 | putchar (c: '\n'); |
279 | } |
280 | } |
281 | |
282 | static int |
283 | test_main (void) |
284 | { |
285 | test_init (); |
286 | |
287 | printf (format: "%23s" , "" ); |
288 | FOR_EACH_IMPL (impl, 0) |
289 | printf (format: "\t%s" , impl->name); |
290 | putchar (c: '\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 (align1: 1, align2: 3, len1: hlen, len2: klen, fail: 0); |
296 | do_test (align1: 0, align2: 9, len1: hlen, len2: klen, fail: 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 (align1: 1, align2: 11, len1: hlen, len2: klen, fail: 0); |
303 | do_test (align1: 14, align2: 5, len1: hlen, len2: klen, fail: 1); |
304 | } |
305 | |
306 | test_hard_needle (ne_len: 64, hs_len: 65536); |
307 | test_hard_needle (ne_len: 256, hs_len: 65536); |
308 | test_hard_needle (ne_len: 1024, hs_len: 65536); |
309 | |
310 | return ret; |
311 | } |
312 | |
313 | #include <support/test-driver.c> |
314 | |