From a6a738c1cc3b754f1bccc0cefc3aeb551c341f88 Mon Sep 17 00:00:00 2001 From: haih-g Date: Thu, 20 May 2021 12:09:16 -0400 Subject: Implementation of random interleaving. (#1105) * Implementation of random interleaving. See http://github.com/google/benchmark/issues/1051 for the feature requests. Committer: Hai Huang (http://github.com/haih-g) On branch fr-1051 Changes to be committed: modified: include/benchmark/benchmark.h modified: src/benchmark.cc new file: src/benchmark_adjust_repetitions.cc new file: src/benchmark_adjust_repetitions.h modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h modified: src/benchmark_register.cc modified: src/benchmark_runner.cc modified: src/benchmark_runner.h modified: test/CMakeLists.txt new file: test/benchmark_random_interleaving_gtest.cc * Fix benchmark_random_interleaving_gtest.cc for fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc modified: src/benchmark_runner.cc modified: test/benchmark_random_interleaving_gtest.cc * Fix macos build for fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h modified: src/benchmark_runner.cc * Fix macos and windows build for fr-1051. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_runner.cc * Fix benchmark_random_interleaving_test.cc for macos and windows in fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: test/benchmark_random_interleaving_gtest.cc * Fix int type benchmark_random_interleaving_gtest for macos in fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: test/benchmark_random_interleaving_gtest.cc * Address dominichamon's comments 03/29 for fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h modified: test/benchmark_random_interleaving_gtest.cc * Address dominichamon's comment on default min_time / repetitions for fr-1051. Also change sentinel of random_interleaving_repetitions to -1. Hopefully it fixes the failures on Windows. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h * Fix windows test failures for fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_api_internal.cc modified: src/benchmark_runner.cc * Add license blurb for fr-1051. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_adjust_repetitions.cc modified: src/benchmark_adjust_repetitions.h * Switch to std::shuffle() for fr-1105. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc * Change to 1e-9 in fr-1105 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_adjust_repetitions.cc * Fix broken build caused by bad merge for fr-1105. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_api_internal.cc modified: src/benchmark_runner.cc * Fix build breakage for fr-1051. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h modified: src/benchmark_register.cc modified: src/benchmark_runner.cc * Print out reports as they come in if random interleaving is disabled (fr-1051) Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc * size_t, int64_t --> int in benchmark_runner for fr-1051. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_runner.cc modified: src/benchmark_runner.h * Address comments from dominichamon for fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc modified: src/benchmark_adjust_repetitions.cc modified: src/benchmark_adjust_repetitions.h modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h modified: test/benchmark_random_interleaving_gtest.cc * benchmar_indices --> size_t to make CI pass: fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark.cc * Fix min_time not initialized issue for fr-1051. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h * min_time --> MinTime in fr-1051. Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: src/benchmark_api_internal.cc modified: src/benchmark_api_internal.h modified: src/benchmark_runner.cc * Add doc for random interleaving for fr-1051 Committer: Hai Huang On branch fr-1051 Your branch is up to date with 'origin/fr-1051'. Changes to be committed: modified: README.md new file: docs/random_interleaving.md Co-authored-by: Dominic Hamon --- test/benchmark_random_interleaving_gtest.cc | 271 ++++++++++++++++++++++++++++ 1 file changed, 271 insertions(+) create mode 100644 test/benchmark_random_interleaving_gtest.cc (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc new file mode 100644 index 0000000..5e8329a --- /dev/null +++ b/test/benchmark_random_interleaving_gtest.cc @@ -0,0 +1,271 @@ +#include +#include +#include + +#include "../src/benchmark_adjust_repetitions.h" +#include "../src/string_util.h" +#include "benchmark/benchmark.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +DECLARE_bool(benchmark_enable_random_interleaving); +DECLARE_string(benchmark_filter); +DECLARE_double(benchmark_random_interleaving_max_overhead); + +namespace do_not_read_flag_directly { +DECLARE_int32(benchmark_repetitions); +} // namespace do_not_read_flag_directly + +namespace benchmark { +namespace internal { +namespace { + +class EventQueue : public std::queue { + public: + void Put(const std::string& event) { + push(event); + } + + void Clear() { + while (!empty()) { + pop(); + } + } + + std::string Get() { + std::string event = front(); + pop(); + return event; + } +}; + +static EventQueue* queue = new EventQueue; + +class NullReporter : public BenchmarkReporter { + public: + bool ReportContext(const Context& /*context*/) override { + return true; + } + void ReportRuns(const std::vector& /* report */) override {} +}; + +class BenchmarkTest : public testing::Test { + public: + static void SetupHook(int /* num_threads */) { queue->push("Setup"); } + + static void TeardownHook(int /* num_threads */) { queue->push("Teardown"); } + + void Execute(const std::string& pattern) { + queue->Clear(); + + BenchmarkReporter* reporter = new NullReporter; + FLAGS_benchmark_filter = pattern; + RunSpecifiedBenchmarks(reporter); + delete reporter; + + queue->Put("DONE"); // End marker + } +}; + +static void BM_Match1(benchmark::State& state) { + const int64_t arg = state.range(0); + + for (auto _ : state) {} + queue->Put(StrFormat("BM_Match1/%d", static_cast(arg))); +} +BENCHMARK(BM_Match1) + ->Iterations(100) + ->Arg(1) + ->Arg(2) + ->Arg(3) + ->Range(10, 80) + ->Args({90}) + ->Args({100}); + +static void BM_MatchOverhead(benchmark::State& state) { + const int64_t arg = state.range(0); + + for (auto _ : state) {} + queue->Put(StrFormat("BM_MatchOverhead/%d", static_cast(arg))); +} +BENCHMARK(BM_MatchOverhead) + ->Iterations(100) + ->Arg(64) + ->Arg(80); + +TEST_F(BenchmarkTest, Match1) { + Execute("BM_Match1"); + ASSERT_EQ("BM_Match1/1", queue->Get()); + ASSERT_EQ("BM_Match1/2", queue->Get()); + ASSERT_EQ("BM_Match1/3", queue->Get()); + ASSERT_EQ("BM_Match1/10", queue->Get()); + ASSERT_EQ("BM_Match1/64", queue->Get()); + ASSERT_EQ("BM_Match1/80", queue->Get()); + ASSERT_EQ("BM_Match1/90", queue->Get()); + ASSERT_EQ("BM_Match1/100", queue->Get()); + ASSERT_EQ("DONE", queue->Get()); +} + +TEST_F(BenchmarkTest, Match1WithRepetition) { + do_not_read_flag_directly::FLAGS_benchmark_repetitions = 2; + + Execute("BM_Match1/(64|80)"); + ASSERT_EQ("BM_Match1/64", queue->Get()); + ASSERT_EQ("BM_Match1/64", queue->Get()); + ASSERT_EQ("BM_Match1/80", queue->Get()); + ASSERT_EQ("BM_Match1/80", queue->Get()); + ASSERT_EQ("DONE", queue->Get()); +} + +TEST_F(BenchmarkTest, Match1WithRandomInterleaving) { + FLAGS_benchmark_enable_random_interleaving = true; + do_not_read_flag_directly::FLAGS_benchmark_repetitions = 100; + FLAGS_benchmark_random_interleaving_max_overhead = + std::numeric_limits::infinity(); + + std::vector expected({"BM_Match1/64", "BM_Match1/80"}); + std::map interleaving_count; + Execute("BM_Match1/(64|80)"); + for (int i = 0; i < 100; ++i) { + std::vector interleaving; + interleaving.push_back(queue->Get()); + interleaving.push_back(queue->Get()); + EXPECT_THAT(interleaving, testing::UnorderedElementsAreArray(expected)); + interleaving_count[StrFormat("%s,%s", interleaving[0].c_str(), + interleaving[1].c_str())]++; + } + EXPECT_GE(interleaving_count.size(), 2) << "Interleaving was not randomized."; + ASSERT_EQ("DONE", queue->Get()); +} + +TEST_F(BenchmarkTest, Match1WithRandomInterleavingAndZeroOverhead) { + FLAGS_benchmark_enable_random_interleaving = true; + do_not_read_flag_directly::FLAGS_benchmark_repetitions = 100; + FLAGS_benchmark_random_interleaving_max_overhead = 0; + + // ComputeRandomInterleavingRepetitions() will kick in and rerun each + // benchmark once with increased iterations. Then number of repetitions will + // be reduced to < 100. The first 4 executions should be + // 2 x BM_MatchOverhead/64 and 2 x BM_MatchOverhead/80. + std::vector expected( + {"BM_MatchOverhead/64", "BM_MatchOverhead/80", "BM_MatchOverhead/64", + "BM_MatchOverhead/80"}); + std::map interleaving_count; + Execute("BM_MatchOverhead/(64|80)"); + std::vector interleaving; + interleaving.push_back(queue->Get()); + interleaving.push_back(queue->Get()); + interleaving.push_back(queue->Get()); + interleaving.push_back(queue->Get()); + EXPECT_THAT(interleaving, testing::UnorderedElementsAreArray(expected)); + ASSERT_LT(queue->size(), 100) << "# Repetitions was not reduced to < 100."; +} + +InternalRandomInterleavingRepetitionsInput CreateInput( + double total, double time, double real_time, double min_time, + double overhead, int repetitions) { + InternalRandomInterleavingRepetitionsInput input; + input.total_execution_time_per_repetition = total; + input.time_used_per_repetition = time; + input.real_time_used_per_repetition = real_time; + input.min_time_per_repetition = min_time; + input.max_overhead = overhead; + input.max_repetitions = repetitions; + return input; +} + +TEST(Benchmark, ComputeRandomInterleavingRepetitions) { + // On wall clock time. + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.05, 0.05, 0.05, 0.05, 0.0, 10)), + 10); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.05, 0.05, 0.05, 0.05, 0.4, 10)), + 10); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.06, 0.05, 0.05, 0.05, 0.0, 10)), + 8); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.06, 0.05, 0.05, 0.05, 0.4, 10)), + 10); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.08, 0.05, 0.05, 0.05, 0.0, 10)), + 6); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.08, 0.05, 0.05, 0.05, 0.4, 10)), + 9); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.26, 0.25, 0.25, 0.05, 0.0, 10)), + 2); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.25, 0.25, 0.25, 0.05, 0.4, 10)), + 3); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.26, 0.25, 0.25, 0.05, 0.0, 10)), + 2); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.26, 0.25, 0.25, 0.05, 0.4, 10)), + 3); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.38, 0.25, 0.25, 0.05, 0.0, 10)), + 2); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.38, 0.25, 0.25, 0.05, 0.4, 10)), + 3); + + // On CPU time. + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.1, 0.05, 0.1, 0.05, 0.0, 10)), + 10); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.1, 0.05, 0.1, 0.05, 0.4, 10)), + 10); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.11, 0.05, 0.1, 0.05, 0.0, 10)), + 9); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.11, 0.05, 0.1, 0.05, 0.4, 10)), + 10); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.15, 0.05, 0.1, 0.05, 0.0, 10)), + 7); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.15, 0.05, 0.1, 0.05, 0.4, 10)), + 9); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.5, 0.25, 0.5, 0.05, 0.0, 10)), + 2); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.5, 0.25, 0.5, 0.05, 0.4, 10)), + 3); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.51, 0.25, 0.5, 0.05, 0.0, 10)), + 2); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.51, 0.25, 0.5, 0.05, 0.4, 10)), + 3); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.8, 0.25, 0.5, 0.05, 0.0, 10)), + 2); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.8, 0.25, 0.5, 0.05, 0.4, 10)), + 2); + + // Corner cases. + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.0, 0.25, 0.5, 0.05, 0.4, 10)), + 3); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.8, 0.0, 0.5, 0.05, 0.4, 10)), + 9); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.8, 0.25, 0.0, 0.05, 0.4, 10)), + 1); + EXPECT_EQ(ComputeRandomInterleavingRepetitions( + CreateInput(0.8, 0.25, 0.5, 0.0, 0.4, 10)), + 1); +} + +} // namespace +} // namespace internal +} // namespace benchmark -- cgit v1.2.3 From e025dd5a54d8cefda429964ad3d2c7f4994ed38e Mon Sep 17 00:00:00 2001 From: Dominic Hamon Date: Tue, 1 Jun 2021 16:05:50 +0100 Subject: Revert "Implementation of random interleaving. (#1105)" (#1161) This reverts commit a6a738c1cc3b754f1bccc0cefc3aeb551c341f88. --- test/benchmark_random_interleaving_gtest.cc | 271 ---------------------------- 1 file changed, 271 deletions(-) delete mode 100644 test/benchmark_random_interleaving_gtest.cc (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc deleted file mode 100644 index 5e8329a..0000000 --- a/test/benchmark_random_interleaving_gtest.cc +++ /dev/null @@ -1,271 +0,0 @@ -#include -#include -#include - -#include "../src/benchmark_adjust_repetitions.h" -#include "../src/string_util.h" -#include "benchmark/benchmark.h" -#include "gmock/gmock.h" -#include "gtest/gtest.h" - -DECLARE_bool(benchmark_enable_random_interleaving); -DECLARE_string(benchmark_filter); -DECLARE_double(benchmark_random_interleaving_max_overhead); - -namespace do_not_read_flag_directly { -DECLARE_int32(benchmark_repetitions); -} // namespace do_not_read_flag_directly - -namespace benchmark { -namespace internal { -namespace { - -class EventQueue : public std::queue { - public: - void Put(const std::string& event) { - push(event); - } - - void Clear() { - while (!empty()) { - pop(); - } - } - - std::string Get() { - std::string event = front(); - pop(); - return event; - } -}; - -static EventQueue* queue = new EventQueue; - -class NullReporter : public BenchmarkReporter { - public: - bool ReportContext(const Context& /*context*/) override { - return true; - } - void ReportRuns(const std::vector& /* report */) override {} -}; - -class BenchmarkTest : public testing::Test { - public: - static void SetupHook(int /* num_threads */) { queue->push("Setup"); } - - static void TeardownHook(int /* num_threads */) { queue->push("Teardown"); } - - void Execute(const std::string& pattern) { - queue->Clear(); - - BenchmarkReporter* reporter = new NullReporter; - FLAGS_benchmark_filter = pattern; - RunSpecifiedBenchmarks(reporter); - delete reporter; - - queue->Put("DONE"); // End marker - } -}; - -static void BM_Match1(benchmark::State& state) { - const int64_t arg = state.range(0); - - for (auto _ : state) {} - queue->Put(StrFormat("BM_Match1/%d", static_cast(arg))); -} -BENCHMARK(BM_Match1) - ->Iterations(100) - ->Arg(1) - ->Arg(2) - ->Arg(3) - ->Range(10, 80) - ->Args({90}) - ->Args({100}); - -static void BM_MatchOverhead(benchmark::State& state) { - const int64_t arg = state.range(0); - - for (auto _ : state) {} - queue->Put(StrFormat("BM_MatchOverhead/%d", static_cast(arg))); -} -BENCHMARK(BM_MatchOverhead) - ->Iterations(100) - ->Arg(64) - ->Arg(80); - -TEST_F(BenchmarkTest, Match1) { - Execute("BM_Match1"); - ASSERT_EQ("BM_Match1/1", queue->Get()); - ASSERT_EQ("BM_Match1/2", queue->Get()); - ASSERT_EQ("BM_Match1/3", queue->Get()); - ASSERT_EQ("BM_Match1/10", queue->Get()); - ASSERT_EQ("BM_Match1/64", queue->Get()); - ASSERT_EQ("BM_Match1/80", queue->Get()); - ASSERT_EQ("BM_Match1/90", queue->Get()); - ASSERT_EQ("BM_Match1/100", queue->Get()); - ASSERT_EQ("DONE", queue->Get()); -} - -TEST_F(BenchmarkTest, Match1WithRepetition) { - do_not_read_flag_directly::FLAGS_benchmark_repetitions = 2; - - Execute("BM_Match1/(64|80)"); - ASSERT_EQ("BM_Match1/64", queue->Get()); - ASSERT_EQ("BM_Match1/64", queue->Get()); - ASSERT_EQ("BM_Match1/80", queue->Get()); - ASSERT_EQ("BM_Match1/80", queue->Get()); - ASSERT_EQ("DONE", queue->Get()); -} - -TEST_F(BenchmarkTest, Match1WithRandomInterleaving) { - FLAGS_benchmark_enable_random_interleaving = true; - do_not_read_flag_directly::FLAGS_benchmark_repetitions = 100; - FLAGS_benchmark_random_interleaving_max_overhead = - std::numeric_limits::infinity(); - - std::vector expected({"BM_Match1/64", "BM_Match1/80"}); - std::map interleaving_count; - Execute("BM_Match1/(64|80)"); - for (int i = 0; i < 100; ++i) { - std::vector interleaving; - interleaving.push_back(queue->Get()); - interleaving.push_back(queue->Get()); - EXPECT_THAT(interleaving, testing::UnorderedElementsAreArray(expected)); - interleaving_count[StrFormat("%s,%s", interleaving[0].c_str(), - interleaving[1].c_str())]++; - } - EXPECT_GE(interleaving_count.size(), 2) << "Interleaving was not randomized."; - ASSERT_EQ("DONE", queue->Get()); -} - -TEST_F(BenchmarkTest, Match1WithRandomInterleavingAndZeroOverhead) { - FLAGS_benchmark_enable_random_interleaving = true; - do_not_read_flag_directly::FLAGS_benchmark_repetitions = 100; - FLAGS_benchmark_random_interleaving_max_overhead = 0; - - // ComputeRandomInterleavingRepetitions() will kick in and rerun each - // benchmark once with increased iterations. Then number of repetitions will - // be reduced to < 100. The first 4 executions should be - // 2 x BM_MatchOverhead/64 and 2 x BM_MatchOverhead/80. - std::vector expected( - {"BM_MatchOverhead/64", "BM_MatchOverhead/80", "BM_MatchOverhead/64", - "BM_MatchOverhead/80"}); - std::map interleaving_count; - Execute("BM_MatchOverhead/(64|80)"); - std::vector interleaving; - interleaving.push_back(queue->Get()); - interleaving.push_back(queue->Get()); - interleaving.push_back(queue->Get()); - interleaving.push_back(queue->Get()); - EXPECT_THAT(interleaving, testing::UnorderedElementsAreArray(expected)); - ASSERT_LT(queue->size(), 100) << "# Repetitions was not reduced to < 100."; -} - -InternalRandomInterleavingRepetitionsInput CreateInput( - double total, double time, double real_time, double min_time, - double overhead, int repetitions) { - InternalRandomInterleavingRepetitionsInput input; - input.total_execution_time_per_repetition = total; - input.time_used_per_repetition = time; - input.real_time_used_per_repetition = real_time; - input.min_time_per_repetition = min_time; - input.max_overhead = overhead; - input.max_repetitions = repetitions; - return input; -} - -TEST(Benchmark, ComputeRandomInterleavingRepetitions) { - // On wall clock time. - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.05, 0.05, 0.05, 0.05, 0.0, 10)), - 10); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.05, 0.05, 0.05, 0.05, 0.4, 10)), - 10); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.06, 0.05, 0.05, 0.05, 0.0, 10)), - 8); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.06, 0.05, 0.05, 0.05, 0.4, 10)), - 10); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.08, 0.05, 0.05, 0.05, 0.0, 10)), - 6); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.08, 0.05, 0.05, 0.05, 0.4, 10)), - 9); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.26, 0.25, 0.25, 0.05, 0.0, 10)), - 2); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.25, 0.25, 0.25, 0.05, 0.4, 10)), - 3); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.26, 0.25, 0.25, 0.05, 0.0, 10)), - 2); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.26, 0.25, 0.25, 0.05, 0.4, 10)), - 3); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.38, 0.25, 0.25, 0.05, 0.0, 10)), - 2); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.38, 0.25, 0.25, 0.05, 0.4, 10)), - 3); - - // On CPU time. - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.1, 0.05, 0.1, 0.05, 0.0, 10)), - 10); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.1, 0.05, 0.1, 0.05, 0.4, 10)), - 10); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.11, 0.05, 0.1, 0.05, 0.0, 10)), - 9); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.11, 0.05, 0.1, 0.05, 0.4, 10)), - 10); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.15, 0.05, 0.1, 0.05, 0.0, 10)), - 7); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.15, 0.05, 0.1, 0.05, 0.4, 10)), - 9); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.5, 0.25, 0.5, 0.05, 0.0, 10)), - 2); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.5, 0.25, 0.5, 0.05, 0.4, 10)), - 3); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.51, 0.25, 0.5, 0.05, 0.0, 10)), - 2); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.51, 0.25, 0.5, 0.05, 0.4, 10)), - 3); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.8, 0.25, 0.5, 0.05, 0.0, 10)), - 2); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.8, 0.25, 0.5, 0.05, 0.4, 10)), - 2); - - // Corner cases. - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.0, 0.25, 0.5, 0.05, 0.4, 10)), - 3); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.8, 0.0, 0.5, 0.05, 0.4, 10)), - 9); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.8, 0.25, 0.0, 0.05, 0.4, 10)), - 1); - EXPECT_EQ(ComputeRandomInterleavingRepetitions( - CreateInput(0.8, 0.25, 0.5, 0.0, 0.4, 10)), - 1); -} - -} // namespace -} // namespace internal -} // namespace benchmark -- cgit v1.2.3 From fbc31405b2a2838560e155d7aec937e135ae0d81 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Thu, 3 Jun 2021 21:16:54 +0300 Subject: Random interleaving of benchmark repetitions - the sequel (fixes #1051) (#1163) Inspired by the original implementation by Hai Huang @haih-g from https://github.com/google/benchmark/pull/1105. The original implementation had design deficiencies that weren't really addressable without redesign, so it was reverted. In essence, the original implementation consisted of two separateable parts: * reducing the amount time each repetition is run for, and symmetrically increasing repetition count * running the repetitions in random order While it worked fine for the usual case, it broke down when user would specify repetitions (it would completely ignore that request), or specified per-repetition min time (while it would still adjust the repetition count, it would not adjust the per-repetition time, leading to much greater run times) Here, like i was originally suggesting in the original review, i'm separating the features, and only dealing with a single one - running repetitions in random order. Now that the runs/repetitions are no longer in-order, the tooling may wish to sort the output, and indeed `compare.py` has been updated to do that: #1168. --- test/benchmark_random_interleaving_gtest.cc | 126 ++++++++++++++++++++++++++++ 1 file changed, 126 insertions(+) create mode 100644 test/benchmark_random_interleaving_gtest.cc (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc new file mode 100644 index 0000000..8e28dab --- /dev/null +++ b/test/benchmark_random_interleaving_gtest.cc @@ -0,0 +1,126 @@ +#include +#include +#include + +#include "../src/commandlineflags.h" +#include "../src/string_util.h" +#include "benchmark/benchmark.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +DECLARE_bool(benchmark_enable_random_interleaving); +DECLARE_string(benchmark_filter); +DECLARE_int32(benchmark_repetitions); + +namespace benchmark { +namespace internal { +namespace { + +class EventQueue : public std::queue { + public: + void Put(const std::string& event) { push(event); } + + void Clear() { + while (!empty()) { + pop(); + } + } + + std::string Get() { + std::string event = front(); + pop(); + return event; + } +}; + +static EventQueue* queue = new EventQueue; + +class NullReporter : public BenchmarkReporter { + public: + bool ReportContext(const Context& /*context*/) override { return true; } + void ReportRuns(const std::vector& /* report */) override {} +}; + +class BenchmarkTest : public testing::Test { + public: + static void SetupHook(int /* num_threads */) { queue->push("Setup"); } + + static void TeardownHook(int /* num_threads */) { queue->push("Teardown"); } + + void Execute(const std::string& pattern) { + queue->Clear(); + + BenchmarkReporter* reporter = new NullReporter; + FLAGS_benchmark_filter = pattern; + RunSpecifiedBenchmarks(reporter); + delete reporter; + + queue->Put("DONE"); // End marker + } +}; + +static void BM_Match1(benchmark::State& state) { + const int64_t arg = state.range(0); + + for (auto _ : state) { + } + queue->Put(StrFormat("BM_Match1/%d", static_cast(arg))); +} +BENCHMARK(BM_Match1) + ->Iterations(100) + ->Arg(1) + ->Arg(2) + ->Arg(3) + ->Range(10, 80) + ->Args({90}) + ->Args({100}); + +TEST_F(BenchmarkTest, Match1) { + Execute("BM_Match1"); + ASSERT_EQ("BM_Match1/1", queue->Get()); + ASSERT_EQ("BM_Match1/2", queue->Get()); + ASSERT_EQ("BM_Match1/3", queue->Get()); + ASSERT_EQ("BM_Match1/10", queue->Get()); + ASSERT_EQ("BM_Match1/64", queue->Get()); + ASSERT_EQ("BM_Match1/80", queue->Get()); + ASSERT_EQ("BM_Match1/90", queue->Get()); + ASSERT_EQ("BM_Match1/100", queue->Get()); + ASSERT_EQ("DONE", queue->Get()); +} + +TEST_F(BenchmarkTest, Match1WithRepetition) { + FLAGS_benchmark_repetitions = 2; + + Execute("BM_Match1/(64|80)"); + ASSERT_EQ("BM_Match1/64", queue->Get()); + ASSERT_EQ("BM_Match1/64", queue->Get()); + ASSERT_EQ("BM_Match1/80", queue->Get()); + ASSERT_EQ("BM_Match1/80", queue->Get()); + ASSERT_EQ("DONE", queue->Get()); +} + +TEST_F(BenchmarkTest, Match1WithRandomInterleaving) { + FLAGS_benchmark_enable_random_interleaving = true; + FLAGS_benchmark_repetitions = 100; + + std::map element_count; + std::map interleaving_count; + Execute("BM_Match1/(64|80)"); + for (int i = 0; i < 100; ++i) { + std::vector interleaving; + interleaving.push_back(queue->Get()); + interleaving.push_back(queue->Get()); + element_count[interleaving[0].c_str()]++; + element_count[interleaving[1].c_str()]++; + interleaving_count[StrFormat("%s,%s", interleaving[0].c_str(), + interleaving[1].c_str())]++; + } + EXPECT_EQ(element_count["BM_Match1/64"], 100) << "Unexpected repetitions."; + EXPECT_EQ(element_count["BM_Match1/80"], 100) << "Unexpected repetitions."; + EXPECT_GE(interleaving_count.size(), 2) << "Interleaving was not randomized."; + ASSERT_EQ("DONE", queue->Get()); +} + +} // namespace +} // namespace internal +} // namespace benchmark -- cgit v1.2.3 From 5da566042943805be87d19bed05092d21410f77c Mon Sep 17 00:00:00 2001 From: Dominic Hamon Date: Thu, 24 Jun 2021 16:50:19 +0100 Subject: Move flags inside the `benchmark` namespace (#1185) This avoids clashes with other libraries that might define the same flags. --- test/benchmark_random_interleaving_gtest.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc index 8e28dab..6e48283 100644 --- a/test/benchmark_random_interleaving_gtest.cc +++ b/test/benchmark_random_interleaving_gtest.cc @@ -8,11 +8,12 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" +namespace benchmark { + DECLARE_bool(benchmark_enable_random_interleaving); DECLARE_string(benchmark_filter); DECLARE_int32(benchmark_repetitions); -namespace benchmark { namespace internal { namespace { -- cgit v1.2.3 From 6a5bf081d34b719aeea5a2eb2c83a17c2f24514f Mon Sep 17 00:00:00 2001 From: Dominic Hamon Date: Thu, 24 Jun 2021 18:21:59 +0100 Subject: prefix macros to avoid clashes (#1186) --- test/benchmark_random_interleaving_gtest.cc | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc index 6e48283..f68c680 100644 --- a/test/benchmark_random_interleaving_gtest.cc +++ b/test/benchmark_random_interleaving_gtest.cc @@ -10,9 +10,9 @@ namespace benchmark { -DECLARE_bool(benchmark_enable_random_interleaving); -DECLARE_string(benchmark_filter); -DECLARE_int32(benchmark_repetitions); +BM_DECLARE_bool(benchmark_enable_random_interleaving); +BM_DECLARE_string(benchmark_filter); +BM_DECLARE_int32(benchmark_repetitions); namespace internal { namespace { -- cgit v1.2.3 From 19026e232c15dfdfd2b4ad80c6766b5ab87e43d3 Mon Sep 17 00:00:00 2001 From: Dominic Hamon Date: Tue, 29 Jun 2021 11:06:53 +0100 Subject: fix clang-tidy warnings (#1195) --- test/benchmark_random_interleaving_gtest.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc index f68c680..88e274e 100644 --- a/test/benchmark_random_interleaving_gtest.cc +++ b/test/benchmark_random_interleaving_gtest.cc @@ -34,7 +34,7 @@ class EventQueue : public std::queue { } }; -static EventQueue* queue = new EventQueue; +EventQueue* queue = new EventQueue(); class NullReporter : public BenchmarkReporter { public: @@ -60,7 +60,7 @@ class BenchmarkTest : public testing::Test { } }; -static void BM_Match1(benchmark::State& state) { +void BM_Match1(benchmark::State& state) { const int64_t arg = state.range(0); for (auto _ : state) { -- cgit v1.2.3 From ab867074da2423c2d9cf225233191a01f043485d Mon Sep 17 00:00:00 2001 From: dominc8 Date: Mon, 6 Dec 2021 12:18:04 +0100 Subject: clang-tidy: readability-redundant and performance (#1298) * clang-tidy: readability-redundant-* * clang-tidy: performance-* --- test/benchmark_random_interleaving_gtest.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc index 88e274e..d04befa 100644 --- a/test/benchmark_random_interleaving_gtest.cc +++ b/test/benchmark_random_interleaving_gtest.cc @@ -111,8 +111,8 @@ TEST_F(BenchmarkTest, Match1WithRandomInterleaving) { std::vector interleaving; interleaving.push_back(queue->Get()); interleaving.push_back(queue->Get()); - element_count[interleaving[0].c_str()]++; - element_count[interleaving[1].c_str()]++; + element_count[interleaving[0]]++; + element_count[interleaving[1]]++; interleaving_count[StrFormat("%s,%s", interleaving[0].c_str(), interleaving[1].c_str())]++; } -- cgit v1.2.3 From 6e51dcbcc3965b3f4b13d4bab5e43895c1a73290 Mon Sep 17 00:00:00 2001 From: Dominic Hamon Date: Fri, 11 Feb 2022 10:23:05 +0000 Subject: Expose default display reporter creation in public API (#1344) * Expose default display reporter creation in public API this is useful when a custom reporter wants to fall back on the default display reporter, but doesn't necessarily have access to the benchmark library flag configuration. * Make use of unique_ptr in the random interleaving test. * clang-format --- test/benchmark_random_interleaving_gtest.cc | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'test/benchmark_random_interleaving_gtest.cc') diff --git a/test/benchmark_random_interleaving_gtest.cc b/test/benchmark_random_interleaving_gtest.cc index d04befa..7f20867 100644 --- a/test/benchmark_random_interleaving_gtest.cc +++ b/test/benchmark_random_interleaving_gtest.cc @@ -51,10 +51,9 @@ class BenchmarkTest : public testing::Test { void Execute(const std::string& pattern) { queue->Clear(); - BenchmarkReporter* reporter = new NullReporter; + std::unique_ptr reporter(new NullReporter()); FLAGS_benchmark_filter = pattern; - RunSpecifiedBenchmarks(reporter); - delete reporter; + RunSpecifiedBenchmarks(reporter.get()); queue->Put("DONE"); // End marker } -- cgit v1.2.3