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 }