benchtests/bench-strchr.c

   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 #  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 *
  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))
  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))
 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
 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
 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
 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
 287 test_main (void)
 288 {
 289   json_ctx_t json_ctx;
 290
 291   size_t i, j;
 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   for (i = 16 / sizeof (CHAR); i <= 8192 / sizeof (CHAR); i += i)
 371     {
 372       for (j = 32 / sizeof (CHAR); j <= 320 / sizeof (CHAR);
 373            j += 32 / sizeof (CHAR))
 374         {
 375           do_test (&json_ctx, 0, i, i + j, 0, MIDDLE_CHAR);
 376           do_test (&json_ctx, 0, i + j, i, 0, MIDDLE_CHAR);
 377           if (i > j)
 378             {
 379               do_test (&json_ctx, 0, i, i - j, 0, MIDDLE_CHAR);
 380               do_test (&json_ctx, 0, i - j, i, 0, MIDDLE_CHAR);
 381             }
 382         }
 383     }
 384
 385   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.0);
 386   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.1);
 387   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.25);
 388   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.33);
 389   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.5);
 390   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.66);
 391   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.75);
 392   DO_RAND_TEST (&json_ctx, 0, 15, 16, 0.9);
 393   DO_RAND_TEST (&json_ctx, 0, 15, 16, 1.0);
 394
 395   json_array_end (&json_ctx);
 396   json_attr_object_end (&json_ctx);
 397   json_attr_object_end (&json_ctx);
 398   json_document_end (&json_ctx);
 399
 400   return ret;
 401 }
 402
 403 #include <support/test-driver.c>