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