1 /* Measure STRCHR functions.
2 Copyright (C) 2013-2023 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 (json_ctx, (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 (json_ctx, (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 (json_ctx);
175 json_attr_uint (json_ctx, "rand", 1);
176 json_attr_uint (json_ctx, "branch", 1);
177 json_attr_double (json_ctx, "perc-zero", perc_zero);
178 json_attr_uint (json_ctx, "length", len);
179 json_attr_uint (json_ctx, "pos", pos);
180 json_attr_uint (json_ctx, "alignment", align);
181 json_array_begin (json_ctx, "timings");
182
183 FOR_EACH_IMPL (impl, 0)
184 do_one_rand_plus_branch_test (json_ctx, impl, buf + align, c);
185
186 json_array_end (json_ctx);
187 json_element_object_end (json_ctx);
188 }
189 {
190 json_element_object_begin (json_ctx);
191 json_attr_uint (json_ctx, "rand", 1);
192 json_attr_uint (json_ctx, "branch", 0);
193 json_attr_double (json_ctx, "perc-zero", perc_zero);
194 json_attr_uint (json_ctx, "length", len);
195 json_attr_uint (json_ctx, "pos", pos);
196 json_attr_uint (json_ctx, "alignment", align);
197 json_array_begin (json_ctx, "timings");
198
199 FOR_EACH_IMPL (impl, 0)
200 do_one_rand_test (json_ctx, impl, buf + align, c);
201
202 json_array_end (json_ctx);
203 json_element_object_end (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 (0, 0, "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 (json_ctx, (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 (json_ctx);
270 json_attr_uint (json_ctx, "rand", 0);
271 json_attr_uint (json_ctx, "length", len);
272 json_attr_uint (json_ctx, "pos", pos);
273 json_attr_uint (json_ctx, "seek_char", seek_char);
274 json_attr_uint (json_ctx, "max_char", max_char);
275 json_attr_uint (json_ctx, "alignment", align);
276 json_array_begin (json_ctx, "timings");
277
278 FOR_EACH_IMPL (impl, 0)
279 do_one_test (json_ctx, impl, buf + align, seek_char, result);
280
281 json_array_end (json_ctx);
282 json_element_object_end (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 (&json_ctx, 0, stdout);
294
295 json_document_begin (&json_ctx);
296 json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
297
298 json_attr_object_begin (&json_ctx, "functions");
299 json_attr_object_begin (&json_ctx, TEST_NAME);
300 json_attr_string (&json_ctx, "bench-variant", "");
301
302 json_array_begin (&json_ctx, "ifuncs");
303 FOR_EACH_IMPL (impl, 0)
304 json_element_string (&json_ctx, impl->name);
305 json_array_end (&json_ctx);
306
307 json_array_begin (&json_ctx, "results");
308
309 for (i = 1; i < 8; ++i)
310 {
311 do_test (&json_ctx, 0, 16 << i, 2048, SMALL_CHAR, MIDDLE_CHAR);
312 do_test (&json_ctx, i, 16 << i, 2048, SMALL_CHAR, MIDDLE_CHAR);
313 }
314
315 for (i = 1; i < 8; ++i)
316 {
317 do_test (&json_ctx, 0, 16 << i, 4096, SMALL_CHAR, MIDDLE_CHAR);
318 do_test (&json_ctx, i, 16 << i, 4096, SMALL_CHAR, MIDDLE_CHAR);
319 }
320
321 for (i = 1; i < 8; ++i)
322 {
323 do_test (&json_ctx, i, 64, 256, SMALL_CHAR, MIDDLE_CHAR);
324 do_test (&json_ctx, i, 64, 256, SMALL_CHAR, BIG_CHAR);
325 }
326
327 for (i = 0; i < 8; ++i)
328 {
329 do_test (&json_ctx, 16 * i, 256, 512, SMALL_CHAR, MIDDLE_CHAR);
330 do_test (&json_ctx, 16 * i, 256, 512, SMALL_CHAR, BIG_CHAR);
331 }
332
333 for (i = 0; i < 32; ++i)
334 {
335 do_test (&json_ctx, 0, i, i + 1, SMALL_CHAR, MIDDLE_CHAR);
336 do_test (&json_ctx, 0, i, i + 1, SMALL_CHAR, BIG_CHAR);
337 }
338
339 for (i = 1; i < 8; ++i)
340 {
341 do_test (&json_ctx, 0, 16 << i, 2048, 0, MIDDLE_CHAR);
342 do_test (&json_ctx, i, 16 << i, 2048, 0, MIDDLE_CHAR);
343 }
344
345 for (i = 1; i < 8; ++i)
346 {
347 do_test (&json_ctx, 0, 16 << i, 4096, 0, MIDDLE_CHAR);
348 do_test (&json_ctx, i, 16 << i, 4096, 0, MIDDLE_CHAR);
349 }
350
351 for (i = 1; i < 8; ++i)
352 {
353 do_test (&json_ctx, i, 64, 256, 0, MIDDLE_CHAR);
354 do_test (&json_ctx, i, 64, 256, 0, BIG_CHAR);
355 }
356
357 for (i = 0; i < 8; ++i)
358 {
359 do_test (&json_ctx, 16 * i, 256, 512, 0, MIDDLE_CHAR);
360 do_test (&json_ctx, 16 * i, 256, 512, 0, BIG_CHAR);
361 }
362
363 for (i = 0; i < 32; ++i)
364 {
365 do_test (&json_ctx, 0, i, i + 1, 0, MIDDLE_CHAR);
366 do_test (&json_ctx, 0, i, i + 1, 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, 0, i, i + j, 0, MIDDLE_CHAR);
375 do_test (&json_ctx, 0, i + j, i, 0, MIDDLE_CHAR);
376 if (i > j)
377 {
378 do_test (&json_ctx, 0, i, i - j, 0, MIDDLE_CHAR);
379 do_test (&json_ctx, 0, i - j, i, 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 (&json_ctx);
395 json_attr_object_end (&json_ctx);
396 json_attr_object_end (&json_ctx);
397 json_document_end (&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