folly/test/ForeachTest.cpp

   1 /*
   2  * Copyright 2012 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/Foreach.h"
  18
  19 #include "folly/Benchmark.h"
  20 #include <gtest/gtest.h>
  21 #include <map>
  22 #include <string>
  23 #include <vector>
  24 #include <list>
  25
  26 using namespace folly;
  27 using namespace folly::detail;
  28
  29 TEST(Foreach, ForEachKV) {
  30   std::map<std::string, int> testMap;
  31   testMap["abc"] = 1;
  32   testMap["def"] = 2;
  33   std::string keys = "";
  34   int values = 0;
  35   int numEntries = 0;
  36   FOR_EACH_KV (key, value, testMap) {
  37     keys += key;
  38     values += value;
  39     ++numEntries;
  40   }
  41   EXPECT_EQ("abcdef", keys);
  42   EXPECT_EQ(3, values);
  43   EXPECT_EQ(2, numEntries);
  44 }
  45
  46 TEST(Foreach, ForEachKVBreak) {
  47   std::map<std::string, int> testMap;
  48   testMap["abc"] = 1;
  49   testMap["def"] = 2;
  50   std::string keys = "";
  51   int values = 0;
  52   int numEntries = 0;
  53   FOR_EACH_KV (key, value, testMap) {
  54     keys += key;
  55     values += value;
  56     ++numEntries;
  57     break;
  58   }
  59   EXPECT_EQ("abc", keys);
  60   EXPECT_EQ(1, values);
  61   EXPECT_EQ(1, numEntries);
  62 }
  63
  64 TEST(Foreach, ForEachKvWithMultiMap) {
  65   std::multimap<std::string, int> testMap;
  66   testMap.insert(std::make_pair("abc", 1));
  67   testMap.insert(std::make_pair("abc", 2));
  68   testMap.insert(std::make_pair("def", 3));
  69   std::string keys = "";
  70   int values = 0;
  71   int numEntries = 0;
  72   FOR_EACH_KV (key, value, testMap) {
  73     keys += key;
  74     values += value;
  75     ++numEntries;
  76   }
  77   EXPECT_EQ("abcabcdef", keys);
  78   EXPECT_EQ(6, values);
  79   EXPECT_EQ(3, numEntries);
  80 }
  81
  82 TEST(Foreach, ForEachEnumerate) {
  83   std::vector<int> vv;
  84   int sumAA = 0;
  85   int sumIter = 0;
  86   int numIterations = 0;
  87   FOR_EACH_ENUMERATE(aa, iter, vv) {
  88     sumAA += aa;
  89     sumIter += *iter;
  90     ++numIterations;
  91   }
  92   EXPECT_EQ(sumAA, 0);
  93   EXPECT_EQ(sumIter, 0);
  94   EXPECT_EQ(numIterations, 0);
  95
  96   vv.push_back(1);
  97   vv.push_back(3);
  98   vv.push_back(5);
  99   FOR_EACH_ENUMERATE(aa, iter, vv) {
 100     sumAA += aa;
 101     sumIter += *iter;
 102     ++numIterations;
 103   }
 104   EXPECT_EQ(sumAA, 3);   // 0 + 1 + 2
 105   EXPECT_EQ(sumIter, 9); // 1 + 3 + 5
 106   EXPECT_EQ(numIterations, 3);
 107 }
 108
 109 TEST(Foreach, ForEachEnumerateBreak) {
 110   std::vector<int> vv;
 111   int sumAA = 0;
 112   int sumIter = 0;
 113   int numIterations = 0;
 114   vv.push_back(1);
 115   vv.push_back(2);
 116   vv.push_back(4);
 117   vv.push_back(8);
 118   FOR_EACH_ENUMERATE(aa, iter, vv) {
 119     sumAA += aa;
 120     sumIter += *iter;
 121     ++numIterations;
 122     if (aa == 1) break;
 123   }
 124   EXPECT_EQ(sumAA, 1);   // 0 + 1
 125   EXPECT_EQ(sumIter, 3); // 1 + 2
 126   EXPECT_EQ(numIterations, 2);
 127 }
 128
 129 TEST(Foreach, ForEachRangeR) {
 130   int sum = 0;
 131
 132   FOR_EACH_RANGE_R (i, 0, 0) {
 133     sum += i;
 134   }
 135   EXPECT_EQ(0, sum);
 136
 137   FOR_EACH_RANGE_R (i, 0, -1) {
 138     sum += i;
 139   }
 140   EXPECT_EQ(0, sum);
 141
 142   FOR_EACH_RANGE_R (i, 0, 5) {
 143     sum += i;
 144   }
 145   EXPECT_EQ(10, sum);
 146
 147   std::list<int> lst = { 0, 1, 2, 3, 4 };
 148   sum = 0;
 149   FOR_EACH_RANGE_R (i, lst.begin(), lst.end()) {
 150     sum += *i;
 151   }
 152   EXPECT_EQ(10, sum);
 153 }
 154
 155 // Benchmarks:
 156 // 1. Benchmark iterating through the man with FOR_EACH, and also assign
 157 //    iter->first and iter->second to local vars inside the FOR_EACH loop.
 158 // 2. Benchmark iterating through the man with FOR_EACH, but use iter->first and
 159 //    iter->second as is, without assigning to local variables.
 160 // 3. Use FOR_EACH_KV loop to iterate through the map.
 161
 162 std::map<int, std::string> bmMap;  // For use in benchmarks below.
 163
 164 void setupBenchmark(int iters) {
 165   bmMap.clear();
 166   for (int i = 0; i < iters; ++i) {
 167     bmMap[i] = "teststring";
 168   }
 169 }
 170
 171 BENCHMARK(ForEachKVNoMacroAssign, iters) {
 172   int sumKeys = 0;
 173   std::string sumValues;
 174
 175   BENCHMARK_SUSPEND {
 176     setupBenchmark(iters);
 177     int sumKeys = 0;
 178     std::string sumValues = "";
 179   }
 180
 181   FOR_EACH (iter, bmMap) {
 182     const int k = iter->first;
 183     const std::string v = iter->second;
 184     sumKeys += k;
 185     sumValues += v;
 186   }
 187 }
 188
 189 BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
 190   int sumKeys = 0;
 191   std::string sumValues;
 192
 193   BENCHMARK_SUSPEND {
 194     setupBenchmark(iters);
 195   }
 196
 197   FOR_EACH (iter, bmMap) {
 198     sumKeys += iter->first;
 199     sumValues += iter->second;
 200   }
 201 }
 202
 203 BENCHMARK(ManualLoopNoAssign, iters) {
 204   BENCHMARK_SUSPEND {
 205     setupBenchmark(iters);
 206   }
 207   int sumKeys = 0;
 208   std::string sumValues;
 209
 210   for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
 211     sumKeys += iter->first;
 212     sumValues += iter->second;
 213   }
 214 }
 215
 216 BENCHMARK(ForEachKVMacro, iters) {
 217   BENCHMARK_SUSPEND {
 218     setupBenchmark(iters);
 219   }
 220   int sumKeys = 0;
 221   std::string sumValues;
 222
 223   FOR_EACH_KV (k, v, bmMap) {
 224     sumKeys += k;
 225     sumValues += v;
 226   }
 227 }
 228
 229 BENCHMARK(ForEachManual, iters) {
 230   int sum = 1;
 231   for (auto i = 1; i < iters; ++i) {
 232     sum *= i;
 233   }
 234   doNotOptimizeAway(sum);
 235 }
 236
 237 BENCHMARK(ForEachRange, iters) {
 238   int sum = 1;
 239   FOR_EACH_RANGE (i, 1, iters) {
 240     sum *= i;
 241   }
 242   doNotOptimizeAway(sum);
 243 }
 244
 245 BENCHMARK(ForEachDescendingManual, iters) {
 246   int sum = 1;
 247   for (auto i = iters; i-- > 1; ) {
 248     sum *= i;
 249   }
 250   doNotOptimizeAway(sum);
 251 }
 252
 253 BENCHMARK(ForEachRangeR, iters) {
 254   int sum = 1;
 255   FOR_EACH_RANGE_R (i, 1, iters) {
 256     sum *= i;
 257   }
 258   doNotOptimizeAway(sum);
 259 }
 260
 261 int main(int argc, char** argv) {
 262   testing::InitGoogleTest(&argc, argv);
 263   auto r = RUN_ALL_TESTS();
 264   if (r) {
 265     return r;
 266   }
 267   runBenchmarks();
 268   return 0;
 269 }