1 | /* Measure STRCHR functions. |
2 | Copyright (C) 2013-2024 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 TEST_MAIN |
20 | #ifndef WIDE |
21 | # ifdef USE_FOR_STRCHRNUL |
22 | # define TEST_NAME "strchrnul" |
23 | # else |
24 | # define TEST_NAME "strchr" |
25 | # endif /* !USE_FOR_STRCHRNUL */ |
26 | #else |
27 | # ifdef USE_FOR_STRCHRNUL |
28 | # define TEST_NAME "wcschrnul" |
29 | # else |
30 | # define TEST_NAME "wcschr" |
31 | # endif /* !USE_FOR_STRCHRNUL */ |
32 | #endif /* WIDE */ |
33 | #include "bench-string.h" |
34 | |
35 | #include "json-lib.h" |
36 | #define BIG_CHAR MAX_CHAR |
37 | |
38 | #ifndef WIDE |
39 | # ifdef USE_FOR_STRCHRNUL |
40 | # undef STRCHR |
41 | # define STRCHR strchrnul |
42 | # endif /* !USE_FOR_STRCHRNUL */ |
43 | # define MIDDLE_CHAR 127 |
44 | # define SMALL_CHAR 23 |
45 | #else |
46 | # ifdef USE_FOR_STRCHRNUL |
47 | # undef STRCHR |
48 | # define STRCHR wcschrnul |
49 | # endif /* !USE_FOR_STRCHRNUL */ |
50 | # define MIDDLE_CHAR 1121 |
51 | # define SMALL_CHAR 851 |
52 | #endif /* WIDE */ |
53 | |
54 | #ifdef USE_FOR_STRCHRNUL |
55 | # define DO_RAND_TEST(...) |
56 | #else |
57 | # define DO_RAND_TEST(...) do_rand_test(__VA_ARGS__) |
58 | #endif |
59 | #ifdef USE_FOR_STRCHRNUL |
60 | # define NULLRET(endptr) endptr |
61 | #else |
62 | # define NULLRET(endptr) NULL |
63 | #endif /* !USE_FOR_STRCHRNUL */ |
64 | |
65 | |
66 | typedef CHAR *(*proto_t) (const CHAR *, int); |
67 | |
68 | IMPL (STRCHR, 1) |
69 | |
70 | #ifndef WIDE |
71 | char *generic_strchr (const char *, int); |
72 | char *generic_strchrnul (const char *, int); |
73 | |
74 | # ifndef USE_FOR_STRCHRNUL |
75 | IMPL (generic_strchr, 0) |
76 | # else |
77 | IMPL (generic_strchrnul, 0) |
78 | # endif |
79 | #endif |
80 | |
81 | #ifndef USE_FOR_STRCHRNUL |
82 | /* Random benchmarks for strchr (if return is CHAR or NULL). The |
83 | rational for the benchmark is returning null/char can be done with |
84 | predicate execution (i.e cmovcc on x86) or a branch. */ |
85 | |
86 | |
87 | /* Large enough that full history can't be stored in BHT. */ |
88 | #define NUM_SEARCH_CHARS 2048 |
89 | |
90 | /* Expectation is usecases of strchr check the return. Otherwise |
91 | strchrnul would almost always be better. Since there is another |
92 | branch coming we want to test the case where a potential branch in |
93 | strchr can be used to skip a later mispredict because of the |
94 | relationship between the two branches. */ |
95 | static void __attribute__ ((noinline, noclone)) |
96 | do_one_rand_plus_branch_test (json_ctx_t *json_ctx, impl_t *impl, |
97 | const CHAR *s, const CHAR *c) |
98 | { |
99 | size_t i, iters = INNER_LOOP_ITERS8; |
100 | int must_execute = 0; |
101 | timing_t start, stop, cur; |
102 | TIMING_NOW (start); |
103 | for (i = 0; i < iters; ++i) |
104 | { |
105 | if (CALL (impl, s, c[i % NUM_SEARCH_CHARS])) |
106 | { |
107 | /* We just need something that will force compiler to emit |
108 | a branch instead of conditional execution. */ |
109 | ++must_execute; |
110 | asm volatile("" : : :); |
111 | } |
112 | } |
113 | TIMING_NOW (stop); |
114 | |
115 | TIMING_DIFF (cur, start, stop); |
116 | |
117 | json_element_double (ctx: json_ctx, d: (double)cur / (double)iters); |
118 | } |
119 | |
120 | static void __attribute__ ((noinline, noclone)) |
121 | do_one_rand_test (json_ctx_t *json_ctx, impl_t *impl, const CHAR *s, |
122 | const CHAR *c) |
123 | { |
124 | size_t i, iters = INNER_LOOP_ITERS8; |
125 | timing_t start, stop, cur; |
126 | TIMING_NOW (start); |
127 | for (i = 0; i < iters; ++i) |
128 | { |
129 | CALL (impl, s, c[i % NUM_SEARCH_CHARS]); |
130 | } |
131 | TIMING_NOW (stop); |
132 | |
133 | TIMING_DIFF (cur, start, stop); |
134 | |
135 | json_element_double (ctx: json_ctx, d: (double)cur / (double)iters); |
136 | } |
137 | |
138 | static void |
139 | do_rand_test (json_ctx_t *json_ctx, size_t align, size_t pos, size_t len, |
140 | float perc_zero) |
141 | { |
142 | size_t i; |
143 | int perc_zero_int; |
144 | CHAR *buf = (CHAR *)buf1; |
145 | CHAR *c = (CHAR *)buf2; |
146 | align &= 127; |
147 | if ((align + len) * sizeof (CHAR) >= page_size) |
148 | return; |
149 | |
150 | /* Test is only interesting if we can hit both cases. */ |
151 | if (pos >= len) |
152 | return; |
153 | |
154 | /* Segfault if we run the test. */ |
155 | if (NUM_SEARCH_CHARS * sizeof (CHAR) > page_size) |
156 | return; |
157 | |
158 | for (i = 0; i < len; ++i) |
159 | { |
160 | buf[align + i] = 2; |
161 | } |
162 | buf[align + len] = 0; |
163 | buf[align + pos] = 1; |
164 | |
165 | perc_zero_int = perc_zero * RAND_MAX; |
166 | for (i = 0; i < NUM_SEARCH_CHARS; ++i) |
167 | { |
168 | if (rand () > perc_zero_int) |
169 | c[i] = 0; |
170 | else |
171 | c[i] = 1; |
172 | } |
173 | { |
174 | json_element_object_begin (ctx: json_ctx); |
175 | json_attr_uint (ctx: json_ctx, name: "rand" , d: 1); |
176 | json_attr_uint (ctx: json_ctx, name: "branch" , d: 1); |
177 | json_attr_double (ctx: json_ctx, name: "perc-zero" , d: perc_zero); |
178 | json_attr_uint (ctx: json_ctx, name: "length" , d: len); |
179 | json_attr_uint (ctx: json_ctx, name: "pos" , d: pos); |
180 | json_attr_uint (ctx: json_ctx, name: "alignment" , d: align); |
181 | json_array_begin (ctx: json_ctx, name: "timings" ); |
182 | |
183 | FOR_EACH_IMPL (impl, 0) |
184 | do_one_rand_plus_branch_test (json_ctx, impl, s: buf + align, c); |
185 | |
186 | json_array_end (ctx: json_ctx); |
187 | json_element_object_end (ctx: json_ctx); |
188 | } |
189 | { |
190 | json_element_object_begin (ctx: json_ctx); |
191 | json_attr_uint (ctx: json_ctx, name: "rand" , d: 1); |
192 | json_attr_uint (ctx: json_ctx, name: "branch" , d: 0); |
193 | json_attr_double (ctx: json_ctx, name: "perc-zero" , d: perc_zero); |
194 | json_attr_uint (ctx: json_ctx, name: "length" , d: len); |
195 | json_attr_uint (ctx: json_ctx, name: "pos" , d: pos); |
196 | json_attr_uint (ctx: json_ctx, name: "alignment" , d: align); |
197 | json_array_begin (ctx: json_ctx, name: "timings" ); |
198 | |
199 | FOR_EACH_IMPL (impl, 0) |
200 | do_one_rand_test (json_ctx, impl, s: buf + align, c); |
201 | |
202 | json_array_end (ctx: json_ctx); |
203 | json_element_object_end (ctx: json_ctx); |
204 | } |
205 | } |
206 | #endif |
207 | |
208 | static void |
209 | do_one_test (json_ctx_t *json_ctx, impl_t *impl, const CHAR *s, int c, |
210 | const CHAR *exp_res) |
211 | { |
212 | size_t i, iters = INNER_LOOP_ITERS8; |
213 | timing_t start, stop, cur; |
214 | const CHAR *res = CALL (impl, s, c); |
215 | if (res != exp_res) |
216 | { |
217 | error (status: 0, errnum: 0, format: "Wrong result in function %s %p != %p" , impl->name, res, |
218 | exp_res); |
219 | ret = 1; |
220 | return; |
221 | } |
222 | |
223 | TIMING_NOW (start); |
224 | for (i = 0; i < iters; ++i) |
225 | { |
226 | CALL (impl, s, c); |
227 | } |
228 | TIMING_NOW (stop); |
229 | |
230 | TIMING_DIFF (cur, start, stop); |
231 | |
232 | json_element_double (ctx: json_ctx, d: (double)cur / (double)iters); |
233 | } |
234 | |
235 | static void |
236 | do_test (json_ctx_t *json_ctx, size_t align, size_t pos, size_t len, |
237 | int seek_char, int max_char) |
238 | /* For wcschr: align here means align not in bytes, |
239 | but in wchar_ts, in bytes it will equal to align * (sizeof (wchar_t)) |
240 | len for wcschr here isn't in bytes but it's number of wchar_t symbols. */ |
241 | { |
242 | size_t i; |
243 | CHAR *result; |
244 | CHAR *buf = (CHAR *) buf1; |
245 | align &= 127; |
246 | if ((align + len) * sizeof (CHAR) >= page_size) |
247 | return; |
248 | |
249 | for (i = 0; i < len; ++i) |
250 | { |
251 | buf[align + i] = 32 + 23 * i % max_char; |
252 | if (buf[align + i] == seek_char) |
253 | buf[align + i] = seek_char + 1; |
254 | else if (buf[align + i] == 0) |
255 | buf[align + i] = 1; |
256 | } |
257 | buf[align + len] = 0; |
258 | |
259 | if (pos < len) |
260 | { |
261 | buf[align + pos] = seek_char; |
262 | result = buf + align + pos; |
263 | } |
264 | else if (seek_char == 0) |
265 | result = buf + align + len; |
266 | else |
267 | result = NULLRET (buf + align + len); |
268 | |
269 | json_element_object_begin (ctx: json_ctx); |
270 | json_attr_uint (ctx: json_ctx, name: "rand" , d: 0); |
271 | json_attr_uint (ctx: json_ctx, name: "length" , d: len); |
272 | json_attr_uint (ctx: json_ctx, name: "pos" , d: pos); |
273 | json_attr_uint (ctx: json_ctx, name: "seek_char" , d: seek_char); |
274 | json_attr_uint (ctx: json_ctx, name: "max_char" , d: max_char); |
275 | json_attr_uint (ctx: json_ctx, name: "alignment" , d: align); |
276 | json_array_begin (ctx: json_ctx, name: "timings" ); |
277 | |
278 | FOR_EACH_IMPL (impl, 0) |
279 | do_one_test (json_ctx, impl, s: buf + align, c: seek_char, exp_res: result); |
280 | |
281 | json_array_end (ctx: json_ctx); |
282 | json_element_object_end (ctx: json_ctx); |
283 | } |
284 | |
285 | int |
286 | test_main (void) |
287 | { |
288 | json_ctx_t json_ctx; |
289 | |
290 | size_t i, j; |
291 | test_init (); |
292 | |
293 | json_init (ctx: &json_ctx, indent_level: 0, stdout); |
294 | |
295 | json_document_begin (ctx: &json_ctx); |
296 | json_attr_string (ctx: &json_ctx, name: "timing_type" , TIMING_TYPE); |
297 | |
298 | json_attr_object_begin (ctx: &json_ctx, name: "functions" ); |
299 | json_attr_object_begin (ctx: &json_ctx, TEST_NAME); |
300 | json_attr_string (ctx: &json_ctx, name: "bench-variant" , s: "" ); |
301 | |
302 | json_array_begin (ctx: &json_ctx, name: "ifuncs" ); |
303 | FOR_EACH_IMPL (impl, 0) |
304 | json_element_string (ctx: &json_ctx, s: impl->name); |
305 | json_array_end (ctx: &json_ctx); |
306 | |
307 | json_array_begin (ctx: &json_ctx, name: "results" ); |
308 | |
309 | for (i = 1; i < 8; ++i) |
310 | { |
311 | do_test (json_ctx: &json_ctx, align: 0, pos: 16 << i, len: 2048, SMALL_CHAR, MIDDLE_CHAR); |
312 | do_test (json_ctx: &json_ctx, align: i, pos: 16 << i, len: 2048, SMALL_CHAR, MIDDLE_CHAR); |
313 | } |
314 | |
315 | for (i = 1; i < 8; ++i) |
316 | { |
317 | do_test (json_ctx: &json_ctx, align: 0, pos: 16 << i, len: 4096, SMALL_CHAR, MIDDLE_CHAR); |
318 | do_test (json_ctx: &json_ctx, align: i, pos: 16 << i, len: 4096, SMALL_CHAR, MIDDLE_CHAR); |
319 | } |
320 | |
321 | for (i = 1; i < 8; ++i) |
322 | { |
323 | do_test (json_ctx: &json_ctx, align: i, pos: 64, len: 256, SMALL_CHAR, MIDDLE_CHAR); |
324 | do_test (json_ctx: &json_ctx, align: i, pos: 64, len: 256, SMALL_CHAR, BIG_CHAR); |
325 | } |
326 | |
327 | for (i = 0; i < 8; ++i) |
328 | { |
329 | do_test (json_ctx: &json_ctx, align: 16 * i, pos: 256, len: 512, SMALL_CHAR, MIDDLE_CHAR); |
330 | do_test (json_ctx: &json_ctx, align: 16 * i, pos: 256, len: 512, SMALL_CHAR, BIG_CHAR); |
331 | } |
332 | |
333 | for (i = 0; i < 32; ++i) |
334 | { |
335 | do_test (json_ctx: &json_ctx, align: 0, pos: i, len: i + 1, SMALL_CHAR, MIDDLE_CHAR); |
336 | do_test (json_ctx: &json_ctx, align: 0, pos: i, len: i + 1, SMALL_CHAR, BIG_CHAR); |
337 | } |
338 | |
339 | for (i = 1; i < 8; ++i) |
340 | { |
341 | do_test (json_ctx: &json_ctx, align: 0, pos: 16 << i, len: 2048, seek_char: 0, MIDDLE_CHAR); |
342 | do_test (json_ctx: &json_ctx, align: i, pos: 16 << i, len: 2048, seek_char: 0, MIDDLE_CHAR); |
343 | } |
344 | |
345 | for (i = 1; i < 8; ++i) |
346 | { |
347 | do_test (json_ctx: &json_ctx, align: 0, pos: 16 << i, len: 4096, seek_char: 0, MIDDLE_CHAR); |
348 | do_test (json_ctx: &json_ctx, align: i, pos: 16 << i, len: 4096, seek_char: 0, MIDDLE_CHAR); |
349 | } |
350 | |
351 | for (i = 1; i < 8; ++i) |
352 | { |
353 | do_test (json_ctx: &json_ctx, align: i, pos: 64, len: 256, seek_char: 0, MIDDLE_CHAR); |
354 | do_test (json_ctx: &json_ctx, align: i, pos: 64, len: 256, seek_char: 0, BIG_CHAR); |
355 | } |
356 | |
357 | for (i = 0; i < 8; ++i) |
358 | { |
359 | do_test (json_ctx: &json_ctx, align: 16 * i, pos: 256, len: 512, seek_char: 0, MIDDLE_CHAR); |
360 | do_test (json_ctx: &json_ctx, align: 16 * i, pos: 256, len: 512, seek_char: 0, BIG_CHAR); |
361 | } |
362 | |
363 | for (i = 0; i < 32; ++i) |
364 | { |
365 | do_test (json_ctx: &json_ctx, align: 0, pos: i, len: i + 1, seek_char: 0, MIDDLE_CHAR); |
366 | do_test (json_ctx: &json_ctx, align: 0, pos: i, len: i + 1, seek_char: 0, BIG_CHAR); |
367 | } |
368 | |
369 | for (i = 16 / sizeof (CHAR); i <= 8192 / sizeof (CHAR); i += i) |
370 | { |
371 | for (j = 32 / sizeof (CHAR); j <= 320 / sizeof (CHAR); |
372 | j += 32 / sizeof (CHAR)) |
373 | { |
374 | do_test (json_ctx: &json_ctx, align: 0, pos: i, len: i + j, seek_char: 0, MIDDLE_CHAR); |
375 | do_test (json_ctx: &json_ctx, align: 0, pos: i + j, len: i, seek_char: 0, MIDDLE_CHAR); |
376 | if (i > j) |
377 | { |
378 | do_test (json_ctx: &json_ctx, align: 0, pos: i, len: i - j, seek_char: 0, MIDDLE_CHAR); |
379 | do_test (json_ctx: &json_ctx, align: 0, pos: i - j, len: i, seek_char: 0, MIDDLE_CHAR); |
380 | } |
381 | } |
382 | } |
383 | |
384 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.0); |
385 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.1); |
386 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.25); |
387 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.33); |
388 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.5); |
389 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.66); |
390 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.75); |
391 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.9); |
392 | DO_RAND_TEST (&json_ctx, 0, 15, 16, 1.0); |
393 | |
394 | json_array_end (ctx: &json_ctx); |
395 | json_attr_object_end (ctx: &json_ctx); |
396 | json_attr_object_end (ctx: &json_ctx); |
397 | json_document_end (ctx: &json_ctx); |
398 | |
399 | return ret; |
400 | } |
401 | |
402 | #include <support/test-driver.c> |
403 | |
404 | #ifndef WIDE |
405 | # undef STRCHRNUL |
406 | # define STRCHRNUL generic_strchrnul |
407 | # undef STRCHR |
408 | # define STRCHR generic_strchr |
409 | # include <string/strchrnul.c> |
410 | # include <string/strchr.c> |
411 | #endif |
412 | |