folly/test/stl_tests/Benchmark.cpp

   1 /*
   2  * Copyright 2014 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 // @author Nicholas Ormrod <njormrod@fb.com>
  18
  19 /******************************************************************************
  20  *
  21  * This file is not perfect - benchmarking is a finicky process.
  22  *
  23  * TAKE THE NUMBERS YOU SEE TO MIND, NOT TO HEART
  24  *
  25  *****************************************************************************/
  26
  27 #include <vector>
  28 #include "OFBVector.h"
  29 #define FOLLY_BENCHMARK_USE_NS_IFOLLY
  30 #include "folly/FBVector.h"
  31
  32 #include <chrono>
  33 #include <deque>
  34 #include <iomanip>
  35 #include <iostream>
  36 #include <locale>
  37 #include <memory>
  38 #include <string>
  39
  40 #include <boost/preprocessor.hpp>
  41
  42 using namespace std;
  43
  44 static const bool enableColors = true;
  45
  46 //=============================================================================
  47 // use the timestamp counter for time measurements
  48
  49 static inline
  50 void clear_icache() {} // placeholder
  51
  52 // return the CPU timestamp counter
  53 static uint64_t readTSC() {
  54    unsigned reslo, reshi;
  55
  56    __asm__ __volatile__  (
  57    "xorl %%eax,%%eax \n cpuid \n"
  58     ::: "%eax", "%ebx", "%ecx", "%edx");
  59    __asm__ __volatile__  (
  60    "rdtsc\n"
  61     : "=a" (reslo), "=d" (reshi) );
  62    __asm__ __volatile__  (
  63    "xorl %%eax,%%eax \n cpuid \n"
  64     ::: "%eax", "%ebx", "%ecx", "%edx");
  65
  66    return ((uint64_t)reshi << 32) | reslo;
  67 }
  68
  69 //=============================================================================
  70 // Timer
  71
  72 // The TIME* macros expand to a sequence of functions and classes whose aim
  73 //  is to run a benchmark function several times with different types and
  74 //  sizes.
  75 //
  76 // The first and last thing that TIME* expands to is a function declaration,
  77 //  through the DECL macro. The declared function is templated on the full
  78 //  vector type, its value_type, its allocator_type, and a number N.
  79 // The first DECL is a forward declaration, and is followed by a
  80 //  semicolon. The second DECL ends the macro - a function body is to be
  81 //  supplied after the macro invocation.
  82 // The declared function returns a uint64_t, which is assumed to be a time.
  83 //
  84 // The GETTER macro calls the DECL function repeatedly. It returns the
  85 //  minimum time taken to execute DECL. GETTER runs DECL between 2 and 100
  86 //  times (it will not run the full 100 if the tests take a long time).
  87 //
  88 // The EVALUATOR macro calls the GETTER macro with each of std::vector,
  89 //  the original fbvector (folly::fbvector), and the new fbvector
  90 //  (Ifolly::fbvector). It runs all three twice, and then calls the
  91 //  pretty printer to display the results. Before calling the pretty
  92 //  printer, the EVALUATOR outputs the three message strings.
  93 //
  94 // The EXECUTOR macro calls the EVALUATOR with different values of N.
  95 //  It also defines the string message for N.
  96 //
  97 // The RUNNER macro defines a struct. That struct defines the testname
  98 //  string. The constructor calls the EXECUTOR with each test type, and
  99 //  also defines the test type string.
 100 // The RUNNER class is also instantiated, so the constructor will be run
 101 //  before entering main().
 102 //
 103
 104 #define TIME(str, types)    TIME_I(str, types, (0))
 105 #define TIME_N(str, types)  TIME_I(str, types, (0)(16)(64)(1024)(16384)(262144))
 106
 107 #define TIME_I(str, types, values) \
 108   TIME_II(str, BOOST_PP_CAT(t_, __LINE__), types, values)
 109
 110 #define TIME_II(str, name, types, values) \
 111   DECL(name);                             \
 112   GETTER(name)                            \
 113   EVALUATOR(name)                         \
 114   EXECUTOR(name, values)                  \
 115   RUNNER(str, name, types)                \
 116   DECL(name)
 117
 118 #define DECL(name)                                                \
 119   template <class Vector, typename T, typename Allocator, int N>  \
 120   static inline uint64_t BOOST_PP_CAT(run_, name) ()
 121
 122 #define GETTER(name)                                                          \
 123   template <class Vector, int N>                                              \
 124   static uint64_t BOOST_PP_CAT(get_, name) () {                               \
 125     auto s = chrono::high_resolution_clock::now();                            \
 126     uint64_t minticks = ~uint64_t(0);                                         \
 127     int burst = 0;                                                            \
 128     for (; burst < 100; ++burst) {                                            \
 129       auto t = BOOST_PP_CAT(run_, name) <Vector,                              \
 130         typename Vector::value_type, typename Vector::allocator_type, N> ();  \
 131       minticks = min(minticks, t);                                            \
 132       if (minticks * burst > 10000000) break;                                 \
 133     }                                                                         \
 134     auto e = chrono::high_resolution_clock::now();                            \
 135     chrono::nanoseconds d(e - s);                                             \
 136     return minticks;                                                          \
 137     return d.count() / burst;                                                 \
 138   }
 139
 140 #define EVALUATOR(name)                                                       \
 141   template <typename T, typename Allocator, int N>                            \
 142   void BOOST_PP_CAT(evaluate_, name)                                          \
 143   ( string& part1, string& part2, string& part3 ) {                           \
 144     cout << setw(25) << left << part1                                         \
 145          << setw(4) << left << part2                                          \
 146          << setw(6) << right << part3;                                        \
 147     part1.clear(); part2.clear(); part3.clear();                              \
 148     auto v1 = BOOST_PP_CAT(get_, name)                                        \
 149       <Ifolly::fbvector<T, Allocator>, N> ();                                 \
 150     auto v2 = BOOST_PP_CAT(get_, name)                                        \
 151       < folly::fbvector<T, Allocator>, N> ();                                 \
 152     auto v3 = BOOST_PP_CAT(get_, name)                                        \
 153       <   std::  vector<T, Allocator>, N> ();                                 \
 154     auto v1b = BOOST_PP_CAT(get_, name)                                       \
 155       <Ifolly::fbvector<T, Allocator>, N> ();                                 \
 156     auto v2b = BOOST_PP_CAT(get_, name)                                       \
 157       < folly::fbvector<T, Allocator>, N> ();                                 \
 158     auto v3b = BOOST_PP_CAT(get_, name)                                       \
 159       <   std::  vector<T, Allocator>, N> ();                                 \
 160     prettyPrint(min(v1, v1b), min(v2, v2b), min(v3, v3b));                    \
 161     cout << endl;                                                             \
 162   }
 163
 164 #define EXECUTOR(name, values)                                                \
 165   template <typename T, typename Allocator>                                   \
 166   void BOOST_PP_CAT(execute_, name) ( string& part1, string& part2 ) {        \
 167     BOOST_PP_SEQ_FOR_EACH(EVALUATE, name, values)                             \
 168   }
 169
 170 #define EVALUATE(r, name, value)                                              \
 171   { string part3(BOOST_PP_STRINGIZE(value));                                  \
 172     BOOST_PP_CAT(evaluate_, name) <T, Allocator, value>                       \
 173     ( part1, part2, part3 ); }
 174
 175 #define RUNNER(str, name, types)                                              \
 176   struct BOOST_PP_CAT(Runner_, name) {                                        \
 177     BOOST_PP_CAT(Runner_, name) () {                                          \
 178       string part1(str);                                                      \
 179       BOOST_PP_SEQ_FOR_EACH(EXECUTE, (part1, name), types)                    \
 180     }                                                                         \
 181   } BOOST_PP_CAT(runner_, name);
 182
 183 #define EXECUTE(r, pn, type)                                                  \
 184   { string part2(BOOST_PP_STRINGIZE(type));                                   \
 185     BOOST_PP_CAT(execute_, BOOST_PP_TUPLE_ELEM(2, 1, pn))                     \
 186     <typename type::first_type, typename type::second_type>                   \
 187     ( BOOST_PP_TUPLE_ELEM(2, 0, pn), part2 ); }
 188
 189 //=============================================================================
 190 // pretty printer
 191
 192 // The pretty printer displays the times for each of the three vectors.
 193 // The fastest time (or times, if there is a tie) is highlighted in green.
 194 // Additionally, if the new fbvector (time v1) is not the fastest, then
 195 //  it is highlighted with red or blue. It is highlighted with blue only
 196 //  if it lost by a small margin (5 clock cycles or 2%, whichever is
 197 //  greater).
 198
 199 void prettyPrint(uint64_t v1, uint64_t v2, uint64_t v3) {
 200   // rdtsc takes some time to run; about 157 clock cycles
 201   // if we see a smaller positive number, adjust readtsc
 202   uint64_t readtsc_time = 157;
 203   if (v1 != 0 && v1 < readtsc_time) readtsc_time = v1;
 204   if (v2 != 0 && v2 < readtsc_time) readtsc_time = v2;
 205   if (v3 != 0 && v3 < readtsc_time) readtsc_time = v3;
 206
 207   if (v1 == 0) v1 = ~uint64_t(0); else v1 -= readtsc_time;
 208   if (v2 == 0) v2 = ~uint64_t(0); else v2 -= readtsc_time;
 209   if (v3 == 0) v3 = ~uint64_t(0); else v3 -= readtsc_time;
 210
 211   auto least = min({ v1, v2, v3 });
 212   // a good time is less than 2% or 5 clock cycles slower
 213   auto good = max(least + 5, (uint64_t)(least * 1.02));
 214
 215   string w("\x1b[1;;42m"); // green
 216   string g("\x1b[1;;44m"); // blue
 217   string b("\x1b[1;;41m"); // red
 218   string e("\x1b[0m");     // reset
 219
 220   if (!enableColors) {
 221     w = b = e = "";
 222   }
 223
 224   cout << " ";
 225
 226   if (v1 == least) cout << w;
 227   else if (v1 <= good) cout << g;
 228   else cout << b;
 229   cout << setw(13) << right;
 230   if (v1 == ~uint64_t(0)) cout << "-"; else cout << v1;
 231   cout << " "  << e << " ";
 232
 233   if (v2 == least) cout << w;
 234   cout << setw(13) << right;
 235   if (v2 == ~uint64_t(0)) cout << "-"; else cout << v2;
 236   cout << " " << e << " ";
 237
 238   if (v3 == least) cout << w;
 239   cout << setw(13) << right;
 240   if (v3 == ~uint64_t(0)) cout << "-"; else cout << v3;
 241   cout << " " << e << " ";
 242 }
 243
 244 //=============================================================================
 245 // table formatting
 246
 247 // Much like the TIME macros, the Leader and Line struct/macros
 248 //  instantiate a class before main, and work is done inside the
 249 //  constructors. The Leader and Line struct print out pretty
 250 //  table boundaries and titles.
 251
 252 uint64_t leader_elapsed() {
 253   static auto t = chrono::high_resolution_clock::now();
 254   chrono::nanoseconds d(chrono::high_resolution_clock::now() - t);
 255   return d.count() / 1000000000;
 256 }
 257
 258 struct Leader {
 259   Leader() {
 260     leader_elapsed();
 261     std::cout.imbue(std::locale(""));
 262
 263     cout << endl;
 264     cout << "========================================"
 265          << "========================================" << endl;
 266     cout << setw(35) << left << "Test";
 267     cout << setw(15) << right << "new fbvector ";
 268     cout << setw(15) << right << "old fbvector ";
 269     cout << setw(15) << right << "std::vector ";
 270     cout << endl;
 271     cout << "========================================"
 272          << "========================================" << endl;
 273   }
 274   ~Leader() {
 275     cout << endl;
 276     cout << "========================================"
 277          << "========================================" << endl;
 278     cout << setw(78) << right << leader_elapsed() << " s" << endl;
 279   }
 280 } leader;
 281
 282 struct Line {
 283   explicit Line(string text) {
 284     cout << "\n--- " << text  << " ---" << endl;
 285   }
 286 };
 287 #define SECTION(str) Line BOOST_PP_CAT(l_, __LINE__) ( str )
 288
 289 //=============================================================================
 290 // Test types
 291
 292 typedef pair<int, std::allocator<int>> T1;
 293 typedef pair<vector<int>, std::allocator<vector<int>>> T2;
 294
 295 uint64_t v1_T1 = 0, v2_T1 = 0, v3_T1 = 0;
 296 uint64_t v1_T2 = 0, v2_T2 = 0, v3_T2 = 0;
 297
 298 #define BASICS (T1)(T2)
 299
 300 //=============================================================================
 301 // prevent optimizing
 302
 303 std::vector<int> O_vi(10000000);
 304
 305 void O(int i) {
 306   O_vi.push_back(i);
 307 }
 308 template <class V>
 309 void O(const V& v) {
 310   int s = v.size();
 311   for (int i = 0; i < s; ++i) O(v[i]);
 312 }
 313
 314 //=============================================================================
 315 // Benchmarks
 316
 317 // #if 0
 318 //-----------------------------------------------------------------------------
 319 //SECTION("Dev");
 320 //#undef BASICS
 321 //#define BASICS (T1)
 322
 323
 324 // #else
 325
 326 //-----------------------------------------------------------------------------
 327 SECTION("Essentials");
 328
 329 TIME_N("~Vector()", BASICS) {
 330   Vector a(N);
 331   O(a);
 332   clear_icache(); auto b = readTSC();
 333   a.~Vector();
 334   auto e = readTSC();
 335   new (&a) Vector();
 336   O(a);
 337   return e - b;
 338 }
 339
 340 TIME_N("a.clear()", BASICS) {
 341   Vector a(N);
 342   O(a);
 343   clear_icache(); auto b = readTSC();
 344   a.clear();
 345   auto e = readTSC();
 346   O(a);
 347   return e - b;
 348 }
 349
 350 TIME("Vector u", BASICS) {
 351   clear_icache(); auto b = readTSC();
 352   Vector u;
 353   auto e = readTSC();
 354   O(u);
 355   return e - b;
 356 }
 357
 358 TIME_N("Vector u(a)", BASICS) {
 359   static const Vector a(N);
 360   clear_icache(); auto b = readTSC();
 361   Vector u(a);
 362   auto e = readTSC();
 363   O(u);
 364   return e - b;
 365 }
 366
 367 TIME_N("Vector u(move(a))", BASICS) {
 368   Vector a(N);
 369   clear_icache(); auto b = readTSC();
 370   Vector u(move(a));
 371   auto e = readTSC();
 372   O(u);
 373   return e - b;
 374 }
 375
 376 //-----------------------------------------------------------------------------
 377 SECTION("Constructors");
 378
 379 TIME_N("Vector u(n)", BASICS) {
 380   clear_icache(); auto b = readTSC();
 381   Vector u(N);
 382   auto e = readTSC();
 383   O(u);
 384   return e - b;
 385 }
 386
 387 TIME_N("Vector u(n, t)", BASICS) {
 388   static const T t(1);
 389   clear_icache(); auto b = readTSC();
 390   Vector u(N, t);
 391   auto e = readTSC();
 392   O(u);
 393   return e - b;
 394 }
 395
 396 TIME_N("Vector u(first, last)", BASICS) {
 397   static const deque<T> d(N);
 398   clear_icache(); auto b = readTSC();
 399   Vector u(d.begin(), d.end());
 400   auto e = readTSC();
 401   O(u);
 402   return e - b;
 403 }
 404
 405 //-----------------------------------------------------------------------------
 406 SECTION("Assignment");
 407
 408 TIME_N("a = b", BASICS) {
 409   Vector a(N);
 410   static const Vector c(N/2 + 10);
 411   O(a);
 412   clear_icache(); auto b = readTSC();
 413   a = c;
 414   auto e = readTSC();
 415   O(a);
 416   return e - b;
 417 }
 418
 419 TIME_N("a = move(b)", BASICS) {
 420   Vector a(N);
 421   Vector c(N/2 + 10);
 422   O(a);
 423   O(c);
 424   clear_icache(); auto b = readTSC();
 425   a = move(c);
 426   auto e = readTSC();
 427   O(a);
 428   O(c);
 429   return e - b;
 430 }
 431
 432 TIME_N("a = destructive_move(b)", BASICS) {
 433   Vector a(N);
 434   Vector c(N/2 + 10);
 435   O(a);
 436   O(c);
 437   clear_icache(); auto b = readTSC();
 438   a = move(c);
 439   c.clear();
 440   auto e = readTSC();
 441   O(a);
 442   O(c);
 443   return e - b;
 444 }
 445
 446 TIME_N("a.assign(N, t)", BASICS) {
 447   Vector a(N/2 + 10);
 448   const T t(1);
 449   O(a);
 450   clear_icache(); auto b = readTSC();
 451   a.assign(N, t);
 452   auto e = readTSC();
 453   O(a);
 454   return e - b;
 455 }
 456
 457 TIME_N("a.assign(first, last)", BASICS) {
 458   static const deque<T> d(N);
 459   Vector a(N/2 + 10);
 460   clear_icache(); auto b = readTSC();
 461   a.assign(d.begin(), d.end());
 462   auto e = readTSC();
 463   O(a);
 464   return e - b;
 465 }
 466
 467 TIME_N("a.swap(b)", BASICS) {
 468   Vector a(N/2 + 10);
 469   Vector c(N);
 470   O(a);
 471   O(c);
 472   clear_icache(); auto b = readTSC();
 473   a.swap(c);
 474   auto e = readTSC();
 475   O(a);
 476   O(c);
 477   return e - b;
 478 }
 479
 480 //-----------------------------------------------------------------------------
 481 SECTION("Iterators");
 482
 483 TIME("a.begin()", BASICS) {
 484   static Vector a(1);
 485   clear_icache(); auto b = readTSC();
 486   auto r = a.begin();
 487   auto e = readTSC();
 488   O(*r);
 489   return e - b;
 490 }
 491
 492 TIME("a.cbegin()", BASICS) {
 493   static Vector a(1);
 494   clear_icache(); auto b = readTSC();
 495   auto r = a.cbegin();
 496   auto e = readTSC();
 497   O(*r);
 498   return e - b;
 499 }
 500
 501 TIME("a.rbegin()", BASICS) {
 502   static Vector a(1);
 503   clear_icache(); auto b = readTSC();
 504   auto r = a.rbegin();
 505   auto e = readTSC();
 506   O(*r);
 507   return e - b;
 508 }
 509
 510 //-----------------------------------------------------------------------------
 511 SECTION("Capacity");
 512
 513 TIME_N("a.size()", BASICS) {
 514   static const Vector a(N);
 515   clear_icache(); auto b = readTSC();
 516   int n = a.size();
 517   auto e = readTSC();
 518   O(n);
 519   return e - b;
 520 }
 521
 522 TIME("a.max_size()", BASICS) {
 523   static Vector a;
 524   clear_icache(); auto b = readTSC();
 525   int n = a.max_size();
 526   auto e = readTSC();
 527   O(n);
 528   return e - b;
 529 }
 530
 531 TIME_N("a.capacity()", BASICS) {
 532   static const Vector a(N);
 533   clear_icache(); auto b = readTSC();
 534   int n = a.capacity();
 535   auto e = readTSC();
 536   O(n);
 537   return e - b;
 538 }
 539
 540 TIME_N("a.empty()", BASICS) {
 541   static const Vector a(N);
 542   clear_icache(); auto b = readTSC();
 543   int n = a.empty();
 544   auto e = readTSC();
 545   O(n);
 546   return e - b;
 547 }
 548
 549 TIME_N("reserve(n)", BASICS) {
 550   Vector u;
 551   O(u);
 552   clear_icache(); auto b = readTSC();
 553   u.reserve(N);
 554   auto e = readTSC();
 555   O(u);
 556   return e - b;
 557 }
 558
 559 TIME_N("resize(n)", BASICS) {
 560   Vector u;
 561   O(u);
 562   clear_icache(); auto b = readTSC();
 563   u.resize(N);
 564   auto e = readTSC();
 565   O(u);
 566   return e - b;
 567 }
 568
 569 TIME_N("resize(n, t)", BASICS) {
 570   static const T t(1);
 571   Vector u;
 572   O(u);
 573   clear_icache(); auto b = readTSC();
 574   u.resize(N, t);
 575   auto e = readTSC();
 576   O(u);
 577   return e - b;
 578 }
 579
 580 TIME("staged reserve", BASICS) {
 581   Vector u;
 582   O(u);
 583   clear_icache(); auto b = readTSC();
 584   u.reserve(500);
 585   u.reserve(1000);
 586   auto e = readTSC();
 587   O(u);
 588   return e - b;
 589 }
 590
 591 TIME("staged resize", BASICS) {
 592   Vector u;
 593   O(u);
 594   clear_icache(); auto b = readTSC();
 595   u.resize(500);
 596   u.resize(1000);
 597   auto e = readTSC();
 598   O(u);
 599   return e - b;
 600 }
 601
 602 TIME("resize then reserve", BASICS) {
 603   Vector u;
 604   O(u);
 605   clear_icache(); auto b = readTSC();
 606   u.resize(500);
 607   u.reserve(1000);
 608   auto e = readTSC();
 609   O(u);
 610   return e - b;
 611 }
 612
 613 TIME("shrink", BASICS) {
 614   Vector u;
 615   O(u);
 616   u.resize(500);
 617   u.reserve(1000);
 618   clear_icache(); auto b = readTSC();
 619   u.shrink_to_fit();
 620   auto e = readTSC();
 621   O(u);
 622   return e - b;
 623 }
 624
 625 //-----------------------------------------------------------------------------
 626 SECTION("Access");
 627
 628 TIME("operator[]", BASICS) {
 629   static const Vector a(10);
 630   clear_icache(); auto b = readTSC();
 631   const auto& v = a[8];
 632   auto e = readTSC();
 633   O(v);
 634   return e - b;
 635 }
 636
 637 TIME("at()", BASICS) {
 638   static const Vector a(10);
 639   clear_icache(); auto b = readTSC();
 640   const auto& v = a.at(8);
 641   auto e = readTSC();
 642   O(v);
 643   return e - b;
 644 }
 645
 646 TIME("front()", BASICS) {
 647   static const Vector a(10);
 648   clear_icache(); auto b = readTSC();
 649   const auto& v = a.front();
 650   auto e = readTSC();
 651   O(v);
 652   return e - b;
 653 }
 654
 655 TIME("back()", BASICS) {
 656   static const Vector a(10);
 657   clear_icache(); auto b = readTSC();
 658   const auto& v = a.back();
 659   auto e = readTSC();
 660   O(v);
 661   return e - b;
 662 }
 663
 664 TIME("data()", BASICS) {
 665   static const Vector a(10);
 666   clear_icache(); auto b = readTSC();
 667   const auto& v = a.data();
 668   auto e = readTSC();
 669   O(*v);
 670   return e - b;
 671 }
 672
 673 //-----------------------------------------------------------------------------
 674 SECTION("Append");
 675
 676 TIME("reserved emplace", BASICS) {
 677   Vector u;
 678   u.reserve(1);
 679   O(u);
 680   clear_icache(); auto b = readTSC();
 681   u.emplace_back(0);
 682   auto e = readTSC();
 683   O(u);
 684   return e - b;
 685 }
 686
 687 TIME("full emplace", BASICS) {
 688   Vector u;
 689   O(u);
 690   clear_icache(); auto b = readTSC();
 691   u.emplace_back(0);
 692   auto e = readTSC();
 693   O(u);
 694   return e - b;
 695 }
 696
 697 TIME("reserved push_back", BASICS) {
 698   static T t(0);
 699   Vector u;
 700   u.reserve(1);
 701   O(u);
 702   clear_icache(); auto b = readTSC();
 703   u.push_back(t);
 704   auto e = readTSC();
 705   O(u);
 706   return e - b;
 707 }
 708
 709 TIME("full push_back", BASICS) {
 710   static T t(0);
 711   Vector u;
 712   O(u);
 713   clear_icache(); auto b = readTSC();
 714   u.push_back(t);
 715   auto e = readTSC();
 716   O(u);
 717   return e - b;
 718 }
 719
 720 TIME("reserved push_back&&", BASICS) {
 721   T t(0);
 722   Vector u;
 723   u.reserve(1);
 724   O(u);
 725   clear_icache(); auto b = readTSC();
 726   u.push_back(std::move(t));
 727   auto e = readTSC();
 728   O(u);
 729   return e - b;
 730 }
 731
 732 TIME("full push_back&&", BASICS) {
 733   T t(0);
 734   Vector u;
 735   O(u);
 736   clear_icache(); auto b = readTSC();
 737   u.push_back(std::move(t));
 738   auto e = readTSC();
 739   O(u);
 740   return e - b;
 741 }
 742
 743 TIME("reserved push emplace", BASICS) {
 744   Vector u;
 745   u.reserve(1);
 746   O(u);
 747   clear_icache(); auto b = readTSC();
 748   u.push_back(T(0));
 749   auto e = readTSC();
 750   O(u);
 751   return e - b;
 752 }
 753
 754 TIME("full push emplace", BASICS) {
 755   Vector u;
 756   O(u);
 757   clear_icache(); auto b = readTSC();
 758   u.push_back(T(0));
 759   auto e = readTSC();
 760   O(u);
 761   return e - b;
 762 }
 763
 764 TIME_N("bulk append", BASICS) {
 765   static deque<T> d(N);
 766   Vector u(N/2 + 10);
 767   O(u);
 768   clear_icache(); auto b = readTSC();
 769   u.insert(u.end(), d.begin(), d.end());
 770   auto e = readTSC();
 771   O(u);
 772   return e - b;
 773 }
 774
 775 TIME_N("erase end", BASICS) {
 776   Vector u(N);
 777   O(u);
 778   auto it = u.begin();
 779   it += u.size() / 2;
 780   if (it != u.end()) O(*it);
 781   clear_icache(); auto b = readTSC();
 782   u.erase(it, u.end());
 783   auto e = readTSC();
 784   O(u);
 785   return e - b;
 786 }
 787
 788 TIME("pop_back", BASICS) {
 789   Vector u(1);
 790   O(u);
 791   clear_icache(); auto b = readTSC();
 792   u.pop_back();
 793   auto e = readTSC();
 794   O(u);
 795   return e - b;
 796 }
 797
 798 //-----------------------------------------------------------------------------
 799 SECTION("Insert/Erase - Bad Ops");
 800
 801 TIME("insert", BASICS) {
 802   Vector u(100);
 803   T t(1);
 804   auto it = u.begin();
 805   it += 50;
 806   O(u);
 807   O(*it);
 808   O(t);
 809   clear_icache(); auto b = readTSC();
 810   u.insert(it, t);
 811   auto e = readTSC();
 812   O(u);
 813   return e - b;
 814 }
 815
 816 TIME("insert&&", BASICS) {
 817   Vector u(100);
 818   T t(1);
 819   auto it = u.begin();
 820   it += 50;
 821   O(u);
 822   O(*it);
 823   O(t);
 824   clear_icache(); auto b = readTSC();
 825   u.insert(it, std::move(t));
 826   auto e = readTSC();
 827   O(u);
 828   return e - b;
 829 }
 830
 831 TIME("insert n few", BASICS) {
 832   Vector u(100);
 833   T t(1);
 834   auto it = u.begin();
 835   it += 50;
 836   O(u);
 837   O(*it);
 838   O(t);
 839   clear_icache(); auto b = readTSC();
 840   u.insert(it, 10, t);
 841   auto e = readTSC();
 842   O(u);
 843   return e - b;
 844 }
 845
 846 TIME("insert n many", BASICS) {
 847   Vector u(100);
 848   T t(1);
 849   auto it = u.begin();
 850   it += 50;
 851   O(u);
 852   O(*it);
 853   O(t);
 854   clear_icache(); auto b = readTSC();
 855   u.insert(it, 200, t);
 856   auto e = readTSC();
 857   O(u);
 858   return e - b;
 859 }
 860
 861 TIME("iterator insert few", BASICS) {
 862   static deque<T> d(10);
 863   Vector u(100);
 864   T t(1);
 865   auto it = u.begin();
 866   it += 50;
 867   O(u);
 868   O(*it);
 869   O(t);
 870   clear_icache(); auto b = readTSC();
 871   u.insert(it, d.begin(), d.end());
 872   auto e = readTSC();
 873   O(u);
 874   return e - b;
 875 }
 876
 877 TIME("iterator insert many", BASICS) {
 878   static deque<T> d(200);
 879   Vector u(100);
 880   T t(1);
 881   auto it = u.begin();
 882   it += 50;
 883   O(u);
 884   O(*it);
 885   O(t);
 886   clear_icache(); auto b = readTSC();
 887   u.insert(it, d.begin(), d.end());
 888   auto e = readTSC();
 889   O(u);
 890   return e - b;
 891 }
 892
 893 TIME("erase", BASICS) {
 894   Vector u(100);
 895   O(u);
 896   auto it = u.begin();
 897   it += 50;
 898   O(*it);
 899   clear_icache(); auto b = readTSC();
 900   u.erase(it);
 901   auto e = readTSC();
 902   O(u);
 903   return e - b;
 904 }
 905
 906 TIME("erase many", BASICS) {
 907   Vector u(100);
 908   O(u);
 909   auto it1 = u.begin();
 910   it1 += 33;
 911   O(*it1);
 912   auto it2 = u.begin();
 913   it2 += 66;
 914   O(*it2);
 915   clear_icache(); auto b = readTSC();
 916   u.erase(it1, it2);
 917   auto e = readTSC();
 918   O(u);
 919   return e - b;
 920 }
 921
 922 //-----------------------------------------------------------------------------
 923 SECTION("Large Tests");
 924
 925 TIME_N("reserved bulk push_back", BASICS) {
 926   Vector u;
 927   u.reserve(N);
 928   T t(0);
 929   O(u);
 930   clear_icache(); auto b = readTSC();
 931   for (int i = 0; i < N; ++i) u.emplace_back(t);
 932   auto e = readTSC();
 933   O(u);
 934   return e - b;
 935 }
 936
 937 TIME_N("reserved bulk emplace", BASICS) {
 938   Vector u;
 939   u.reserve(N);
 940   O(u);
 941   clear_icache(); auto b = readTSC();
 942   for (int i = 0; i < N; ++i) u.emplace_back(0);
 943   auto e = readTSC();
 944   O(u);
 945   return e - b;
 946 }
 947
 948 TIME_N("populate", BASICS) {
 949   static T t(0);
 950   Vector u;
 951   O(u);
 952   clear_icache(); auto b = readTSC();
 953   for (int i = 0; i < N; ++i) u.push_back(t);
 954   auto e = readTSC();
 955   O(u);
 956   return e - b;
 957 }
 958
 959 TIME("jigsaw growth", BASICS) {
 960   int sizes[] =
 961     { 1, 5, 2, 80, 17, 8, 9, 8, 140, 130, 1000, 130, 10000, 0, 8000, 2000 };
 962   clear_icache(); auto b = readTSC();
 963   Vector u;
 964   for (auto s : sizes) {
 965     if (s < u.size()) {
 966       int toAdd = u.size() - s;
 967       for (int i = 0; i < toAdd / 2; ++i) u.emplace_back(0);
 968       u.insert(u.end(), (toAdd + 1) / 2, T(1));
 969     } else {
 970       int toRm = u.size() - s;
 971       for (int i = 0; i < toRm / 2; ++i) u.pop_back();
 972       auto it = u.begin();
 973       std::advance(it, s);
 974       if (it < u.end()) u.erase(it, u.end());
 975     }
 976   }
 977   auto e = readTSC();
 978   O(u);
 979   return e - b;
 980 }
 981
 982 TIME("random access and modify", (T1)) {
 983   static const int n = 1024 * 1024 * 16;
 984   Vector u(n);
 985   O(u);
 986   clear_icache(); auto b = readTSC();
 987   int j = 7;
 988   for (int i = 0; i < 100000; ++i) {
 989     j = (j * 2 + j) ^ 0xdeadbeef;
 990     j = j & (n - 1);
 991     u[j] = i;
 992     u.at(n - j) = -i;
 993   }
 994   auto e = readTSC();
 995   O(u);
 996   return e - b;
 997 }
 998
 999 TIME_N("iterate", (T1)) {
1000   static Vector u(N);
1001   O(u);
1002   clear_icache(); auto b = readTSC();
1003   int acc = 0;
1004   for (auto& e : u) {
1005     acc += e;
1006     e++;
1007   }
1008   auto e = readTSC();
1009   O(acc);
1010   O(u);
1011   return e - b;
1012 }
1013
1014 TIME("emplace massive", BASICS) {
1015   clear_icache(); auto b = readTSC();
1016   Vector u;
1017   for (int i = 0; i < 10000000; ++i) {
1018     u.emplace_back(0);
1019   }
1020   auto e = readTSC();
1021   O(u);
1022   return e - b;
1023 }
1024
1025 // #endif
1026
1027 //=============================================================================
1028
1029 int main() {
1030   return 0;
1031 }
1032