fork(1) download
copy 
  1. #include <algorithm>
  2. #include <chrono>
  3. #include <random>
  4. #include <list>
  5. #include <iostream>
  6. #include <vector>
  7.  
  8. template <typename T> void orderedInsert(T &List, int Elem) {
  9.   auto Iter = std::lower_bound(List.begin(), List.end(), Elem);
  10.   List.insert(Iter, Elem);
  11. }
  12.  
  13. template <typename T> void orderedDelete(T &List, int Elem) {
  14.   // Finds the first thing greater than or equal to Elem.
  15.   auto Iter = std::lower_bound(List.begin(), List.end(), Elem);
  16.   if (Iter != List.end() && *Iter == Elem)
  17.     List.erase(Iter);
  18. }
  19.  
  20. // Ensure that inling doesn't play with things...
  21. template <typename T> __attribute__((noinline)) void touchElems(T &List) {
  22.   volatile int *Ptr;
  23.   for (int &I : List) {
  24.     Ptr = &I;
  25.     // Compilers can't kill volatile ops ;)
  26.     *Ptr;
  27.   }
  28. }
  29.  
  30. // Ensure that inling doesn't play with things...
  31. template <typename T>
  32. __attribute__((noinline)) void runTest(T &__restrict__ List,
  33.                                        const std::vector<int> &ToInsert) {
  34.   for (int I : ToInsert)
  35.     orderedInsert(List, I);
  36.  
  37.   for (int I : ToInsert)
  38.     orderedDelete(List, I);
  39. }
  40.  
  41. using BenchDuration = std::chrono::duration<double, std::ratio<1, 1000>>;
  42. template <typename T> BenchDuration timeIt(const T &Fn) {
  43.   using Clock = std::chrono::high_resolution_clock;
  44.   auto Start = Clock::now();
  45.   Fn();
  46.   return Clock::now() - Start;
  47. }
  48.  
  49. template <typename Iter> void printRange(Iter Start, Iter End) {
  50.   std::cout << '[';
  51.   bool First = true;
  52.   for (auto I = Start; I != End; ++I) {
  53.     if (!First)
  54.       std::cout << ", ";
  55.     else
  56.       First = false;
  57.     std::cout << I->count() << "ms";
  58.   }
  59.   std::cout << ']';
  60. }
  61.  
  62. int main() {
  63.   constexpr int NumElems = 5000;
  64.   constexpr int NumOps = 5000;
  65.   constexpr int NumRuns = 5;
  66.   std::vector<int> Numbers(NumElems);
  67.   std::list<int> NumbersList;
  68.  
  69.   for (unsigned I = 0, E = NumElems; I != E; ++I) {
  70.     Numbers[I] = I * 2;
  71.     NumbersList.push_back(I * 2);
  72.   }
  73.  
  74.   std::vector<int> Ops(NumOps);
  75.   std::mt19937 RNG;
  76.   int UpperBound = Numbers.back();
  77.   for (int &I : Ops)
  78.     I = RNG() % UpperBound;
  79.  
  80.   std::vector<BenchDuration> VecTimes(NumRuns);
  81.   for (auto &Time : VecTimes) {
  82.     touchElems(Numbers);
  83.     touchElems(Ops);
  84.     Time = timeIt([&] { runTest(Numbers, Ops); });
  85.   }
  86.  
  87.   std::vector<BenchDuration> ListTimes(NumRuns);
  88.   for (auto &Time : ListTimes) {
  89.     touchElems(NumbersList);
  90.     touchElems(Ops);
  91.     Time = timeIt([&] { runTest(NumbersList, Ops); });
  92.   }
  93.  
  94.   std::cout << "Vec times: ";
  95.   printRange(VecTimes.begin(), VecTimes.end());
  96.   std::cout << '\n';
  97.  
  98.   std::cout << "List times: ";
  99.   printRange(ListTimes.begin(), ListTimes.end());
  100.   std::cout << '\n';
  101. }
Success #stdin #stdout 1.82s 3616KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Vec times: [24.1408ms, 23.9955ms, 23.9232ms, 24.0374ms, 24.0676ms]
List times: [317.4ms, 343.228ms, 351.455ms, 348.614ms, 347.833ms]
https://ideone.com/Af1t3p
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!