Re: [PATCH v1 02/23] benchtests: Add random benchmark in bench-strchr.c

["H.J. Lu" <hjl.tools@gmail.com>]

On Wed, Mar 23, 2022 at 2:58 PM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> Add benchmark that randomizes whether return should be NULL or pointer
> to CHAR. The rationale is on many architectures there is a choice
> between a predicate execution option (i.e cmovcc on x86) or a branch.
>
> On x86 the results for cmovcc vs branch are something along the lines
> of the following:
>
> perc-zero, Br On Result, Time Br / Time cmov
>      0.10,            1,              ,0.983
>      0.10,            0,              ,1.246
>      0.25,            1,              ,1.035
>      0.25,            0,              ,1.49
>      0.33,            1,              ,1.016
>      0.33,            0,              ,1.579
>      0.50,            1,              ,1.228
>      0.50,            0,              ,1.739
>      0.66,            1,              ,1.039
>      0.66,            0,              ,1.764
>      0.75,            1,              ,0.996
>      0.75,            0,              ,1.642
>      0.90,            1,              ,1.071
>      0.90,            0,              ,1.409
>      1.00,            1,              ,0.937
>      1.00,            0,              ,0.999
> ---
>  benchtests/bench-strchr.c | 143 ++++++++++++++++++++++++++++++++++++++
>  1 file changed, 143 insertions(+)
>
> diff --git a/benchtests/bench-strchr.c b/benchtests/bench-strchr.c
> index 203900d4ad..54640bde7e 100644
> --- a/benchtests/bench-strchr.c
> +++ b/benchtests/bench-strchr.c
> @@ -53,6 +53,11 @@
>  # define SMALL_CHAR 851
>  #endif /* WIDE */
>
> +#ifdef USE_FOR_STRCHRNUL
> +# define DO_RAND_TEST(...)
> +#else
> +# define DO_RAND_TEST(...) do_rand_test(__VA_ARGS__)
> +#endif
>  #ifdef USE_FOR_STRCHRNUL
>  # define NULLRET(endptr) endptr
>  #else
> @@ -74,6 +79,133 @@ simple_STRCHR (const CHAR *s, int c)
>  IMPL (simple_STRCHR, 0)
>  IMPL (STRCHR, 1)
>
> +#ifndef USE_FOR_STRCHRNUL
> +/* Random benchmarks for strchr (if return is CHAR or NULL).  The
> +   rational for the benchmark is returning null/char can be done with
> +   predicate execution (i.e cmovcc on x86) or a branch. */
> +
> +
> +/* Large enough that full history can't be stored in BHT. */
> +#define NUM_SEARCH_CHARS 2048
> +
> +/* Expectation is usecases of strchr check the return. Otherwise
> +   strchrnul would almost always be better. Since there is another
> +   branch coming we want to test the case where a potential branch in
> +   strchr can be used to skip a later mispredict because of the
> +   relationship between the two branches. */
> +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)
> +{
> +  size_t i, iters = INNER_LOOP_ITERS_LARGE;
> +  int must_execute = 0;
> +  timing_t start, stop, cur;
> +  TIMING_NOW (start);
> +  for (i = 0; i < iters; ++i)
> +    {
> +      if (CALL (impl, s, c[i % NUM_SEARCH_CHARS]))
> +        {
> +          /* We just need something that will force compiler to emit
> +             a branch instead of conditional execution. */
> +          ++must_execute;
> +          asm volatile("" : : :);
> +        }
> +    }
> +  TIMING_NOW (stop);
> +
> +  TIMING_DIFF (cur, start, stop);
> +
> +  json_element_double (json_ctx, (double)cur / (double)iters);
> +}
> +
> +static void __attribute__ ((noinline, noclone))
> +do_one_rand_test (json_ctx_t *json_ctx, impl_t *impl, const CHAR *s,
> +                  const CHAR *c)
> +{
> +  size_t i, iters = INNER_LOOP_ITERS_LARGE;
> +  timing_t start, stop, cur;
> +  TIMING_NOW (start);
> +  for (i = 0; i < iters; ++i)
> +    {
> +      CALL (impl, s, c[i % NUM_SEARCH_CHARS]);
> +    }
> +  TIMING_NOW (stop);
> +
> +  TIMING_DIFF (cur, start, stop);
> +
> +  json_element_double (json_ctx, (double)cur / (double)iters);
> +}
> +
> +static void
> +do_rand_test (json_ctx_t *json_ctx, size_t align, size_t pos, size_t len,
> +              float perc_zero)
> +{
> +  size_t i;
> +  int perc_zero_int;
> +  CHAR *buf = (CHAR *)buf1;
> +  CHAR *c = (CHAR *)buf2;
> +  align &= 127;
> +  if ((align + len) * sizeof (CHAR) >= page_size)
> +    return;
> +
> +  /* Test is only interesting if we can hit both cases. */
> +  if (pos >= len)
> +    return;
> +
> +  /* Segfault if we run the test. */
> +  if (NUM_SEARCH_CHARS * sizeof (CHAR) > page_size)
> +    return;
> +
> +  for (i = 0; i < len; ++i)
> +    {
> +      buf[align + i] = 2;
> +    }
> +  buf[align + len] = 0;
> +  buf[align + pos] = 1;
> +
> +  perc_zero_int = perc_zero * RAND_MAX;
> +  for (i = 0; i < NUM_SEARCH_CHARS; ++i)
> +    {
> +      if (rand () > perc_zero_int)
> +        c[i] = 0;
> +      else
> +        c[i] = 1;
> +    }
> +  {
> +    json_element_object_begin (json_ctx);
> +    json_attr_uint (json_ctx, "rand", 1);
> +    json_attr_uint (json_ctx, "branch", 1);
> +    json_attr_double (json_ctx, "perc-zero", perc_zero);
> +    json_attr_uint (json_ctx, "length", len);
> +    json_attr_uint (json_ctx, "pos", pos);
> +    json_attr_uint (json_ctx, "alignment", align);
> +    json_array_begin (json_ctx, "timings");
> +
> +    FOR_EACH_IMPL (impl, 0)
> +      do_one_rand_plus_branch_test (json_ctx, impl, buf + align, c);
> +
> +    json_array_end (json_ctx);
> +    json_element_object_end (json_ctx);
> +  }
> +  {
> +    json_element_object_begin (json_ctx);
> +    json_attr_uint (json_ctx, "rand", 1);
> +    json_attr_uint (json_ctx, "branch", 0);
> +    json_attr_double (json_ctx, "perc-zero", perc_zero);
> +    json_attr_uint (json_ctx, "length", len);
> +    json_attr_uint (json_ctx, "pos", pos);
> +    json_attr_uint (json_ctx, "alignment", align);
> +    json_array_begin (json_ctx, "timings");
> +
> +    FOR_EACH_IMPL (impl, 0)
> +      do_one_rand_test (json_ctx, impl, buf + align, c);
> +
> +    json_array_end (json_ctx);
> +    json_element_object_end (json_ctx);
> +  }
> +}
> +#endif
> +
>  static void
>  do_one_test (json_ctx_t *json_ctx, impl_t *impl, const CHAR *s, int c,
>               const CHAR *exp_res)
> @@ -136,6 +268,7 @@ do_test (json_ctx_t *json_ctx, size_t align, size_t pos, size_t len,
>      result = NULLRET (buf + align + len);
>
>    json_element_object_begin (json_ctx);
> +  json_attr_uint (json_ctx, "rand", 0);
>    json_attr_uint (json_ctx, "length", len);
>    json_attr_uint (json_ctx, "pos", pos);
>    json_attr_uint (json_ctx, "seek_char", seek_char);
> @@ -234,6 +367,16 @@ test_main (void)
>        do_test (&json_ctx, 0, i, i + 1, 0, BIG_CHAR);
>      }
>
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.0);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.1);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.25);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.33);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.5);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.66);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.75);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 0.9);
> +  DO_RAND_TEST(&json_ctx, 0, 15, 16, 1.0);
> +
>    json_array_end (&json_ctx);
>    json_attr_object_end (&json_ctx);
>    json_attr_object_end (&json_ctx);
> --
> 2.25.1
>

LGTM.

Reviewed-by: H.J. Lu <hjl.tools@gmail.com>

Thanks.

-- 
H.J.