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