Message ID | 20240903063056.2724742-2-visitorckw@gmail.com |
---|---|
State | New |
Headers | show |
Series | Optimization and benchmarking of bsearch() | expand |
On Mon, Sep 2, 2024 at 11:31 PM 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", > "results": [121.887] > } > } > } > > Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> > --- > Changes in v3: > - Sort the stdlib-benchset entries in Makefile to resolve CI failures. > > benchtests/Makefile | 1 + > benchtests/bench-bsearch.c | 110 +++++++++++++++++++++++++++++++++++++ > 2 files changed, 111 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..9ec88af60a > --- /dev/null > +++ b/benchtests/bench-bsearch.c > @@ -0,0 +1,110 @@ > +/* 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); > + } Can you add some additional context to the json output? 1) arr size 2) A short description of the key pattern, in this case maybe "ascending". 3) A field like "contained" to indicate whether you are testing keys that are contained in the arr or not. > + > + 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_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 >
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..9ec88af60a --- /dev/null +++ b/benchtests/bench-bsearch.c @@ -0,0 +1,110 @@ +/* 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_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>
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", "results": [121.887] } } } Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com> --- Changes in v3: - Sort the stdlib-benchset entries in Makefile to resolve CI failures. benchtests/Makefile | 1 + benchtests/bench-bsearch.c | 110 +++++++++++++++++++++++++++++++++++++ 2 files changed, 111 insertions(+) create mode 100644 benchtests/bench-bsearch.c