2 * Copyright 2016-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include <folly/Benchmark.h>
21 #include <folly/Random.h>
22 #include <folly/container/Enumerate.h>
23 #include <folly/container/Foreach.h>
24 #include <folly/init/Init.h>
26 using namespace folly;
27 using namespace folly::detail;
30 // 1. Benchmark iterating through the man with FOR_EACH, and also assign
31 // iter->first and iter->second to local vars inside the FOR_EACH loop.
32 // 2. Benchmark iterating through the man with FOR_EACH, but use iter->first and
33 // iter->second as is, without assigning to local variables.
34 // 3. Use FOR_EACH_KV loop to iterate through the map.
36 // For use in benchmarks below.
37 std::map<int, std::string> bmMap;
38 std::vector<int> vec_one;
39 std::vector<int> vec_two;
41 // Smallest type to isolate iteration overhead.
42 std::vector<char> vec_char;
44 void setupBenchmark(size_t iters) {
46 for (size_t i = 0; i < iters; ++i) {
47 bmMap[i] = "teststring";
52 vec_one.resize(iters);
53 vec_two.resize(iters);
56 void setupCharVecBenchmark(size_t iters) {
57 vec_char.resize(iters);
59 vec_char.begin(), vec_char.end(), [] { return Random::rand32(128); });
62 BENCHMARK(ForEachFunctionNoAssign, iters) {
63 BenchmarkSuspender suspender;
66 std::string sumValues;
67 setupBenchmark(iters);
69 suspender.dismissing([&]() {
70 folly::for_each(bmMap, [&](auto& key_val_pair) {
71 sumKeys += key_val_pair.first;
72 sumValues += key_val_pair.second;
74 doNotOptimizeAway(sumKeys);
78 BENCHMARK(StdForEachFunctionNoAssign, iters) {
79 BenchmarkSuspender suspender;
82 std::string sumValues;
83 setupBenchmark(iters);
85 suspender.dismissing([&]() {
86 std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
87 sumKeys += key_val_pair.first;
88 sumValues += key_val_pair.second;
90 doNotOptimizeAway(sumKeys);
94 BENCHMARK(RangeBasedForLoopNoAssign, iters) {
95 BenchmarkSuspender suspender;
97 std::string sumValues;
98 setupBenchmark(iters);
100 suspender.dismissing([&]() {
101 for (auto& key_val_pair : bmMap) {
102 sumKeys += key_val_pair.first;
103 sumValues += key_val_pair.second;
105 doNotOptimizeAway(sumKeys);
109 BENCHMARK(ManualLoopNoAssign, iters) {
110 BenchmarkSuspender suspender;
113 std::string sumValues;
114 setupBenchmark(iters);
116 suspender.dismissing([&]() {
117 for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
118 sumKeys += iter->first;
119 sumValues += iter->second;
121 doNotOptimizeAway(sumKeys);
125 BENCHMARK(ForEachFunctionAssign, iters) {
126 BenchmarkSuspender suspender;
129 std::string sumValues;
130 setupBenchmark(iters);
132 suspender.dismissing([&]() {
133 folly::for_each(bmMap, [&](auto& key_val_pair) {
134 const int k = key_val_pair.first;
135 const std::string v = key_val_pair.second;
142 BENCHMARK(StdForEachFunctionAssign, iters) {
143 BenchmarkSuspender suspender;
146 std::string sumValues;
147 setupBenchmark(iters);
149 suspender.dismissing([&]() {
150 std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
151 const int k = key_val_pair.first;
152 const std::string v = key_val_pair.second;
159 BENCHMARK(RangeBasedForLoopAssign, iters) {
160 BenchmarkSuspender suspender;
163 std::string sumValues;
164 setupBenchmark(iters);
166 suspender.dismissing([&]() {
167 for (auto& key_val_pair : bmMap) {
168 const int k = key_val_pair.first;
169 const std::string v = key_val_pair.second;
176 BENCHMARK(ManualLoopAssign, iters) {
177 BenchmarkSuspender suspender;
180 std::string sumValues;
181 setupBenchmark(iters);
183 suspender.dismissing([&]() {
184 for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
185 const int k = iter->first;
186 const std::string v = iter->second;
193 BENCHMARK(ForEachFunctionNoAssignWithIndexManipulation, iters) {
194 BenchmarkSuspender suspender;
197 std::string sumValues;
198 setupBenchmark(iters);
200 suspender.dismissing([&]() {
201 folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
202 sumKeys += key_val_pair.first;
203 sumValues += key_val_pair.second;
209 BENCHMARK(StdForEachFunctionNoAssignWithIndexManipulation, iters) {
210 BenchmarkSuspender suspender;
213 std::string sumValues;
214 setupBenchmark(iters);
216 suspender.dismissing([&]() {
217 auto index = std::size_t{0};
218 std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
219 sumKeys += key_val_pair.first;
220 sumValues += key_val_pair.second;
227 BENCHMARK(RangeBasedForLoopNoAssignWithIndexManipulation, iters) {
228 BenchmarkSuspender suspender;
231 std::string sumValues;
232 setupBenchmark(iters);
234 suspender.dismissing([&]() {
235 auto index = std::size_t{0};
236 for (auto& key_val_pair : bmMap) {
237 sumKeys += key_val_pair.first;
238 sumValues += key_val_pair.second;
244 BENCHMARK(ForEachFunctionFetch, iters) {
245 BenchmarkSuspender suspender;
246 setupBenchmark(iters);
248 suspender.dismissing([&]() {
249 folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
250 folly::fetch(vec_one, index) = key_val_pair.first;
255 BENCHMARK(StdForEachFunctionFetch, iters) {
256 BenchmarkSuspender suspender;
257 setupBenchmark(iters);
259 suspender.dismissing([&]() {
260 auto index = std::size_t{0};
261 std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
262 *(vec_one.begin() + index++) = key_val_pair.first;
267 BENCHMARK(ForLoopFetch, iters) {
268 BenchmarkSuspender suspender;
269 setupBenchmark(iters);
271 suspender.dismissing([&]() {
272 auto index = std::size_t{0};
273 for (auto& key_val_pair : bmMap) {
274 *(vec_one.begin() + index++) = key_val_pair.first;
279 BENCHMARK(ForEachKVNoMacroAssign, iters) {
281 std::string sumValues;
283 BENCHMARK_SUSPEND { setupBenchmark(iters); }
285 FOR_EACH(iter, bmMap) {
286 const int k = iter->first;
287 const std::string v = iter->second;
293 BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
295 std::string sumValues;
297 BENCHMARK_SUSPEND { setupBenchmark(iters); }
299 FOR_EACH(iter, bmMap) {
300 sumKeys += iter->first;
301 sumValues += iter->second;
305 BENCHMARK(ForEachKVMacro, iters) {
307 std::string sumValues;
309 BENCHMARK_SUSPEND { setupBenchmark(iters); }
311 FOR_EACH_KV(k, v, bmMap) {
317 BENCHMARK(ForEachManual, iters) {
319 for (size_t i = 1; i < iters; ++i) {
322 doNotOptimizeAway(sum);
325 BENCHMARK(ForEachRange, iters) {
327 FOR_EACH_RANGE(i, 1, iters) { sum *= i; }
328 doNotOptimizeAway(sum);
331 BENCHMARK(ForEachDescendingManual, iters) {
333 for (size_t i = iters; i-- > 1;) {
336 doNotOptimizeAway(sum);
339 BENCHMARK(ForEachRangeR, iters) {
341 FOR_EACH_RANGE_R(i, 1U, iters) { sum *= i; }
342 doNotOptimizeAway(sum);
345 BENCHMARK(CharVecForRange, iters) {
347 setupCharVecBenchmark(iters);
350 for (auto& c : vec_char) {
353 doNotOptimizeAway(sum);
356 BENCHMARK(CharVecForRangeExplicitIndex, iters) {
358 setupCharVecBenchmark(iters);
362 for (auto& c : vec_char) {
366 doNotOptimizeAway(sum);
369 BENCHMARK(CharVecForEach, iters) {
371 setupCharVecBenchmark(iters);
374 folly::for_each(vec_char, [&](auto& c) { sum += c; });
375 doNotOptimizeAway(sum);
378 BENCHMARK(CharVecForEachIndex, iters) {
380 setupCharVecBenchmark(iters);
383 folly::for_each(vec_char, [&](auto& c, auto index) { sum += c * index; });
384 doNotOptimizeAway(sum);
387 BENCHMARK(CharVecForRangeEnumerate, iters) {
389 setupCharVecBenchmark(iters);
392 for (auto&& it : enumerate(vec_char)) {
393 sum += *it * it.index;
395 doNotOptimizeAway(sum);
398 int main(int argc, char** argv) {
399 folly::init(&argc, &argv);