[v4,1/2] benchtests: Add benchmark test for bsearch

  Introduce a benchmark test for the bsearch function to evaluate its
performance.

Example bench-bsearch.out:
{
 "timing_type": "hp_timing",
 "functions": {
  "bsearch": {
   "bench-variant": "default",
   "array-size": 100000,
   "key-pattern": "ascending",
   "contained": "yes",
   "results": [121.735]
  }
 }
}

Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
Changes in v4:
- Add three fields: "array-size," "key-pattern," and "contained" to
  benchmark json output.
- Update the benchmark result format in commit messages.

 benchtests/Makefile        |   1 +
 benchtests/bench-bsearch.c | 114 +++++++++++++++++++++++++++++++++++++
 2 files changed, 115 insertions(+)
 create mode 100644 benchtests/bench-bsearch.c
  

On Wed, Sep 4, 2024 at 9:02 AM Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
>
> Introduce a benchmark test for the bsearch function to evaluate its
> performance.
>
> Example bench-bsearch.out:
> {
>  "timing_type": "hp_timing",
>  "functions": {
>   "bsearch": {
>    "bench-variant": "default",
>    "array-size": 100000,
>    "key-pattern": "ascending",
>    "contained": "yes",
>    "results": [121.735]
>   }
>  }
> }
>
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> Changes in v4:
> - Add three fields: "array-size," "key-pattern," and "contained" to
>   benchmark json output.
> - Update the benchmark result format in commit messages.
>
>  benchtests/Makefile        |   1 +
>  benchtests/bench-bsearch.c | 114 +++++++++++++++++++++++++++++++++++++
>  2 files changed, 115 insertions(+)
>  create mode 100644 benchtests/bench-bsearch.c
>
> diff --git a/benchtests/Makefile b/benchtests/Makefile
> index d228e9e68a..955b766756 100644
> --- a/benchtests/Makefile
> +++ b/benchtests/Makefile
> @@ -253,6 +253,7 @@ hash-benchset := \
>
>  stdlib-benchset := \
>    arc4random \
> +  bsearch \
>    random-lock \
>    strtod \
>    # stdlib-benchset
> diff --git a/benchtests/bench-bsearch.c b/benchtests/bench-bsearch.c
> new file mode 100644
> index 0000000000..75bf812290
> --- /dev/null
> +++ b/benchtests/bench-bsearch.c
> @@ -0,0 +1,114 @@
> +/* Measure bsearch functions.
> +   Copyright (C) 2022-2024 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library; if not, see
> +   <https://www.gnu.org/licenses/>.  */
> +
> +#define TEST_MAIN
> +#define TEST_NAME "bsearch"
> +
> +#define ARRAY_SIZE 100000
> +#define LOOP_ITERS 100000000
> +
> +/* Directly including <stdlib.h> leads to the use of an inline version
> +   of bsearch(), which may cause our test cases to be optimized away by
> +   the compiler due to predictability. To address this, we should
> +   include <bits/stdlib-bsearch.h> directly and replace __extern_inline
> +   with __attribute__((noinline)) to ensure the compiler does not
> +   inline the function. Additionally, we need to add some macros
> +   required for compilation. */
> +#include <stddef.h>
> +#define __extern_inline __attribute__((noinline))
> +#define __GNUC_PREREQ(x, y) 0
> +typedef int (*__compar_fn_t) (const void *, const void *);
> +#include <bits/stdlib-bsearch.h>
> +#undef __extern_inline
> +#undef __GNUC_PREREQ
> +
> +#include "json-lib.h"
> +#include "bench-timing.h"
> +
> +int arr[ARRAY_SIZE];
> +
> +static int
> +comp (const void *p1, const void *p2)
> +{
> +  int x1 = *(int *) p1;
> +  int x2 = *(int *) p2;
> +
> +  if (x1 < x2)
> +    return -1;
> +  if (x1 > x2)
> +    return 1;
> +  return 0;
> +}
> +
> +static void
> +do_bench (json_ctx_t *json_ctx)
> +{
> +  size_t i, iters = LOOP_ITERS;
> +  timing_t start, stop, cur;
> +  int key;
> +  volatile __attribute__((__unused__)) void *res;
> +
> +  for (i = 0; i < ARRAY_SIZE; ++i)
> +    {
> +      arr[i] = i;
> +    }
> +
> +  TIMING_NOW (start);
> +
> +  for (i = 0; i < iters; ++i)
> +    {
> +      key = i % ARRAY_SIZE;
> +      res = bsearch(&key, arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), comp);
> +    }
> +
> +  TIMING_NOW (stop);
> +
> +  TIMING_DIFF (cur, start, stop);
> +
> +  json_element_double (json_ctx, (double) cur / (double) iters);
> +}
> +
> +int
> +do_test (void)
> +{
> +  json_ctx_t json_ctx;
> +
> +  json_init (&json_ctx, 0, stdout);
> +
> +  json_document_begin (&json_ctx);
> +  json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
> +  json_attr_object_begin (&json_ctx, "functions");
> +  json_attr_object_begin (&json_ctx, TEST_NAME);
> +  json_attr_string (&json_ctx, "bench-variant", "default");
> +  json_attr_uint (&json_ctx, "array-size", ARRAY_SIZE);
> +  json_attr_string (&json_ctx, "key-pattern", "ascending");
> +  json_attr_string (&json_ctx, "contained", "yes");
> +
Can you have `do_bench` fill this info in? (For example
`bench-strlen.c::do_test`).
Makes it easier to parameterize/extend.

Also can you add a field for `nmemb` and another for the compare i.e a bool
field call 'simple' (we may want to add a benchmark w/ a heavy compare).

> +  json_array_begin (&json_ctx, "results");
> +
> +  do_bench(&json_ctx);
> +
> +  json_array_end (&json_ctx);
> +  json_attr_object_end (&json_ctx);
> +  json_attr_object_end (&json_ctx);
> +  json_document_end (&json_ctx);
> +
> +  return 0;
> +}
> +
> +#include <support/test-driver.c>
> --
> 2.34.1
>
  

