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
66typedef CHAR *(*proto_t) (const CHAR *, int);
67
68IMPL (STRCHR, 1)
69
70#ifndef WIDE
71char *generic_strchr (const char *, int);
72char *generic_strchrnul (const char *, int);
73
74# ifndef USE_FOR_STRCHRNUL
75IMPL (generic_strchr, 0)
76# else
77IMPL (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. */
95static void __attribute__ ((noinline, noclone))
96do_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
120static void __attribute__ ((noinline, noclone))
121do_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
138static void
139do_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
208static void
209do_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
235static void
236do_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
285int
286test_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

source code of glibc/benchtests/bench-strchr.c