1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 *
7 */
8
9 #include <folly/Benchmark.h>
10 #include <quic/common/CircularDeque.h>
11 #include <quic/common/test/TestUtils.h>
12 #include <deque>
13
14 namespace {
15 constexpr size_t kLen = 50;
16 template <typename T>
prepareDeque(T & d,size_t count)17 void prepareDeque(T& d, size_t count) {
18 size_t counter = 0;
19 auto buffer = quic::test::buildRandomInputData(kLen);
20 while (counter++ < count) {
21 d.emplace_back(buffer->clone()->moveToFbString().toStdString());
22 }
23 }
24 } // namespace
25
BENCHMARK(deque_push_front,iters)26 BENCHMARK(deque_push_front, iters) {
27 folly::BenchmarkSuspender suspender;
28 std::deque<std::string> d;
29 d.resize(iters);
30 auto buffer = quic::test::buildRandomInputData(kLen);
31 suspender.dismiss();
32 while (iters--) {
33 d.push_front(buffer->clone()->moveToFbString().toStdString());
34 }
35 }
36
BENCHMARK(circular_deque_push_front,iters)37 BENCHMARK(circular_deque_push_front, iters) {
38 folly::BenchmarkSuspender suspender;
39 quic::CircularDeque<std::string> d;
40 d.resize(iters);
41 auto buffer = quic::test::buildRandomInputData(kLen);
42 suspender.dismiss();
43 while (iters--) {
44 d.push_front(buffer->clone()->moveToFbString().toStdString());
45 }
46 }
47
BENCHMARK(deque_push_back,iters)48 BENCHMARK(deque_push_back, iters) {
49 folly::BenchmarkSuspender suspender;
50 std::deque<std::string> d;
51 d.resize(iters);
52 auto buffer = quic::test::buildRandomInputData(kLen);
53 suspender.dismiss();
54 while (iters--) {
55 d.push_back(buffer->clone()->moveToFbString().toStdString());
56 }
57 }
58
BENCHMARK(circular_deque_push_back,iters)59 BENCHMARK(circular_deque_push_back, iters) {
60 folly::BenchmarkSuspender suspender;
61 quic::CircularDeque<std::string> d;
62 d.resize(iters);
63 auto buffer = quic::test::buildRandomInputData(kLen);
64 suspender.dismiss();
65 while (iters--) {
66 d.push_back(buffer->clone()->moveToFbString().toStdString());
67 }
68 }
69
BENCHMARK(deque_pop_front,iters)70 BENCHMARK(deque_pop_front, iters) {
71 folly::BenchmarkSuspender suspender;
72 std::deque<std::string> d;
73 prepareDeque(d, iters * 2);
74 suspender.dismiss();
75 while (iters-- && !d.empty()) {
76 d.pop_front();
77 }
78 }
79
BENCHMARK(circular_deque_pop_front,iters)80 BENCHMARK(circular_deque_pop_front, iters) {
81 folly::BenchmarkSuspender suspender;
82 quic::CircularDeque<std::string> d;
83 prepareDeque(d, iters * 2);
84 suspender.dismiss();
85 while (iters-- && !d.empty()) {
86 d.pop_front();
87 }
88 }
89
BENCHMARK(deque_pop_back,iters)90 BENCHMARK(deque_pop_back, iters) {
91 folly::BenchmarkSuspender suspender;
92 std::deque<std::string> d;
93 prepareDeque(d, iters * 2);
94 suspender.dismiss();
95 while (iters-- && !d.empty()) {
96 d.pop_back();
97 }
98 }
99
BENCHMARK(circular_deque_pop_back,iters)100 BENCHMARK(circular_deque_pop_back, iters) {
101 folly::BenchmarkSuspender suspender;
102 quic::CircularDeque<std::string> d;
103 prepareDeque(d, iters * 2);
104 suspender.dismiss();
105 while (iters-- && !d.empty()) {
106 d.pop_back();
107 }
108 }
109
BENCHMARK(deque_erase_tail,iters)110 BENCHMARK(deque_erase_tail, iters) {
111 folly::BenchmarkSuspender suspender;
112 std::deque<std::string> d;
113 prepareDeque(d, iters * 2);
114 suspender.dismiss();
115 while (iters-- && !d.empty()) {
116 d.erase(d.end() - 2, d.end());
117 }
118 }
119
BENCHMARK(circular_deque_erase_tail,iters)120 BENCHMARK(circular_deque_erase_tail, iters) {
121 folly::BenchmarkSuspender suspender;
122 quic::CircularDeque<std::string> d;
123 prepareDeque(d, iters * 2);
124 suspender.dismiss();
125 while (iters-- && !d.empty()) {
126 d.erase(d.end() - 2, d.end());
127 }
128 }
129
BENCHMARK(deque_erase_head,iters)130 BENCHMARK(deque_erase_head, iters) {
131 folly::BenchmarkSuspender suspender;
132 std::deque<std::string> d;
133 prepareDeque(d, iters * 2);
134 suspender.dismiss();
135 while (iters-- && !d.empty()) {
136 d.erase(d.begin(), d.begin() + 2);
137 }
138 }
139
BENCHMARK(circular_deque_erase_head,iters)140 BENCHMARK(circular_deque_erase_head, iters) {
141 folly::BenchmarkSuspender suspender;
142 quic::CircularDeque<std::string> d;
143 prepareDeque(d, iters * 2);
144 suspender.dismiss();
145 while (iters-- && !d.empty()) {
146 d.erase(d.begin(), d.begin() + 2);
147 }
148 }
149
BENCHMARK(deque_size,iters)150 BENCHMARK(deque_size, iters) {
151 folly::BenchmarkSuspender suspender;
152 std::deque<std::string> d;
153 while (iters--) {
154 d.emplace_back("This is a test string");
155 suspender.dismiss();
156 auto s = d.size();
157 auto e = d.empty();
158 folly::doNotOptimizeAway(s);
159 folly::doNotOptimizeAway(e);
160 suspender.rehire();
161 }
162 }
163
BENCHMARK(circular_deque_size,iters)164 BENCHMARK(circular_deque_size, iters) {
165 folly::BenchmarkSuspender suspender;
166 quic::CircularDeque<std::string> d;
167 while (iters--) {
168 d.emplace_back("This is a test string");
169 suspender.dismiss();
170 auto s = d.size();
171 auto e = d.empty();
172 folly::doNotOptimizeAway(s);
173 folly::doNotOptimizeAway(e);
174 suspender.rehire();
175 }
176 }
177
BENCHMARK(deque_erase_middle,iters)178 BENCHMARK(deque_erase_middle, iters) {
179 folly::BenchmarkSuspender suspender;
180 std::deque<std::string> d;
181 prepareDeque(d, iters * 2);
182 suspender.dismiss();
183 while (iters--) {
184 d.erase(d.begin() + d.size() / 3);
185 }
186 }
187
BENCHMARK(circular_deque_erase_middle,iters)188 BENCHMARK(circular_deque_erase_middle, iters) {
189 folly::BenchmarkSuspender suspender;
190 quic::CircularDeque<std::string> d;
191 prepareDeque(d, iters * 2);
192 suspender.dismiss();
193 while (iters--) {
194 d.erase(d.begin() + d.size() / 3);
195 }
196 }
197
BENCHMARK(deque_insert_middle,iters)198 BENCHMARK(deque_insert_middle, iters) {
199 folly::BenchmarkSuspender suspender;
200 std::deque<std::string> d;
201 prepareDeque(d, iters / 2);
202 suspender.dismiss();
203 while (iters--) {
204 d.insert(d.begin() + d.size() / 2, "This is a test string");
205 }
206 }
207
BENCHMARK(circular_deque_insert_middle,iters)208 BENCHMARK(circular_deque_insert_middle, iters) {
209 folly::BenchmarkSuspender suspender;
210 quic::CircularDeque<std::string> d;
211 prepareDeque(d, iters / 2);
212 suspender.dismiss();
213 while (iters--) {
214 d.insert(d.begin() + d.size() / 2, "This is a test string");
215 }
216 }
217
main(int argc,char * argv[])218 int main(int argc, char* argv[]) {
219 gflags::ParseCommandLineFlags(&argc, &argv, true);
220 folly::runBenchmarks();
221 return 0;
222 }
223
224 /*
225 * On an Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz
226 *
227 buck run @mode/opt quic/common/test:CircularDequeBench -- --bm_min_iters=100000
228 ============================================================================
229 quic/common/test/CircularDequeBench.cpp relative time/iter iters/s
230 ============================================================================
231 deque_push_front 109.56ns 9.13M
232 circular_deque_push_front 97.77ns 10.23M
233 deque_push_back 106.10ns 9.43M
234 circular_deque_push_back 99.18ns 10.08M
235 deque_pop_front 34.43ns 29.05M
236 circular_deque_pop_front 34.01ns 29.41M
237 deque_pop_back 32.57ns 30.70M
238 circular_deque_pop_back 33.32ns 30.01M
239 deque_erase_tail 61.55ns 16.25M
240 circular_deque_erase_tail 41.64ns 24.02M
241 deque_erase_head 54.06ns 18.50M
242 circular_deque_erase_head 50.11ns 19.96M
243 deque_size 21.56ns 46.39M
244 circular_deque_size 21.75ns 45.98M
245 deque_erase_middle 238.35us 4.20K
246 circular_deque_erase_middle 244.40us 4.09K
247 deque_insert_middle 165.43us 6.04K
248 circular_deque_insert_middle 265.68us 3.76K
249 ============================================================================
250 */
251