folly/test/ForeachTest.cpp

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