folly/container/test/ForeachBenchmark.cpp

   1 /*
   2  * Copyright 2017 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 <folly/container/Foreach.h>
  18
  19 #include <folly/Benchmark.h>
  20 #include <folly/portability/GTest.h>
  21
  22 #include <map>
  23
  24 using namespace folly;
  25 using namespace folly::detail;
  26
  27 // Benchmarks:
  28 // 1. Benchmark iterating through the man with FOR_EACH, and also assign
  29 //    iter->first and iter->second to local vars inside the FOR_EACH loop.
  30 // 2. Benchmark iterating through the man with FOR_EACH, but use iter->first and
  31 //    iter->second as is, without assigning to local variables.
  32 // 3. Use FOR_EACH_KV loop to iterate through the map.
  33
  34 std::map<int, std::string> bmMap; // For use in benchmarks below.
  35 std::vector<int> vec_one;
  36 std::vector<int> vec_two;
  37
  38 void setupBenchmark(size_t iters) {
  39   bmMap.clear();
  40   for (size_t i = 0; i < iters; ++i) {
  41     bmMap[i] = "teststring";
  42   }
  43
  44   vec_one.clear();
  45   vec_two.clear();
  46   vec_one.resize(iters);
  47   vec_two.resize(iters);
  48 }
  49
  50 BENCHMARK(ForEachFunctionNoAssign, iters) {
  51   BenchmarkSuspender suspender;
  52
  53   int sumKeys = 0;
  54   std::string sumValues;
  55   setupBenchmark(iters);
  56
  57   suspender.dismissing([&]() {
  58     folly::for_each(bmMap, [&](auto& key_val_pair) {
  59       sumKeys += key_val_pair.first;
  60       sumValues += key_val_pair.second;
  61     });
  62     doNotOptimizeAway(sumKeys);
  63   });
  64 }
  65
  66 BENCHMARK(StdForEachFunctionNoAssign, iters) {
  67   BenchmarkSuspender suspender;
  68
  69   int sumKeys = 0;
  70   std::string sumValues;
  71   setupBenchmark(iters);
  72
  73   suspender.dismissing([&]() {
  74     std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
  75       sumKeys += key_val_pair.first;
  76       sumValues += key_val_pair.second;
  77     });
  78     doNotOptimizeAway(sumKeys);
  79   });
  80 }
  81
  82 BENCHMARK(RangeBasedForLoopNoAssign, iters) {
  83   BenchmarkSuspender suspender;
  84   int sumKeys = 0;
  85   std::string sumValues;
  86   setupBenchmark(iters);
  87
  88   suspender.dismissing([&]() {
  89     for (auto& key_val_pair : bmMap) {
  90       sumKeys += key_val_pair.first;
  91       sumValues += key_val_pair.second;
  92     }
  93     doNotOptimizeAway(sumKeys);
  94   });
  95 }
  96
  97 BENCHMARK(ManualLoopNoAssign, iters) {
  98   BenchmarkSuspender suspender;
  99
 100   int sumKeys = 0;
 101   std::string sumValues;
 102   setupBenchmark(iters);
 103
 104   suspender.dismissing([&]() {
 105     for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
 106       sumKeys += iter->first;
 107       sumValues += iter->second;
 108     }
 109     doNotOptimizeAway(sumKeys);
 110   });
 111 }
 112
 113 BENCHMARK(ForEachFunctionAssign, iters) {
 114   BenchmarkSuspender suspender;
 115
 116   int sumKeys = 0;
 117   std::string sumValues;
 118   setupBenchmark(iters);
 119
 120   suspender.dismissing([&]() {
 121     folly::for_each(bmMap, [&](auto& key_val_pair) {
 122       const int k = key_val_pair.first;
 123       const std::string v = key_val_pair.second;
 124       sumKeys += k;
 125       sumValues += v;
 126     });
 127   });
 128 }
 129
 130 BENCHMARK(StdForEachFunctionAssign, iters) {
 131   BenchmarkSuspender suspender;
 132
 133   int sumKeys = 0;
 134   std::string sumValues;
 135   setupBenchmark(iters);
 136
 137   suspender.dismissing([&]() {
 138     std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
 139       const int k = key_val_pair.first;
 140       const std::string v = key_val_pair.second;
 141       sumKeys += k;
 142       sumValues += v;
 143     });
 144   });
 145 }
 146
 147 BENCHMARK(RangeBasedForLoopAssign, iters) {
 148   BenchmarkSuspender suspender;
 149
 150   int sumKeys = 0;
 151   std::string sumValues;
 152   setupBenchmark(iters);
 153
 154   suspender.dismissing([&]() {
 155     for (auto& key_val_pair : bmMap) {
 156       const int k = key_val_pair.first;
 157       const std::string v = key_val_pair.second;
 158       sumKeys += k;
 159       sumValues += v;
 160     }
 161   });
 162 }
 163
 164 BENCHMARK(ManualLoopAssign, iters) {
 165   BenchmarkSuspender suspender;
 166
 167   int sumKeys = 0;
 168   std::string sumValues;
 169   setupBenchmark(iters);
 170
 171   suspender.dismissing([&]() {
 172     for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
 173       const int k = iter->first;
 174       const std::string v = iter->second;
 175       sumKeys += k;
 176       sumValues += v;
 177     }
 178   });
 179 }
 180
 181 BENCHMARK(ForEachFunctionNoAssignWithIndexManipulation, iters) {
 182   BenchmarkSuspender suspender;
 183
 184   int sumKeys = 0;
 185   std::string sumValues;
 186   setupBenchmark(iters);
 187
 188   suspender.dismissing([&]() {
 189     folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
 190       sumKeys += key_val_pair.first;
 191       sumValues += key_val_pair.second;
 192       sumValues += index;
 193     });
 194   });
 195 }
 196
 197 BENCHMARK(StdForEachFunctionNoAssignWithIndexManipulation, iters) {
 198   BenchmarkSuspender suspender;
 199
 200   int sumKeys = 0;
 201   std::string sumValues;
 202   setupBenchmark(iters);
 203
 204   suspender.dismissing([&]() {
 205     auto index = std::size_t{0};
 206     std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
 207       sumKeys += key_val_pair.first;
 208       sumValues += key_val_pair.second;
 209       sumValues += index;
 210       ++index;
 211     });
 212   });
 213 }
 214
 215 BENCHMARK(RangeBasedForLoopNoAssignWithIndexManipulation, iters) {
 216   BenchmarkSuspender suspender;
 217
 218   int sumKeys = 0;
 219   std::string sumValues;
 220   setupBenchmark(iters);
 221
 222   suspender.dismissing([&]() {
 223     auto index = std::size_t{0};
 224     for (auto& key_val_pair : bmMap) {
 225       sumKeys += key_val_pair.first;
 226       sumValues += key_val_pair.second;
 227       sumValues += index;
 228     }
 229   });
 230 }
 231
 232 BENCHMARK(ForEachFunctionFetch, iters) {
 233   BenchmarkSuspender suspender;
 234   setupBenchmark(iters);
 235
 236   suspender.dismissing([&]() {
 237     folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
 238       folly::fetch(vec_one, index) = key_val_pair.first;
 239     });
 240   });
 241 }
 242
 243 BENCHMARK(StdForEachFunctionFetch, iters) {
 244   BenchmarkSuspender suspender;
 245   setupBenchmark(iters);
 246
 247   suspender.dismissing([&]() {
 248     auto index = std::size_t{0};
 249     std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
 250       *(vec_one.begin() + index++) = key_val_pair.first;
 251     });
 252   });
 253 }
 254
 255 BENCHMARK(ForLoopFetch, iters) {
 256   BenchmarkSuspender suspender;
 257   setupBenchmark(iters);
 258
 259   suspender.dismissing([&]() {
 260     auto index = std::size_t{0};
 261     for (auto& key_val_pair : bmMap) {
 262       *(vec_one.begin() + index++) = key_val_pair.first;
 263     }
 264   });
 265 }
 266
 267 BENCHMARK(ForEachKVNoMacroAssign, iters) {
 268   int sumKeys = 0;
 269   std::string sumValues;
 270
 271   BENCHMARK_SUSPEND { setupBenchmark(iters); }
 272
 273   FOR_EACH(iter, bmMap) {
 274     const int k = iter->first;
 275     const std::string v = iter->second;
 276     sumKeys += k;
 277     sumValues += v;
 278   }
 279 }
 280
 281 BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
 282   int sumKeys = 0;
 283   std::string sumValues;
 284
 285   BENCHMARK_SUSPEND { setupBenchmark(iters); }
 286
 287   FOR_EACH(iter, bmMap) {
 288     sumKeys += iter->first;
 289     sumValues += iter->second;
 290   }
 291 }
 292
 293 BENCHMARK(ForEachKVMacro, iters) {
 294   int sumKeys = 0;
 295   std::string sumValues;
 296
 297   BENCHMARK_SUSPEND { setupBenchmark(iters); }
 298
 299   FOR_EACH_KV(k, v, bmMap) {
 300     sumKeys += k;
 301     sumValues += v;
 302   }
 303 }
 304
 305 BENCHMARK(ForEachManual, iters) {
 306   int sum = 1;
 307   for (size_t i = 1; i < iters; ++i) {
 308     sum *= i;
 309   }
 310   doNotOptimizeAway(sum);
 311 }
 312
 313 BENCHMARK(ForEachRange, iters) {
 314   int sum = 1;
 315   FOR_EACH_RANGE(i, 1, iters) { sum *= i; }
 316   doNotOptimizeAway(sum);
 317 }
 318
 319 BENCHMARK(ForEachDescendingManual, iters) {
 320   int sum = 1;
 321   for (size_t i = iters; i-- > 1;) {
 322     sum *= i;
 323   }
 324   doNotOptimizeAway(sum);
 325 }
 326
 327 BENCHMARK(ForEachRangeR, iters) {
 328   int sum = 1;
 329   FOR_EACH_RANGE_R(i, 1U, iters) { sum *= i; }
 330   doNotOptimizeAway(sum);
 331 }
 332
 333 int main(int argc, char** argv) {
 334   testing::InitGoogleTest(&argc, argv);
 335   gflags::ParseCommandLineFlags(&argc, &argv, true);
 336   auto r = RUN_ALL_TESTS();
 337   if (r) {
 338     return r;
 339   }
 340   runBenchmarks();
 341   return 0;
 342 }