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 # 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