inlined_vector_benchmark.cc
Go to the documentation of this file.
1 // Copyright 2019 The Abseil Authors.
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 // https://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 <string>
16 #include <vector>
17 
18 #include "benchmark/benchmark.h"
20 #include "absl/base/macros.h"
22 #include "absl/strings/str_cat.h"
23 
24 namespace {
25 
26 void BM_InlinedVectorFill(benchmark::State& state) {
28  int val = 10;
29  for (auto _ : state) {
30  benchmark::DoNotOptimize(v);
31  v.push_back(val);
32  }
33 }
34 BENCHMARK(BM_InlinedVectorFill)->Range(0, 1024);
35 
36 void BM_InlinedVectorFillRange(benchmark::State& state) {
37  const int len = state.range(0);
38  std::unique_ptr<int[]> ia(new int[len]);
39  for (int i = 0; i < len; i++) {
40  ia[i] = i;
41  }
42  auto* from = ia.get();
43  auto* to = from + len;
44  for (auto _ : state) {
45  benchmark::DoNotOptimize(from);
46  benchmark::DoNotOptimize(to);
48  benchmark::DoNotOptimize(v);
49  }
50 }
51 BENCHMARK(BM_InlinedVectorFillRange)->Range(0, 1024);
52 
53 void BM_StdVectorFill(benchmark::State& state) {
54  std::vector<int> v;
55  int val = 10;
56  for (auto _ : state) {
57  benchmark::DoNotOptimize(v);
58  benchmark::DoNotOptimize(val);
59  v.push_back(val);
60  }
61 }
62 BENCHMARK(BM_StdVectorFill)->Range(0, 1024);
63 
64 // The purpose of the next two benchmarks is to verify that
65 // absl::InlinedVector is efficient when moving is more efficent than
66 // copying. To do so, we use strings that are larger than the short
67 // string optimization.
68 bool StringRepresentedInline(std::string s) {
69  const char* chars = s.data();
70  std::string s1 = std::move(s);
71  return s1.data() != chars;
72 }
73 
74 int GetNonShortStringOptimizationSize() {
75  for (int i = 24; i <= 192; i *= 2) {
76  if (!StringRepresentedInline(std::string(i, 'A'))) {
77  return i;
78  }
79  }
81  FATAL,
82  "Failed to find a std::string larger than the short std::string optimization");
83  return -1;
84 }
85 
86 void BM_InlinedVectorFillString(benchmark::State& state) {
87  const int len = state.range(0);
88  const int no_sso = GetNonShortStringOptimizationSize();
89  std::string strings[4] = {std::string(no_sso, 'A'), std::string(no_sso, 'B'),
90  std::string(no_sso, 'C'), std::string(no_sso, 'D')};
91 
92  for (auto _ : state) {
94  for (int i = 0; i < len; i++) {
95  v.push_back(strings[i & 3]);
96  }
97  }
98  state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
99 }
100 BENCHMARK(BM_InlinedVectorFillString)->Range(0, 1024);
101 
102 void BM_StdVectorFillString(benchmark::State& state) {
103  const int len = state.range(0);
104  const int no_sso = GetNonShortStringOptimizationSize();
105  std::string strings[4] = {std::string(no_sso, 'A'), std::string(no_sso, 'B'),
106  std::string(no_sso, 'C'), std::string(no_sso, 'D')};
107 
108  for (auto _ : state) {
109  std::vector<std::string> v;
110  for (int i = 0; i < len; i++) {
111  v.push_back(strings[i & 3]);
112  }
113  }
114  state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
115 }
116 BENCHMARK(BM_StdVectorFillString)->Range(0, 1024);
117 
118 struct Buffer { // some arbitrary structure for benchmarking.
119  char* base;
120  int length;
121  int capacity;
122  void* user_data;
123 };
124 
125 void BM_InlinedVectorAssignments(benchmark::State& state) {
126  const int len = state.range(0);
127  using BufferVec = absl::InlinedVector<Buffer, 2>;
128 
129  BufferVec src;
130  src.resize(len);
131 
132  BufferVec dst;
133  for (auto _ : state) {
134  benchmark::DoNotOptimize(dst);
135  benchmark::DoNotOptimize(src);
136  dst = src;
137  }
138 }
139 BENCHMARK(BM_InlinedVectorAssignments)
140  ->Arg(0)
141  ->Arg(1)
142  ->Arg(2)
143  ->Arg(3)
144  ->Arg(4)
145  ->Arg(20);
146 
147 void BM_CreateFromContainer(benchmark::State& state) {
148  for (auto _ : state) {
149  absl::InlinedVector<int, 4> src{1, 2, 3};
150  benchmark::DoNotOptimize(src);
152  benchmark::DoNotOptimize(dst);
153  }
154 }
155 BENCHMARK(BM_CreateFromContainer);
156 
157 struct LargeCopyableOnly {
158  LargeCopyableOnly() : d(1024, 17) {}
159  LargeCopyableOnly(const LargeCopyableOnly& o) = default;
160  LargeCopyableOnly& operator=(const LargeCopyableOnly& o) = default;
161 
162  std::vector<int> d;
163 };
164 
165 struct LargeCopyableSwappable {
166  LargeCopyableSwappable() : d(1024, 17) {}
167 
168  LargeCopyableSwappable(const LargeCopyableSwappable& o) = default;
169 
170  LargeCopyableSwappable& operator=(LargeCopyableSwappable o) {
171  using std::swap;
172  swap(*this, o);
173  return *this;
174  }
175 
176  friend void swap(LargeCopyableSwappable& a, LargeCopyableSwappable& b) {
177  using std::swap;
178  swap(a.d, b.d);
179  }
180 
181  std::vector<int> d;
182 };
183 
184 struct LargeCopyableMovable {
185  LargeCopyableMovable() : d(1024, 17) {}
186  // Use implicitly defined copy and move.
187 
188  std::vector<int> d;
189 };
190 
191 struct LargeCopyableMovableSwappable {
192  LargeCopyableMovableSwappable() : d(1024, 17) {}
193  LargeCopyableMovableSwappable(const LargeCopyableMovableSwappable& o) =
194  default;
195  LargeCopyableMovableSwappable(LargeCopyableMovableSwappable&& o) = default;
196 
197  LargeCopyableMovableSwappable& operator=(LargeCopyableMovableSwappable o) {
198  using std::swap;
199  swap(*this, o);
200  return *this;
201  }
202  LargeCopyableMovableSwappable& operator=(LargeCopyableMovableSwappable&& o) =
203  default;
204 
205  friend void swap(LargeCopyableMovableSwappable& a,
206  LargeCopyableMovableSwappable& b) {
207  using std::swap;
208  swap(a.d, b.d);
209  }
210 
211  std::vector<int> d;
212 };
213 
214 template <typename ElementType>
215 void BM_SwapElements(benchmark::State& state) {
216  const int len = state.range(0);
218  Vec a(len);
219  Vec b;
220  for (auto _ : state) {
221  using std::swap;
222  benchmark::DoNotOptimize(a);
223  benchmark::DoNotOptimize(b);
224  swap(a, b);
225  }
226 }
227 BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableOnly)->Range(0, 1024);
228 BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableSwappable)->Range(0, 1024);
229 BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableMovable)->Range(0, 1024);
230 BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableMovableSwappable)
231  ->Range(0, 1024);
232 
233 // The following benchmark is meant to track the efficiency of the vector size
234 // as a function of stored type via the benchmark label. It is not meant to
235 // output useful sizeof operator performance. The loop is a dummy operation
236 // to fulfill the requirement of running the benchmark.
237 template <typename VecType>
238 void BM_Sizeof(benchmark::State& state) {
239  int size = 0;
240  for (auto _ : state) {
241  VecType vec;
242  size = sizeof(vec);
243  }
244  state.SetLabel(absl::StrCat("sz=", size));
245 }
246 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 1>);
247 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 4>);
248 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 7>);
249 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 8>);
250 
251 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 1>);
252 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 4>);
253 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 7>);
254 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 8>);
255 
256 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 1>);
257 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 4>);
258 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 7>);
259 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 8>);
260 
261 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 1>);
262 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 4>);
263 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 7>);
264 BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 8>);
265 
266 void BM_InlinedVectorIndexInlined(benchmark::State& state) {
267  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
268  for (auto _ : state) {
269  benchmark::DoNotOptimize(v);
270  benchmark::DoNotOptimize(v[4]);
271  }
272 }
273 BENCHMARK(BM_InlinedVectorIndexInlined);
274 
275 void BM_InlinedVectorIndexExternal(benchmark::State& state) {
276  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
277  for (auto _ : state) {
278  benchmark::DoNotOptimize(v);
279  benchmark::DoNotOptimize(v[4]);
280  }
281 }
282 BENCHMARK(BM_InlinedVectorIndexExternal);
283 
284 void BM_StdVectorIndex(benchmark::State& state) {
285  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
286  for (auto _ : state) {
287  benchmark::DoNotOptimize(v);
288  benchmark::DoNotOptimize(v[4]);
289  }
290 }
291 BENCHMARK(BM_StdVectorIndex);
292 
293 void BM_InlinedVectorDataInlined(benchmark::State& state) {
294  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
295  for (auto _ : state) {
296  benchmark::DoNotOptimize(v);
297  benchmark::DoNotOptimize(v.data());
298  }
299 }
300 BENCHMARK(BM_InlinedVectorDataInlined);
301 
302 void BM_InlinedVectorDataExternal(benchmark::State& state) {
303  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
304  for (auto _ : state) {
305  benchmark::DoNotOptimize(v);
306  benchmark::DoNotOptimize(v.data());
307  }
308  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
309 }
310 BENCHMARK(BM_InlinedVectorDataExternal);
311 
312 void BM_StdVectorData(benchmark::State& state) {
313  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
314  for (auto _ : state) {
315  benchmark::DoNotOptimize(v);
316  benchmark::DoNotOptimize(v.data());
317  }
318  state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
319 }
320 BENCHMARK(BM_StdVectorData);
321 
322 void BM_InlinedVectorSizeInlined(benchmark::State& state) {
323  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
324  for (auto _ : state) {
325  benchmark::DoNotOptimize(v);
326  benchmark::DoNotOptimize(v.size());
327  }
328 }
329 BENCHMARK(BM_InlinedVectorSizeInlined);
330 
331 void BM_InlinedVectorSizeExternal(benchmark::State& state) {
332  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
333  for (auto _ : state) {
334  benchmark::DoNotOptimize(v);
335  benchmark::DoNotOptimize(v.size());
336  }
337 }
338 BENCHMARK(BM_InlinedVectorSizeExternal);
339 
340 void BM_StdVectorSize(benchmark::State& state) {
341  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
342  for (auto _ : state) {
343  benchmark::DoNotOptimize(v);
344  benchmark::DoNotOptimize(v.size());
345  }
346 }
347 BENCHMARK(BM_StdVectorSize);
348 
349 void BM_InlinedVectorEmptyInlined(benchmark::State& state) {
350  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
351  for (auto _ : state) {
352  benchmark::DoNotOptimize(v);
353  benchmark::DoNotOptimize(v.empty());
354  }
355 }
356 BENCHMARK(BM_InlinedVectorEmptyInlined);
357 
358 void BM_InlinedVectorEmptyExternal(benchmark::State& state) {
359  absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
360  for (auto _ : state) {
361  benchmark::DoNotOptimize(v);
362  benchmark::DoNotOptimize(v.empty());
363  }
364 }
365 BENCHMARK(BM_InlinedVectorEmptyExternal);
366 
367 void BM_StdVectorEmpty(benchmark::State& state) {
368  std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
369  for (auto _ : state) {
370  benchmark::DoNotOptimize(v);
371  benchmark::DoNotOptimize(v.empty());
372  }
373 }
374 BENCHMARK(BM_StdVectorEmpty);
375 
376 constexpr size_t kInlineElements = 4;
377 constexpr size_t kSmallSize = kInlineElements / 2;
378 constexpr size_t kLargeSize = kInlineElements * 2;
379 constexpr size_t kBatchSize = 100;
380 
381 struct TrivialType {
382  size_t val;
383 };
384 
386 
387 class NontrivialType {
388  public:
389  ABSL_ATTRIBUTE_NOINLINE NontrivialType() : val_() {}
390 
391  ABSL_ATTRIBUTE_NOINLINE NontrivialType(const NontrivialType& other)
392  : val_(other.val_) {}
393 
394  ABSL_ATTRIBUTE_NOINLINE NontrivialType& operator=(
395  const NontrivialType& other) {
396  val_ = other.val_;
397  return *this;
398  }
399 
400  ABSL_ATTRIBUTE_NOINLINE ~NontrivialType() noexcept {}
401 
402  private:
403  size_t val_;
404 };
405 
407 
408 template <typename VecT, typename PrepareVec, typename TestVec>
409 void BatchedBenchmark(benchmark::State& state, PrepareVec prepare_vec,
410  TestVec test_vec) {
411  VecT vectors[kBatchSize];
412 
413  while (state.KeepRunningBatch(kBatchSize)) {
414  // Prepare batch
415  state.PauseTiming();
416  for (auto& vec : vectors) {
417  prepare_vec(&vec);
418  }
419  benchmark::DoNotOptimize(vectors);
420  state.ResumeTiming();
421 
422  // Test batch
423  for (auto& vec : vectors) {
424  test_vec(&vec);
425  }
426  }
427 }
428 
429 template <typename VecT, size_t FromSize>
430 void BM_Clear(benchmark::State& state) {
431  BatchedBenchmark<VecT>(
432  state,
433  /* prepare_vec = */ [](VecT* vec) { vec->resize(FromSize); },
434  /* test_vec = */ [](VecT* vec) { vec->clear(); });
435 }
436 
437 BENCHMARK_TEMPLATE(BM_Clear, TrivialVec, kSmallSize);
438 BENCHMARK_TEMPLATE(BM_Clear, TrivialVec, kLargeSize);
439 
440 BENCHMARK_TEMPLATE(BM_Clear, NontrivialVec, kSmallSize);
441 BENCHMARK_TEMPLATE(BM_Clear, NontrivialVec, kLargeSize);
442 
443 } // namespace
int v
Definition: variant_test.cc:81
pointer data() noexcept
#define ABSL_RAW_LOG(severity,...)
Definition: raw_logging.h:42
std::string StrCat(const AlphaNum &a, const AlphaNum &b)
Definition: str_cat.cc:98
size_t to
size_type size() const noexcept
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
uintptr_t size
UnboundConversion o
Definition: parser_test.cc:86
void resize(size_type n)
#define ABSL_ATTRIBUTE_NOINLINE
Definition: attributes.h:136
uint64_t b
Definition: layout_test.cc:50
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
size_t from
bool empty() const noexcept
std::size_t length
Definition: test_util.cc:52
void push_back(const_reference v)


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:36