From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pj1-x1034.google.com (mail-pj1-x1034.google.com [IPv6:2607:f8b0:4864:20::1034]) by sourceware.org (Postfix) with ESMTPS id 89F933858D3C for ; Thu, 24 Mar 2022 18:44:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 89F933858D3C Received: by mail-pj1-x1034.google.com with SMTP id m22so5495177pja.0 for ; Thu, 24 Mar 2022 11:44:52 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=KKN3olMNw7hnddAsar5C0PIfNqoDA0rkZZQcaZkYzPg=; b=D9ic/f1WevoQ8oSNB0xIQtFWWNolMAc80YFji1Pdrx3hmNhMkSbaWh8FMf3nyhVsqO swQXY+b5DzWDh31N35MA3w6A2w0zVll0b8JNhlhllUqMfBkgqIcASuEeb3rjZ+XuNKKh iaI1GVeM6oo1T8gurVIB7N/lYTqnfJT5BRoqU0rmnYnJaDGJ8GTE7rpLTArMwwRoN8HX szMLLo4o05Nu4ZmgoMv5oeYlo8cxbyKGf0zLz6BOJwJrt0G5wzpgE62yIoxGOiHeswQB Djmc/5V1SxvaDprdW+UNbqST292cDSzWzLW1NQ3ls6Y2S54tzrSDj/UXerifuwfbte9W o58A== X-Gm-Message-State: AOAM530s+LffwCD8kEOV/sV69IBPhWs0NwR0zMr4XrxvuWpN6vE0e7vf IhfKEdTLD958cPp0MjtWSwm5voQv9shawmYWtSWj/zsaDqs= X-Google-Smtp-Source: ABdhPJyD54xEzRblpvMzwHUQwzN7yeyvjEJpf4VvTC/AGNvIFij3dgb3hKY+IinABrPfkFCVsZxD2CliqDrCMPEBrzw= X-Received: by 2002:a17:902:f690:b0:154:2ceb:f18a with SMTP id l16-20020a170902f69000b001542cebf18amr7374062plg.4.1648147491421; Thu, 24 Mar 2022 11:44:51 -0700 (PDT) MIME-Version: 1.0 References: <20220323215734.3927131-1-goldstein.w.n@gmail.com> <20220323215734.3927131-2-goldstein.w.n@gmail.com> In-Reply-To: <20220323215734.3927131-2-goldstein.w.n@gmail.com> From: "H.J. Lu" Date: Thu, 24 Mar 2022 11:44:15 -0700 Message-ID: Subject: Re: [PATCH v1 02/23] benchtests: Add random benchmark in bench-strchr.c To: Noah Goldstein Cc: GNU C Library , "Carlos O'Donell" Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-3026.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Mar 2022 18:44:54 -0000 On Wed, Mar 23, 2022 at 2:58 PM Noah Goldstein 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 Thanks. -- H.J.