folly/test/FBVectorTestBenchmarks.cpp.h

   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 /**
  18  * This file is supposed to be included from within
  19  * FBVectorTest. Do not use otherwise.
  20  */
  21
  22 TESTFUN(clause_23_3_6_1_1) {
  23   VECTOR v;
  24   EXPECT_TRUE(v.empty());
  25   VECTOR::allocator_type a;
  26   VECTOR v1(a);
  27   EXPECT_TRUE(v1.empty());
  28 }
  29
  30 TESTFUN(clause_23_3_6_1_3) {
  31   auto const n = random(0U, 10000U);
  32   VECTOR v(n);
  33   EXPECT_EQ(v.size(), n);
  34   FOR_EACH (i, v) {
  35     EXPECT_EQ(*i, VECTOR::value_type());
  36   }
  37 }
  38
  39 TESTFUN(clause_23_3_6_1_9) {
  40   // Insert with iterators
  41   list<VECTOR::value_type> lst;
  42   auto const n = random(0U, 10000U);
  43   FOR_EACH_RANGE (i, 0, n) {
  44     lst.push_back(randomObject<VECTOR::value_type>());
  45   }
  46   VECTOR v(lst.begin(), lst.end());
  47   EXPECT_EQ(v.size(), lst.size());
  48   size_t j = 0;
  49   FOR_EACH (i, lst) {
  50     EXPECT_EQ(v[j], *i);
  51     j++;
  52   }
  53 }
  54
  55 TESTFUN(clause_23_3_6_1_11) {
  56   // assign with iterators
  57   list<VECTOR::value_type> lst;
  58   auto const n = random(0U, 10000U);
  59   FOR_EACH_RANGE (i, 0, n) {
  60     lst.push_back(randomObject<VECTOR::value_type>());
  61   }
  62   VECTOR v;
  63   v.assign(lst.begin(), lst.end());
  64   EXPECT_EQ(v.size(), lst.size());
  65   size_t j = 0;
  66   FOR_EACH (i, lst) {
  67     EXPECT_EQ(v[j], *i);
  68     j++;
  69   }
  70
  71   // aliased assign
  72   v.assign(v.begin(), v.begin() + v.size() / 2);
  73   EXPECT_EQ(v.size(), lst.size() / 2);
  74   j = 0;
  75   FOR_EACH (i, lst) {
  76     if (j == v.size()) break;
  77     EXPECT_EQ(v[j], *i);
  78     j++;
  79   }
  80 }
  81
  82 TESTFUN(clause_23_3_6_1_12) {
  83   VECTOR v;
  84   auto const n = random(0U, 10000U);
  85   auto const obj = randomObject<VECTOR::value_type>();
  86   v.assign(n, obj);
  87   EXPECT_EQ(v.size(), n);
  88   FOR_EACH (i, v) {
  89     EXPECT_EQ(*i, obj);
  90   }
  91 }
  92
  93 TESTFUN(clause_23_3_6_2_1) {
  94   VECTOR v;
  95   auto const n = random(0U, 10000U);
  96   v.reserve(n);
  97   EXPECT_GE(v.capacity(), n);
  98 }
  99
 100 TESTFUN(clause_23_3_6_2_7) {
 101   auto const n1 = random(0U, 10000U);
 102   auto const n2 = random(0U, 10000U);
 103   auto const obj1 = randomObject<VECTOR::value_type>();
 104   auto const obj2 = randomObject<VECTOR::value_type>();
 105   VECTOR v1(n1, obj1), v2(n2, obj2);
 106   v1.swap(v2);
 107   EXPECT_EQ(v1.size(), n2);
 108   EXPECT_EQ(v2.size(), n1);
 109   FOR_EACH (i, v1) {
 110     EXPECT_EQ(*i, obj2);
 111   }
 112   FOR_EACH (i, v2) {
 113     EXPECT_EQ(*i, obj1);
 114   }
 115 }
 116
 117 TESTFUN(clause_23_3_6_2_9) {
 118   VECTOR v;
 119   auto const n1 = random(0U, 10000U);
 120   v.resize(n1);
 121   FOR_EACH (i, v) {
 122     EXPECT_EQ(*i, VECTOR::value_type());
 123   }
 124   FOR_EACH (i, v) {
 125     EXPECT_EQ(*i, VECTOR::value_type());
 126   }
 127 }
 128
 129 TESTFUN(clause_23_3_6_2_11) {
 130   VECTOR v;
 131   auto const n1 = random(0U, 10000U);
 132   auto const obj1 = randomObject<VECTOR::value_type>();
 133   v.resize(n1, obj1);
 134   FOR_EACH (i, v) {
 135     EXPECT_EQ(*i, obj1);
 136   }
 137   auto const n2 = random(0U, 10000U);
 138   auto const obj2 = randomObject<VECTOR::value_type>();
 139   v.resize(n2, obj2);
 140   if (n1 < n2) {
 141     FOR_EACH_RANGE (i, n1, n2) {
 142       EXPECT_EQ(v[i], obj2);
 143     }
 144   }
 145 }
 146
 147 TESTFUN(clause_absent_element_access) {
 148   VECTOR v;
 149   auto const n1 = random(1U, 10000U);
 150   auto const obj1 = randomObject<VECTOR::value_type>();
 151   v.resize(n1, obj1);
 152   auto const n = random(0U, v.size() - 1);
 153   EXPECT_EQ(v[n], v.at(n));
 154   auto const obj2 = randomObject<VECTOR::value_type>();
 155   v[n] = obj2;
 156   EXPECT_EQ(v[n], v.at(n));
 157   EXPECT_EQ(v[n], obj2);
 158   auto const obj3 = randomObject<VECTOR::value_type>();
 159   v.at(n) = obj3;
 160   EXPECT_EQ(v[n], v.at(n));
 161   EXPECT_EQ(v[n], obj3);
 162 }
 163
 164 TESTFUN(clause_23_3_6_3_1) {
 165   VECTOR v;
 166   auto const n1 = random(1U, 10000U);
 167   auto const obj1 = randomObject<VECTOR::value_type>();
 168   v.resize(n1, obj1);
 169   EXPECT_EQ(v.data(), &v.front());
 170 }
 171
 172 TESTFUN(clause_23_3_6_4_1_a) {
 173   VECTOR v, w;
 174   auto const n1 = random(1U, 10000U);
 175   FOR_EACH_RANGE (i, 0, n1) {
 176     auto const obj1 = randomObject<VECTOR::value_type>();
 177     v.push_back(obj1);
 178     w.push_back(obj1);
 179   }
 180   auto const n2 = random(0U, n1 - 1);
 181   auto pos = v.begin() + n2;
 182   auto const obj2 = randomObject<VECTOR::value_type>();
 183
 184   auto r = v.insert(pos, obj2);
 185
 186   EXPECT_EQ(v.size(), w.size() + 1);
 187   EXPECT_EQ(r - v.begin(), n2);
 188   EXPECT_EQ(*r, obj2);
 189   FOR_EACH_RANGE (i, 0, r - v.begin()) {
 190     EXPECT_EQ(v[i], w[i]);
 191   }
 192   FOR_EACH_RANGE (i, r - v.begin() + 1, v.size()) {
 193     EXPECT_EQ(v[i], w[i - 1]);
 194   }
 195 }
 196
 197 TESTFUN(clause_23_3_6_4_1_c) {
 198   // This test only works for fbvector
 199   fbvector<VECTOR::value_type> v, w;
 200   auto const n1 = random(1U, 10000U);
 201   FOR_EACH_RANGE (i, 0, n1) {
 202     auto const obj1 = randomObject<VECTOR::value_type>();
 203     v.push_back(obj1);
 204     w.push_back(obj1);
 205   }
 206   auto const n2 = random(0U, n1-1);
 207   auto pos = v.begin() + n2;
 208   auto const obj2 = randomObject<VECTOR::value_type>();
 209   auto const n3 = random(0U, 10000U);
 210
 211   auto r = v.insert(pos, n3, obj2);
 212
 213   EXPECT_EQ(v.size(), w.size() + n3);
 214   EXPECT_EQ(r - v.begin(), n2);
 215   FOR_EACH_RANGE (i, 0, r - v.begin()) {
 216     EXPECT_EQ(v[i], w[i]);
 217   }
 218   FOR_EACH_RANGE (i, r - v.begin(), r - v.begin() + n3) {
 219     EXPECT_EQ(v[i], obj2);
 220   }
 221   FOR_EACH_RANGE (i, r - v.begin() + n3, v.size()) {
 222     EXPECT_EQ(v[i], w[i - n3]);
 223   }
 224 }
 225
 226 TESTFUN(clause_23_3_6_4_1_d) {
 227   VECTOR v, w;
 228   auto const n1 = random(0U, 10000U);
 229   FOR_EACH_RANGE (i, 0, n1) {
 230     auto const obj1 = randomObject<VECTOR::value_type>();
 231     v.push_back(obj1);
 232     w.push_back(obj1);
 233   }
 234   EXPECT_EQ(v.size(), n1);
 235
 236   auto const obj2 = randomObject<VECTOR::value_type>();
 237   v.push_back(obj2);
 238   EXPECT_EQ(v.back(), obj2);
 239   EXPECT_EQ(v.size(), w.size() + 1);
 240
 241   FOR_EACH_RANGE (i, 0, w.size()) {
 242     EXPECT_EQ(v[i], w[i]);
 243   }
 244 }
 245
 246 TESTFUN(clause_23_3_6_4_3) {
 247   VECTOR v, w;
 248   auto const n1 = random(1U, 10000U);
 249   FOR_EACH_RANGE (i, 0, n1) {
 250     auto const obj1 = randomObject<VECTOR::value_type>();
 251     v.push_back(obj1);
 252     w.push_back(obj1);
 253   }
 254   EXPECT_EQ(v.size(), n1);
 255
 256   auto const n2 = random(0U, n1 - 1);
 257   auto it = v.erase(v.begin() + n2);
 258   EXPECT_EQ(v.size() + 1, w.size());
 259
 260   FOR_EACH_RANGE (i, 0, it - v.begin()) {
 261     EXPECT_EQ(v[i], w[i]);
 262   }
 263
 264   FOR_EACH_RANGE (i, it - v.begin(), v.size()) {
 265     EXPECT_EQ(v[i], w[i + 1]);
 266   }
 267 }
 268
 269 TESTFUN(clause_23_3_6_4_4) {
 270   VECTOR v, w;
 271   auto const n1 = random(1U, 10000U);
 272   FOR_EACH_RANGE (i, 0, n1) {
 273     auto const obj1 = randomObject<VECTOR::value_type>();
 274     v.push_back(obj1);
 275     w.push_back(obj1);
 276   }
 277   EXPECT_EQ(v.size(), n1);
 278
 279   auto const n2 = random(0U, n1 - 1);
 280   auto const n3 = random(n2, n1 - 1);
 281   auto it = v.erase(v.begin() + n2, v.begin() + n3);
 282   EXPECT_EQ(v.size() + (n3 - n2), w.size());
 283
 284   FOR_EACH_RANGE (i, 0, it - v.begin()) {
 285     EXPECT_EQ(v[i], w[i]);
 286   }
 287
 288   FOR_EACH_RANGE (i, it - v.begin(), v.size()) {
 289     EXPECT_EQ(v[i], w[i + (n3 - n2)]);
 290   }
 291 }
 292
 293 TESTFUN(clause_23_3_6_4_clear) {
 294   VECTOR v;
 295   v.clear();
 296   EXPECT_TRUE(v.empty());
 297   v.resize(random(0U, 10000U));
 298   auto c = v.capacity();
 299   v.clear();
 300   EXPECT_TRUE(v.empty());
 301   EXPECT_EQ(v.capacity(), c);
 302 }
 303
 304 BENCHMARK(BENCHFUN(zzInitRNG)) {
 305   //LOG(INFO) << "\nTesting with type " << typeid(VECTOR).name() << "\n";
 306   srand(seed);
 307 }
 308
 309 BENCHMARK(BENCHFUN(defaultCtor), iters) {
 310   FOR_EACH_RANGE (i, 0, iters) {
 311     VECTOR v[4096];
 312     doNotOptimizeAway(&v);
 313   }
 314 }
 315
 316 void BENCHFUN(sizeCtor)(int iters, int size) {
 317   FOR_EACH_RANGE (i, 0, iters) {
 318     VECTOR v(size);
 319     doNotOptimizeAway(&v);
 320   }
 321 }
 322 BENCHMARK_PARAM(BENCHFUN(sizeCtor), 128);
 323 BENCHMARK_PARAM(BENCHFUN(sizeCtor), 1024);
 324 BENCHMARK_PARAM(BENCHFUN(sizeCtor), 1048576);
 325
 326 void BENCHFUN(fillCtor)(int iters, int size) {
 327   FOR_EACH_RANGE (i, 0, iters) {
 328     VECTOR v(size_t(size), randomObject<VECTOR::value_type>());
 329     doNotOptimizeAway(&v);
 330   }
 331 }
 332 BENCHMARK_PARAM(BENCHFUN(fillCtor), 128);
 333 BENCHMARK_PARAM(BENCHFUN(fillCtor), 1024);
 334 BENCHMARK_PARAM(BENCHFUN(fillCtor), 10240);
 335
 336 void BENCHFUN(pushBack)(int iters, int size) {
 337   auto const obj = randomObject<VECTOR::value_type>();
 338   FOR_EACH_RANGE (i, 0, iters) {
 339     VECTOR v;
 340     FOR_EACH_RANGE (j, 0, size) {
 341       v.push_back(obj);
 342     }
 343   }
 344 }
 345 BENCHMARK_PARAM(BENCHFUN(pushBack), 128);
 346 BENCHMARK_PARAM(BENCHFUN(pushBack), 1024);
 347 BENCHMARK_PARAM(BENCHFUN(pushBack), 10240);
 348 BENCHMARK_PARAM(BENCHFUN(pushBack), 102400);
 349 BENCHMARK_PARAM(BENCHFUN(pushBack), 512000);
 350
 351 void BENCHFUN(reserve)(int iters, int /* size */) {
 352   auto const obj = randomObject<VECTOR::value_type>();
 353   VECTOR v(random(0U, 10000U), obj);
 354   FOR_EACH_RANGE (i, 0, iters) {
 355     v.reserve(random(0U, 100000U));
 356   }
 357 }
 358 BENCHMARK_PARAM(BENCHFUN(reserve), 128);
 359 BENCHMARK_PARAM(BENCHFUN(reserve), 1024);
 360 BENCHMARK_PARAM(BENCHFUN(reserve), 10240);
 361
 362 void BENCHFUN(insert)(int iters, int /* size */) {
 363   auto const obj1 = randomObject<VECTOR::value_type>();
 364   auto const obj2 = randomObject<VECTOR::value_type>();
 365   VECTOR v(random(0U, 1U), obj1);
 366   FOR_EACH_RANGE (i, 0, iters / 100) {
 367     v.insert(v.begin(), obj2);
 368   }
 369 }
 370 BENCHMARK_PARAM(BENCHFUN(insert), 100);
 371
 372 void BENCHFUN(erase)(int iters, int /* size */) {
 373   auto const obj1 = randomObject<VECTOR::value_type>();
 374   VECTOR v(random(0U, 100U), obj1);
 375   FOR_EACH_RANGE (i, 0, iters) {
 376     if (v.empty()) continue;
 377     v.erase(v.begin());
 378   }
 379 }
 380 BENCHMARK_PARAM(BENCHFUN(erase), 1024);