folly/test/FBVectorTestBenchmarks.cpp.h

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