folly/test/FBVectorTestBenchmarks.cpp.h

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