1 // Copyright (C) 2019 The Android Open Source Project
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <random>
16
17 #include <benchmark/benchmark.h>
18
19 #include "src/trace_processor/containers/row_map.h"
20
21 using perfetto::trace_processor::BitVector;
22 using perfetto::trace_processor::RowMap;
23
24 namespace {
25
26 static constexpr uint32_t kPoolSize = 100000;
27 static constexpr uint32_t kSize = 123456;
28
CreateRange(uint32_t end)29 RowMap CreateRange(uint32_t end) {
30 static constexpr uint32_t kRandomSeed = 32;
31 std::minstd_rand0 rnd_engine(kRandomSeed);
32
33 uint32_t start = rnd_engine() % end;
34 uint32_t size = rnd_engine() % (end - start);
35 return RowMap(start, start + size);
36 }
37
CreateIndexVector(uint32_t size,uint32_t mod)38 std::vector<uint32_t> CreateIndexVector(uint32_t size, uint32_t mod) {
39 static constexpr uint32_t kRandomSeed = 476;
40 std::minstd_rand0 rnd_engine(kRandomSeed);
41 std::vector<uint32_t> rows(size);
42 for (uint32_t i = 0; i < size; ++i) {
43 rows[i] = rnd_engine() % mod;
44 }
45 return rows;
46 }
47
CreateBitVector(uint32_t size)48 BitVector CreateBitVector(uint32_t size) {
49 static constexpr uint32_t kRandomSeed = 42;
50 std::minstd_rand0 rnd_engine(kRandomSeed);
51 BitVector bv;
52 for (uint32_t i = 0; i < size; ++i) {
53 if (rnd_engine() % 2) {
54 bv.AppendTrue();
55 } else {
56 bv.AppendFalse();
57 }
58 }
59 return bv;
60 }
61
BenchRowMapGet(benchmark::State & state,RowMap rm)62 void BenchRowMapGet(benchmark::State& state, RowMap rm) {
63 auto pool_vec = CreateIndexVector(kPoolSize, rm.size());
64
65 uint32_t pool_idx = 0;
66 for (auto _ : state) {
67 benchmark::DoNotOptimize(rm.Get(pool_vec[pool_idx]));
68 pool_idx = (pool_idx + 1) % kPoolSize;
69 }
70 }
71
72 template <typename Factory>
BenchRowMapInsertIntoEmpty(benchmark::State & state,Factory factory)73 void BenchRowMapInsertIntoEmpty(benchmark::State& state, Factory factory) {
74 auto pool_vec = CreateIndexVector(kPoolSize, kSize);
75
76 uint32_t pool_idx = 0;
77 for (auto _ : state) {
78 RowMap rm = factory();
79
80 rm.Insert(pool_vec[pool_idx]);
81 pool_idx = (pool_idx + 1) % kPoolSize;
82
83 benchmark::ClobberMemory();
84 }
85 }
86
BenchRowMapSelect(benchmark::State & state,RowMap rm,const RowMap & selector)87 void BenchRowMapSelect(benchmark::State& state,
88 RowMap rm,
89 const RowMap& selector) {
90 for (auto _ : state) {
91 benchmark::DoNotOptimize(rm.SelectRows(selector));
92 }
93 }
94 } // namespace
95
BM_RowMapRangeGet(benchmark::State & state)96 static void BM_RowMapRangeGet(benchmark::State& state) {
97 BenchRowMapGet(state, RowMap(CreateRange(kSize)));
98 }
99 BENCHMARK(BM_RowMapRangeGet);
100
BM_RowMapBvGet(benchmark::State & state)101 static void BM_RowMapBvGet(benchmark::State& state) {
102 BenchRowMapGet(state, RowMap(CreateBitVector(kSize)));
103 }
104 BENCHMARK(BM_RowMapBvGet);
105
BM_RowMapIvGet(benchmark::State & state)106 static void BM_RowMapIvGet(benchmark::State& state) {
107 BenchRowMapGet(state, RowMap(CreateIndexVector(kSize, kSize)));
108 }
109 BENCHMARK(BM_RowMapIvGet);
110
111 // TODO(lalitm): add benchmarks for IndexOf after BitVector is made faster.
112 // We can't add them right now because they are just too slow to run.
113
BM_RowMapRangeInsertIntoEmpty(benchmark::State & state)114 static void BM_RowMapRangeInsertIntoEmpty(benchmark::State& state) {
115 BenchRowMapInsertIntoEmpty(state, []() { return RowMap(0, 0); });
116 }
117 BENCHMARK(BM_RowMapRangeInsertIntoEmpty);
118
BM_RowMapBvInsertIntoEmpty(benchmark::State & state)119 static void BM_RowMapBvInsertIntoEmpty(benchmark::State& state) {
120 BenchRowMapInsertIntoEmpty(state, []() { return RowMap(BitVector{}); });
121 }
122 BENCHMARK(BM_RowMapBvInsertIntoEmpty);
123
BM_RowMapIvInsertIntoEmpty(benchmark::State & state)124 static void BM_RowMapIvInsertIntoEmpty(benchmark::State& state) {
125 BenchRowMapInsertIntoEmpty(state,
126 []() { return RowMap(std::vector<uint32_t>{}); });
127 }
128 BENCHMARK(BM_RowMapIvInsertIntoEmpty);
129
BM_RowMapSelectRangeWithRange(benchmark::State & state)130 static void BM_RowMapSelectRangeWithRange(benchmark::State& state) {
131 RowMap rm(CreateRange(kSize));
132 RowMap selector(CreateRange(rm.size()));
133 BenchRowMapSelect(state, std::move(rm), std::move(selector));
134 }
135 BENCHMARK(BM_RowMapSelectRangeWithRange);
136
BM_RowMapSelectRangeWithBv(benchmark::State & state)137 static void BM_RowMapSelectRangeWithBv(benchmark::State& state) {
138 RowMap rm(CreateRange(kSize));
139 RowMap selector(CreateBitVector(rm.size()));
140 BenchRowMapSelect(state, std::move(rm), std::move(selector));
141 }
142 BENCHMARK(BM_RowMapSelectRangeWithBv);
143
BM_RowMapSelectRangeWithIv(benchmark::State & state)144 static void BM_RowMapSelectRangeWithIv(benchmark::State& state) {
145 RowMap rm(CreateRange(kSize));
146 RowMap selector(CreateIndexVector(rm.size(), rm.size()));
147 BenchRowMapSelect(state, std::move(rm), std::move(selector));
148 }
149 BENCHMARK(BM_RowMapSelectRangeWithIv);
150
BM_RowMapSelectBvWithRange(benchmark::State & state)151 static void BM_RowMapSelectBvWithRange(benchmark::State& state) {
152 RowMap rm(CreateBitVector(kSize));
153 RowMap selector(CreateRange(rm.size()));
154 BenchRowMapSelect(state, std::move(rm), std::move(selector));
155 }
156 BENCHMARK(BM_RowMapSelectBvWithRange);
157
BM_RowMapSelectBvWithBv(benchmark::State & state)158 static void BM_RowMapSelectBvWithBv(benchmark::State& state) {
159 RowMap rm(CreateBitVector(kSize));
160 RowMap selector(CreateBitVector(rm.size()));
161 BenchRowMapSelect(state, std::move(rm), std::move(selector));
162 }
163 BENCHMARK(BM_RowMapSelectBvWithBv);
164
BM_RowMapSelectBvWithIv(benchmark::State & state)165 static void BM_RowMapSelectBvWithIv(benchmark::State& state) {
166 RowMap rm(CreateBitVector(kSize));
167 RowMap selector(CreateIndexVector(rm.size(), rm.size()));
168 BenchRowMapSelect(state, std::move(rm), std::move(selector));
169 }
170 BENCHMARK(BM_RowMapSelectBvWithIv);
171
BM_RowMapSelectIvWithRange(benchmark::State & state)172 static void BM_RowMapSelectIvWithRange(benchmark::State& state) {
173 RowMap rm(CreateIndexVector(kSize, kSize));
174 RowMap selector(CreateRange(rm.size()));
175 BenchRowMapSelect(state, std::move(rm), std::move(selector));
176 }
177 BENCHMARK(BM_RowMapSelectIvWithRange);
178
BM_RowMapSelectIvWithBv(benchmark::State & state)179 static void BM_RowMapSelectIvWithBv(benchmark::State& state) {
180 RowMap rm(CreateIndexVector(kSize, kSize));
181 RowMap selector(CreateBitVector(rm.size()));
182 BenchRowMapSelect(state, std::move(rm), std::move(selector));
183 }
184 BENCHMARK(BM_RowMapSelectIvWithBv);
185
BM_RowMapSelectIvWithIv(benchmark::State & state)186 static void BM_RowMapSelectIvWithIv(benchmark::State& state) {
187 RowMap rm(CreateIndexVector(kSize, kSize));
188 RowMap selector(CreateIndexVector(rm.size(), rm.size()));
189 BenchRowMapSelect(state, std::move(rm), std::move(selector));
190 }
191 BENCHMARK(BM_RowMapSelectIvWithIv);
192