On Wed, Sep 4, 2024 at 11:20 AM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> On Wed, Sep 4, 2024 at 9:02 AM Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
> >
> > Introduce a benchmark test for the bsearch function to evaluate its
> > performance.
> >
> > Example bench-bsearch.out:
> > {
> >  "timing_type": "hp_timing",
> >  "functions": {
> >   "bsearch": {
> >    "bench-variant": "default",
> >    "array-size": 100000,
> >    "key-pattern": "ascending",
> >    "contained": "yes",
> >    "results": [121.735]
> >   }
> >  }
> > }
> >
> > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> > ---
> > Changes in v4:
> > - Add three fields: "array-size," "key-pattern," and "contained" to
> >   benchmark json output.
> > - Update the benchmark result format in commit messages.
> >
> >  benchtests/Makefile        |   1 +
> >  benchtests/bench-bsearch.c | 114 +++++++++++++++++++++++++++++++++++++
> >  2 files changed, 115 insertions(+)
> >  create mode 100644 benchtests/bench-bsearch.c
> >
> > diff --git a/benchtests/Makefile b/benchtests/Makefile
> > index d228e9e68a..955b766756 100644
> > --- a/benchtests/Makefile
> > +++ b/benchtests/Makefile
> > @@ -253,6 +253,7 @@ hash-benchset := \
> >
> >  stdlib-benchset := \
> >    arc4random \
> > +  bsearch \
> >    random-lock \
> >    strtod \
> >    # stdlib-benchset
> > diff --git a/benchtests/bench-bsearch.c b/benchtests/bench-bsearch.c
> > new file mode 100644
> > index 0000000000..75bf812290
> > --- /dev/null
> > +++ b/benchtests/bench-bsearch.c
> > @@ -0,0 +1,114 @@
> > +/* Measure bsearch functions.
> > +   Copyright (C) 2022-2024 Free Software Foundation, Inc.
> > +   This file is part of the GNU C Library.
> > +
> > +   The GNU C Library is free software; you can redistribute it and/or
> > +   modify it under the terms of the GNU Lesser General Public
> > +   License as published by the Free Software Foundation; either
> > +   version 2.1 of the License, or (at your option) any later version.
> > +
> > +   The GNU C Library is distributed in the hope that it will be useful,
> > +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> > +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> > +   Lesser General Public License for more details.
> > +
> > +   You should have received a copy of the GNU Lesser General Public
> > +   License along with the GNU C Library; if not, see
> > +   <https://www.gnu.org/licenses/>.  */
> > +
> > +#define TEST_MAIN
> > +#define TEST_NAME "bsearch"
> > +
> > +#define ARRAY_SIZE 100000
> > +#define LOOP_ITERS 100000000
> > +
> > +/* Directly including <stdlib.h> leads to the use of an inline version
> > +   of bsearch(), which may cause our test cases to be optimized away by
> > +   the compiler due to predictability. To address this, we should
> > +   include <bits/stdlib-bsearch.h> directly and replace __extern_inline
> > +   with __attribute__((noinline)) to ensure the compiler does not
> > +   inline the function. Additionally, we need to add some macros
> > +   required for compilation. */
> > +#include <stddef.h>
> > +#define __extern_inline __attribute__((noinline))
> > +#define __GNUC_PREREQ(x, y) 0
> > +typedef int (*__compar_fn_t) (const void *, const void *);
> > +#include <bits/stdlib-bsearch.h>
> > +#undef __extern_inline
> > +#undef __GNUC_PREREQ
> > +
> > +#include "json-lib.h"
> > +#include "bench-timing.h"
> > +
> > +int arr[ARRAY_SIZE];
> > +
> > +static int
> > +comp (const void *p1, const void *p2)
> > +{
> > +  int x1 = *(int *) p1;
> > +  int x2 = *(int *) p2;
> > +
> > +  if (x1 < x2)
> > +    return -1;
> > +  if (x1 > x2)
> > +    return 1;
> > +  return 0;
> > +}
> > +
> > +static void
> > +do_bench (json_ctx_t *json_ctx)
> > +{
> > +  size_t i, iters = LOOP_ITERS;
> > +  timing_t start, stop, cur;
> > +  int key;
> > +  volatile __attribute__((__unused__)) void *res;
> > +
> > +  for (i = 0; i < ARRAY_SIZE; ++i)
> > +    {
> > +      arr[i] = i;
> > +    }
> > +
> > +  TIMING_NOW (start);
> > +
> > +  for (i = 0; i < iters; ++i)
> > +    {
> > +      key = i % ARRAY_SIZE;
> > +      res = bsearch(&key, arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), comp);
> > +    }
> > +
> > +  TIMING_NOW (stop);
> > +
> > +  TIMING_DIFF (cur, start, stop);
> > +
> > +  json_element_double (json_ctx, (double) cur / (double) iters);
> > +}
> > +
> > +int
> > +do_test (void)
> > +{
> > +  json_ctx_t json_ctx;
> > +
> > +  json_init (&json_ctx, 0, stdout);
> > +
> > +  json_document_begin (&json_ctx);
> > +  json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
> > +  json_attr_object_begin (&json_ctx, "functions");
> > +  json_attr_object_begin (&json_ctx, TEST_NAME);
> > +  json_attr_string (&json_ctx, "bench-variant", "default");
> > +  json_attr_uint (&json_ctx, "array-size", ARRAY_SIZE);
> > +  json_attr_string (&json_ctx, "key-pattern", "ascending");
> > +  json_attr_string (&json_ctx, "contained", "yes");
> > +
> Can you have `do_bench` fill this info in? (For example
> `bench-strlen.c::do_test`).
> Makes it easier to parameterize/extend.
>
> Also can you add a field for `nmemb` and another for the compare i.e a bool
> field call 'simple' (we may want to add a benchmark w/ a heavy compare).

Can you also put all the benchmark data in an array:
`json_array_begin (&json_ctx, "results");`

and each config in its own object.
>
> > +  json_array_begin (&json_ctx, "results");
> > +
> > +  do_bench(&json_ctx);
> > +
> > +  json_array_end (&json_ctx);
> > +  json_attr_object_end (&json_ctx);
> > +  json_attr_object_end (&json_ctx);
> > +  json_document_end (&json_ctx);
> > +
> > +  return 0;
> > +}
> > +
> > +#include <support/test-driver.c>
> > --
> > 2.34.1
> >