1 /*
2 * Copyright (C) 2022 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <random>
18
19 #include <benchmark/benchmark.h>
20
21 #include "src/trace_processor/containers/row_map_algorithms.h"
22
23 using perfetto::trace_processor::BitVector;
24
25 namespace {
26
27 using namespace perfetto::trace_processor::row_map_algorithms;
28
IsBenchmarkFunctionalOnly()29 bool IsBenchmarkFunctionalOnly() {
30 return getenv("BENCHMARK_FUNCTIONAL_TEST_ONLY") != nullptr;
31 }
32
BvWithSetBits(uint32_t bv_set_bits)33 BitVector BvWithSetBits(uint32_t bv_set_bits) {
34 static constexpr uint32_t kRandomSeed = 29;
35 std::minstd_rand0 rnd_engine(kRandomSeed);
36
37 BitVector bv;
38 for (uint32_t i = 0; i < bv_set_bits;) {
39 if (rnd_engine() % 2 == 0) {
40 bv.AppendTrue();
41 ++i;
42 } else {
43 bv.AppendFalse();
44 }
45 }
46 return bv;
47 }
48
IvWithSizeAndMaxIndex(uint32_t bv_set_bits,uint32_t set_bit_to_selector_ratio)49 std::vector<uint32_t> IvWithSizeAndMaxIndex(
50 uint32_t bv_set_bits,
51 uint32_t set_bit_to_selector_ratio) {
52 static constexpr uint32_t kRandomSeed = 78;
53 std::minstd_rand0 rnd_engine(kRandomSeed);
54
55 uint32_t size = bv_set_bits / set_bit_to_selector_ratio;
56 std::vector<uint32_t> indices(size);
57 for (uint32_t i = 0; i < size; ++i) {
58 indices[i] = rnd_engine() % bv_set_bits;
59 }
60 return indices;
61 }
62
BvWithIvArgs(benchmark::internal::Benchmark * b)63 void BvWithIvArgs(benchmark::internal::Benchmark* b) {
64 std::vector<int> set_bit_to_selector_ratios;
65 if (IsBenchmarkFunctionalOnly()) {
66 set_bit_to_selector_ratios = std::vector<int>{2};
67 } else {
68 set_bit_to_selector_ratios = std::vector<int>{2, 4, 6, 8, 10, 12, 16, 32};
69 }
70
71 std::vector<int> bv_set_bits;
72 if (IsBenchmarkFunctionalOnly()) {
73 bv_set_bits = std::vector<int>{1024};
74 } else {
75 bv_set_bits = std::vector<int>{1024, 4096, 1024 * 1024};
76 }
77
78 for (int bv_set_bit : bv_set_bits) {
79 for (int set_bit_to_selector_ratio : set_bit_to_selector_ratios) {
80 b->Args({bv_set_bit, set_bit_to_selector_ratio});
81 }
82 }
83 }
84
85 // |BM_SelectBvWithIvByConvertToIv| and |BM_SelectBvWithIvByIndexOfNthSet| are
86 // used together to find the ratio between the selector size and the number of
87 // set bits in the BitVector where |SelectBvWithIvByIndexOfNthSet| is faster
88 // than |SelectBvWithIvByConvertToIv|.
89 //
90 // See the comment in SelectBvWithIv in row_map.cc for more information on this.
91
BM_SelectBvWithIvByConvertToIv(benchmark::State & state)92 static void BM_SelectBvWithIvByConvertToIv(benchmark::State& state) {
93 uint32_t bv_set_bit = static_cast<uint32_t>(state.range(0));
94 uint32_t set_bit_to_selector_ratio = static_cast<uint32_t>(state.range(1));
95
96 BitVector bv = BvWithSetBits(bv_set_bit);
97 std::vector<uint32_t> iv =
98 IvWithSizeAndMaxIndex(bv_set_bit, set_bit_to_selector_ratio);
99
100 for (auto _ : state) {
101 benchmark::DoNotOptimize(SelectBvWithIvByConvertToIv(bv, iv));
102 }
103 }
104 BENCHMARK(BM_SelectBvWithIvByConvertToIv)->Apply(BvWithIvArgs);
105
BM_SelectBvWithIvByIndexOfNthSet(benchmark::State & state)106 static void BM_SelectBvWithIvByIndexOfNthSet(benchmark::State& state) {
107 uint32_t bv_set_bit = static_cast<uint32_t>(state.range(0));
108 uint32_t set_bit_to_selector_ratio = static_cast<uint32_t>(state.range(1));
109
110 BitVector bv = BvWithSetBits(bv_set_bit);
111 std::vector<uint32_t> iv =
112 IvWithSizeAndMaxIndex(bv_set_bit, set_bit_to_selector_ratio);
113
114 for (auto _ : state) {
115 benchmark::DoNotOptimize(SelectBvWithIvByIndexOfNthSet(bv, iv));
116 }
117 }
118 BENCHMARK(BM_SelectBvWithIvByIndexOfNthSet)->Apply(BvWithIvArgs);
119
120 } // namespace
121