123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408 |
- /*
- * Copyright 2016-present Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- #include <algorithm>
- #include <map>
- #include <folly/Benchmark.h>
- #include <folly/Random.h>
- #include <folly/container/Enumerate.h>
- #include <folly/container/Foreach.h>
- #include <folly/init/Init.h>
- using namespace folly;
- using namespace folly::detail;
- // Benchmarks:
- // 1. Benchmark iterating through the man with FOR_EACH, and also assign
- // iter->first and iter->second to local vars inside the FOR_EACH loop.
- // 2. Benchmark iterating through the man with FOR_EACH, but use iter->first and
- // iter->second as is, without assigning to local variables.
- // 3. Use FOR_EACH_KV loop to iterate through the map.
- // For use in benchmarks below.
- std::map<int, std::string> bmMap;
- std::vector<int> vec_one;
- std::vector<int> vec_two;
- // Smallest type to isolate iteration overhead.
- std::vector<char> vec_char;
- void setupBenchmark(size_t iters) {
- bmMap.clear();
- for (size_t i = 0; i < iters; ++i) {
- bmMap[i] = "teststring";
- }
- vec_one.clear();
- vec_two.clear();
- vec_one.resize(iters);
- vec_two.resize(iters);
- }
- void setupCharVecBenchmark(size_t iters) {
- vec_char.resize(iters);
- std::generate(
- vec_char.begin(), vec_char.end(), [] { return Random::rand32(128); });
- }
- BENCHMARK(ForEachFunctionNoAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- });
- doNotOptimizeAway(sumKeys);
- });
- }
- BENCHMARK(StdForEachFunctionNoAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- });
- doNotOptimizeAway(sumKeys);
- });
- }
- BENCHMARK(RangeBasedForLoopNoAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- for (auto& key_val_pair : bmMap) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- }
- doNotOptimizeAway(sumKeys);
- });
- }
- BENCHMARK(ManualLoopNoAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
- sumKeys += iter->first;
- sumValues += iter->second;
- }
- doNotOptimizeAway(sumKeys);
- });
- }
- BENCHMARK(ForEachFunctionAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair) {
- const int k = key_val_pair.first;
- const std::string v = key_val_pair.second;
- sumKeys += k;
- sumValues += v;
- });
- });
- }
- BENCHMARK(StdForEachFunctionAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- const int k = key_val_pair.first;
- const std::string v = key_val_pair.second;
- sumKeys += k;
- sumValues += v;
- });
- });
- }
- BENCHMARK(RangeBasedForLoopAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- for (auto& key_val_pair : bmMap) {
- const int k = key_val_pair.first;
- const std::string v = key_val_pair.second;
- sumKeys += k;
- sumValues += v;
- }
- });
- }
- BENCHMARK(ManualLoopAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
- const int k = iter->first;
- const std::string v = iter->second;
- sumKeys += k;
- sumValues += v;
- }
- });
- }
- BENCHMARK(ForEachFunctionNoAssignWithIndexManipulation, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- sumValues += index;
- });
- });
- }
- BENCHMARK(StdForEachFunctionNoAssignWithIndexManipulation, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- sumValues += index;
- ++index;
- });
- });
- }
- BENCHMARK(RangeBasedForLoopNoAssignWithIndexManipulation, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- for (auto& key_val_pair : bmMap) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- sumValues += index;
- }
- });
- }
- BENCHMARK(ForEachFunctionFetch, iters) {
- BenchmarkSuspender suspender;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
- folly::fetch(vec_one, index) = key_val_pair.first;
- });
- });
- }
- BENCHMARK(StdForEachFunctionFetch, iters) {
- BenchmarkSuspender suspender;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- *(vec_one.begin() + index++) = key_val_pair.first;
- });
- });
- }
- BENCHMARK(ForLoopFetch, iters) {
- BenchmarkSuspender suspender;
- setupBenchmark(iters);
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- for (auto& key_val_pair : bmMap) {
- *(vec_one.begin() + index++) = key_val_pair.first;
- }
- });
- }
- BENCHMARK(ForEachKVNoMacroAssign, iters) {
- int sumKeys = 0;
- std::string sumValues;
- BENCHMARK_SUSPEND {
- setupBenchmark(iters);
- }
- FOR_EACH (iter, bmMap) {
- const int k = iter->first;
- const std::string v = iter->second;
- sumKeys += k;
- sumValues += v;
- }
- }
- BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
- int sumKeys = 0;
- std::string sumValues;
- BENCHMARK_SUSPEND {
- setupBenchmark(iters);
- }
- FOR_EACH (iter, bmMap) {
- sumKeys += iter->first;
- sumValues += iter->second;
- }
- }
- BENCHMARK(ForEachKVMacro, iters) {
- int sumKeys = 0;
- std::string sumValues;
- BENCHMARK_SUSPEND {
- setupBenchmark(iters);
- }
- FOR_EACH_KV (k, v, bmMap) {
- sumKeys += k;
- sumValues += v;
- }
- }
- BENCHMARK(ForEachManual, iters) {
- int sum = 1;
- for (size_t i = 1; i < iters; ++i) {
- sum *= i;
- }
- doNotOptimizeAway(sum);
- }
- BENCHMARK(ForEachRange, iters) {
- int sum = 1;
- FOR_EACH_RANGE (i, 1, iters) { sum *= i; }
- doNotOptimizeAway(sum);
- }
- BENCHMARK(ForEachDescendingManual, iters) {
- int sum = 1;
- for (size_t i = iters; i-- > 1;) {
- sum *= i;
- }
- doNotOptimizeAway(sum);
- }
- BENCHMARK(ForEachRangeR, iters) {
- int sum = 1;
- FOR_EACH_RANGE_R (i, 1U, iters) { sum *= i; }
- doNotOptimizeAway(sum);
- }
- BENCHMARK(CharVecForRange, iters) {
- BENCHMARK_SUSPEND {
- setupCharVecBenchmark(iters);
- }
- size_t sum = 0;
- for (auto& c : vec_char) {
- sum += c;
- }
- doNotOptimizeAway(sum);
- }
- BENCHMARK(CharVecForRangeExplicitIndex, iters) {
- BENCHMARK_SUSPEND {
- setupCharVecBenchmark(iters);
- }
- size_t sum = 0;
- size_t index = 0;
- for (auto& c : vec_char) {
- sum += c * index;
- ++index;
- }
- doNotOptimizeAway(sum);
- }
- BENCHMARK(CharVecForEach, iters) {
- BENCHMARK_SUSPEND {
- setupCharVecBenchmark(iters);
- }
- size_t sum = 0;
- folly::for_each(vec_char, [&](auto& c) { sum += c; });
- doNotOptimizeAway(sum);
- }
- BENCHMARK(CharVecForEachIndex, iters) {
- BENCHMARK_SUSPEND {
- setupCharVecBenchmark(iters);
- }
- size_t sum = 0;
- folly::for_each(vec_char, [&](auto& c, auto index) { sum += c * index; });
- doNotOptimizeAway(sum);
- }
- BENCHMARK(CharVecForRangeEnumerate, iters) {
- BENCHMARK_SUSPEND {
- setupCharVecBenchmark(iters);
- }
- size_t sum = 0;
- for (auto&& it : enumerate(vec_char)) {
- sum += *it * it.index;
- }
- doNotOptimizeAway(sum);
- }
- int main(int argc, char** argv) {
- folly::init(&argc, &argv);
- runBenchmarks();
- return 0;
- }
|