1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef BENCHMARK_CONTAINER_BENCHMARKS_H
11#define BENCHMARK_CONTAINER_BENCHMARKS_H
12
13#include <cassert>
14
15#include "Utilities.h"
16#include "benchmark/benchmark.h"
17
18namespace ContainerBenchmarks {
19
20template <class Container>
21void BM_ConstructSize(benchmark::State& st, Container) {
22  auto size = st.range(0);
23  for (auto _ : st) {
24    Container c(size);
25    DoNotOptimizeData(c);
26  }
27}
28
29template <class Container>
30void BM_ConstructSizeValue(benchmark::State& st, Container, typename Container::value_type const& val) {
31  const auto size = st.range(0);
32  for (auto _ : st) {
33    Container c(size, val);
34    DoNotOptimizeData(c);
35  }
36}
37
38template <class Container, class GenInputs>
39void BM_ConstructIterIter(benchmark::State& st, Container, GenInputs gen) {
40    auto in = gen(st.range(0));
41    const auto begin = in.begin();
42    const auto end = in.end();
43    benchmark::DoNotOptimize(&in);
44    while (st.KeepRunning()) {
45        Container c(begin, end);
46        DoNotOptimizeData(c);
47    }
48}
49
50template <class Container, class GenInputs>
51void BM_InsertValue(benchmark::State& st, Container c, GenInputs gen) {
52    auto in = gen(st.range(0));
53    const auto end = in.end();
54    while (st.KeepRunning()) {
55        c.clear();
56        for (auto it = in.begin(); it != end; ++it) {
57            benchmark::DoNotOptimize(&(*c.insert(*it).first));
58        }
59        benchmark::ClobberMemory();
60    }
61}
62
63template <class Container, class GenInputs>
64void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
65    auto in = gen(st.range(0));
66    const auto end = in.end();
67    while (st.KeepRunning()) {
68        c.clear();
69        c.rehash(16);
70        for (auto it = in.begin(); it != end; ++it) {
71            benchmark::DoNotOptimize(&(*c.insert(*it).first));
72        }
73        benchmark::ClobberMemory();
74    }
75}
76
77
78template <class Container, class GenInputs>
79void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) {
80    auto in = gen(st.range(0));
81    const auto end = in.end();
82    c.insert(in.begin(), in.end());
83    benchmark::DoNotOptimize(&c);
84    benchmark::DoNotOptimize(&in);
85    while (st.KeepRunning()) {
86        for (auto it = in.begin(); it != end; ++it) {
87            benchmark::DoNotOptimize(&(*c.insert(*it).first));
88        }
89        benchmark::ClobberMemory();
90    }
91}
92
93
94template <class Container, class GenInputs>
95void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) {
96    auto in = gen(st.range(0));
97    const auto end = in.end();
98    c.insert(in.begin(), in.end());
99    benchmark::DoNotOptimize(&c);
100    benchmark::DoNotOptimize(&in);
101    while (st.KeepRunning()) {
102        for (auto it = in.begin(); it != end; ++it) {
103            benchmark::DoNotOptimize(&(*c.emplace(*it).first));
104        }
105        benchmark::ClobberMemory();
106    }
107}
108
109template <class Container, class GenInputs>
110static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
111    auto in = gen(st.range(0));
112    c.insert(in.begin(), in.end());
113    benchmark::DoNotOptimize(&(*c.begin()));
114    const auto end = in.data() + in.size();
115    while (st.KeepRunning()) {
116        for (auto it = in.data(); it != end; ++it) {
117            benchmark::DoNotOptimize(&(*c.find(*it)));
118        }
119        benchmark::ClobberMemory();
120    }
121}
122
123template <class Container, class GenInputs>
124static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
125    c.rehash(8);
126    auto in = gen(st.range(0));
127    c.insert(in.begin(), in.end());
128    benchmark::DoNotOptimize(&(*c.begin()));
129    const auto end = in.data() + in.size();
130    while (st.KeepRunning()) {
131        for (auto it = in.data(); it != end; ++it) {
132            benchmark::DoNotOptimize(&(*c.find(*it)));
133        }
134        benchmark::ClobberMemory();
135    }
136}
137
138} // end namespace ContainerBenchmarks
139
140#endif // BENCHMARK_CONTAINER_BENCHMARKS_H
141