Improve performance of enumerate() with optimization disabled
[folly.git] / folly / container / test / ForeachBenchmark.cpp
1 /*
2  * Copyright 2017-present Facebook, Inc.
3  *
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
7  *
8  *   http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <algorithm>
18 #include <map>
19
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>
25
26 using namespace folly;
27 using namespace folly::detail;
28
29 // Benchmarks:
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.
35
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;
40
41 // Smallest type to isolate iteration overhead.
42 std::vector<char> vec_char;
43
44 void setupBenchmark(size_t iters) {
45   bmMap.clear();
46   for (size_t i = 0; i < iters; ++i) {
47     bmMap[i] = "teststring";
48   }
49
50   vec_one.clear();
51   vec_two.clear();
52   vec_one.resize(iters);
53   vec_two.resize(iters);
54 }
55
56 void setupCharVecBenchmark(size_t iters) {
57   vec_char.resize(iters);
58   std::generate(
59       vec_char.begin(), vec_char.end(), [] { return Random::rand32(128); });
60 }
61
62 BENCHMARK(ForEachFunctionNoAssign, iters) {
63   BenchmarkSuspender suspender;
64
65   int sumKeys = 0;
66   std::string sumValues;
67   setupBenchmark(iters);
68
69   suspender.dismissing([&]() {
70     folly::for_each(bmMap, [&](auto& key_val_pair) {
71       sumKeys += key_val_pair.first;
72       sumValues += key_val_pair.second;
73     });
74     doNotOptimizeAway(sumKeys);
75   });
76 }
77
78 BENCHMARK(StdForEachFunctionNoAssign, iters) {
79   BenchmarkSuspender suspender;
80
81   int sumKeys = 0;
82   std::string sumValues;
83   setupBenchmark(iters);
84
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;
89     });
90     doNotOptimizeAway(sumKeys);
91   });
92 }
93
94 BENCHMARK(RangeBasedForLoopNoAssign, iters) {
95   BenchmarkSuspender suspender;
96   int sumKeys = 0;
97   std::string sumValues;
98   setupBenchmark(iters);
99
100   suspender.dismissing([&]() {
101     for (auto& key_val_pair : bmMap) {
102       sumKeys += key_val_pair.first;
103       sumValues += key_val_pair.second;
104     }
105     doNotOptimizeAway(sumKeys);
106   });
107 }
108
109 BENCHMARK(ManualLoopNoAssign, iters) {
110   BenchmarkSuspender suspender;
111
112   int sumKeys = 0;
113   std::string sumValues;
114   setupBenchmark(iters);
115
116   suspender.dismissing([&]() {
117     for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
118       sumKeys += iter->first;
119       sumValues += iter->second;
120     }
121     doNotOptimizeAway(sumKeys);
122   });
123 }
124
125 BENCHMARK(ForEachFunctionAssign, iters) {
126   BenchmarkSuspender suspender;
127
128   int sumKeys = 0;
129   std::string sumValues;
130   setupBenchmark(iters);
131
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;
136       sumKeys += k;
137       sumValues += v;
138     });
139   });
140 }
141
142 BENCHMARK(StdForEachFunctionAssign, iters) {
143   BenchmarkSuspender suspender;
144
145   int sumKeys = 0;
146   std::string sumValues;
147   setupBenchmark(iters);
148
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;
153       sumKeys += k;
154       sumValues += v;
155     });
156   });
157 }
158
159 BENCHMARK(RangeBasedForLoopAssign, iters) {
160   BenchmarkSuspender suspender;
161
162   int sumKeys = 0;
163   std::string sumValues;
164   setupBenchmark(iters);
165
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;
170       sumKeys += k;
171       sumValues += v;
172     }
173   });
174 }
175
176 BENCHMARK(ManualLoopAssign, iters) {
177   BenchmarkSuspender suspender;
178
179   int sumKeys = 0;
180   std::string sumValues;
181   setupBenchmark(iters);
182
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;
187       sumKeys += k;
188       sumValues += v;
189     }
190   });
191 }
192
193 BENCHMARK(ForEachFunctionNoAssignWithIndexManipulation, iters) {
194   BenchmarkSuspender suspender;
195
196   int sumKeys = 0;
197   std::string sumValues;
198   setupBenchmark(iters);
199
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;
204       sumValues += index;
205     });
206   });
207 }
208
209 BENCHMARK(StdForEachFunctionNoAssignWithIndexManipulation, iters) {
210   BenchmarkSuspender suspender;
211
212   int sumKeys = 0;
213   std::string sumValues;
214   setupBenchmark(iters);
215
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;
221       sumValues += index;
222       ++index;
223     });
224   });
225 }
226
227 BENCHMARK(RangeBasedForLoopNoAssignWithIndexManipulation, iters) {
228   BenchmarkSuspender suspender;
229
230   int sumKeys = 0;
231   std::string sumValues;
232   setupBenchmark(iters);
233
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;
239       sumValues += index;
240     }
241   });
242 }
243
244 BENCHMARK(ForEachFunctionFetch, iters) {
245   BenchmarkSuspender suspender;
246   setupBenchmark(iters);
247
248   suspender.dismissing([&]() {
249     folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
250       folly::fetch(vec_one, index) = key_val_pair.first;
251     });
252   });
253 }
254
255 BENCHMARK(StdForEachFunctionFetch, iters) {
256   BenchmarkSuspender suspender;
257   setupBenchmark(iters);
258
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;
263     });
264   });
265 }
266
267 BENCHMARK(ForLoopFetch, iters) {
268   BenchmarkSuspender suspender;
269   setupBenchmark(iters);
270
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;
275     }
276   });
277 }
278
279 BENCHMARK(ForEachKVNoMacroAssign, iters) {
280   int sumKeys = 0;
281   std::string sumValues;
282
283   BENCHMARK_SUSPEND { setupBenchmark(iters); }
284
285   FOR_EACH(iter, bmMap) {
286     const int k = iter->first;
287     const std::string v = iter->second;
288     sumKeys += k;
289     sumValues += v;
290   }
291 }
292
293 BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
294   int sumKeys = 0;
295   std::string sumValues;
296
297   BENCHMARK_SUSPEND { setupBenchmark(iters); }
298
299   FOR_EACH(iter, bmMap) {
300     sumKeys += iter->first;
301     sumValues += iter->second;
302   }
303 }
304
305 BENCHMARK(ForEachKVMacro, iters) {
306   int sumKeys = 0;
307   std::string sumValues;
308
309   BENCHMARK_SUSPEND { setupBenchmark(iters); }
310
311   FOR_EACH_KV(k, v, bmMap) {
312     sumKeys += k;
313     sumValues += v;
314   }
315 }
316
317 BENCHMARK(ForEachManual, iters) {
318   int sum = 1;
319   for (size_t i = 1; i < iters; ++i) {
320     sum *= i;
321   }
322   doNotOptimizeAway(sum);
323 }
324
325 BENCHMARK(ForEachRange, iters) {
326   int sum = 1;
327   FOR_EACH_RANGE(i, 1, iters) { sum *= i; }
328   doNotOptimizeAway(sum);
329 }
330
331 BENCHMARK(ForEachDescendingManual, iters) {
332   int sum = 1;
333   for (size_t i = iters; i-- > 1;) {
334     sum *= i;
335   }
336   doNotOptimizeAway(sum);
337 }
338
339 BENCHMARK(ForEachRangeR, iters) {
340   int sum = 1;
341   FOR_EACH_RANGE_R(i, 1U, iters) { sum *= i; }
342   doNotOptimizeAway(sum);
343 }
344
345 BENCHMARK(CharVecForRange, iters) {
346   BENCHMARK_SUSPEND {
347     setupCharVecBenchmark(iters);
348   }
349   size_t sum = 0;
350   for (auto& c : vec_char) {
351     sum += c;
352   }
353   doNotOptimizeAway(sum);
354 }
355
356 BENCHMARK(CharVecForRangeExplicitIndex, iters) {
357   BENCHMARK_SUSPEND {
358     setupCharVecBenchmark(iters);
359   }
360   size_t sum = 0;
361   size_t index = 0;
362   for (auto& c : vec_char) {
363     sum += c * index;
364     ++index;
365   }
366   doNotOptimizeAway(sum);
367 }
368
369 BENCHMARK(CharVecForEach, iters) {
370   BENCHMARK_SUSPEND {
371     setupCharVecBenchmark(iters);
372   }
373   size_t sum = 0;
374   folly::for_each(vec_char, [&](auto& c) { sum += c; });
375   doNotOptimizeAway(sum);
376 }
377
378 BENCHMARK(CharVecForEachIndex, iters) {
379   BENCHMARK_SUSPEND {
380     setupCharVecBenchmark(iters);
381   }
382   size_t sum = 0;
383   folly::for_each(vec_char, [&](auto& c, auto index) { sum += c * index; });
384   doNotOptimizeAway(sum);
385 }
386
387 BENCHMARK(CharVecForRangeEnumerate, iters) {
388   BENCHMARK_SUSPEND {
389     setupCharVecBenchmark(iters);
390   }
391   size_t sum = 0;
392   for (auto it : enumerate(vec_char)) {
393     sum += *it * it.index;
394   }
395   doNotOptimizeAway(sum);
396 }
397
398 int main(int argc, char** argv) {
399   folly::init(&argc, &argv);
400   runBenchmarks();
401   return 0;
402 }