language: C++11 (gcc-4.7.2)
date: 397 days 20 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

/* From @waleri, suggestions of Article improvement by adding a test to discover how much memory allocations drag-down the linked-list (LL). LL does memory allocations for every node, compared to vector that does it in chunks. 
 
Comparison 1: Compare LL pre-allocated vs LL non-allocated for random insertions.
 
Article question: "Another test you can do"
http://www.codeproject.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us?msg=4253843#xx4253843xx*/
 
#include <list>
#include <vector>
#include <iostream>
#include <iomanip>
#include <functional>
#include <random>
#include <iostream>
#include <chrono>
#include <string>
#include <numeric>
#include <algorithm>
#include <cassert>
 
namespace g2
{       
  typedef std::chrono::high_resolution_clock clock;
  typedef std::chrono::microseconds microseconds;
  typedef std::chrono::milliseconds milliseconds;
 
  clock::time_point now(){return clock::now();}
 
  microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  {return std::chrono::duration_cast<microseconds>(t1 - t0);}
 
  milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
 
 
  class StopWatch
  {
    clock::time_point start_;
  public:
    StopWatch() : start_(clock::now()){}
    clock::time_point restart()         { start_ = clock::now(); return start_;}
    microseconds elapsedUs()            { return intervalUs(now(), start_);}
    milliseconds elapsedMs()            {return intervalMs(now(), start_);}
  };
} // g2
 
 
typedef unsigned int  Number;
typedef std::list<Number>           NumbersInList;
typedef std::vector<Number>         NumbersInVector;
typedef long long int               TimeValue;
 
 
int random_int(int low, int high)
{
  using namespace std;
  static default_random_engine engine;
  typedef uniform_int_distribution<int> Distribution;
  static Distribution distribution;
  return distribution(engine, Distribution::param_type(low, high));
}
 
 
// Measure time in milliseconds for linear insert in a std container
template<typename Container>
TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
{
    g2::StopWatch watch;
    {
       std::for_each(randoms.begin(), randoms.end(), [&](const Number& n)
       {
         auto itr = container.begin();
         for (; itr!= container.end(); ++itr)
         {
            if ((*itr) >= n)
            {  break; }
        }
        container.insert(itr, n);
    });
    }
    auto time = watch.elapsedUs().count();
    return time;
}
 
// Measure time in milliseconds for linear insert in a std container
template<typename Container>
TimeValue linearInsertPerformance(const NumbersInVector& randoms, 
                                  Container& memory_pool_container,  Container& container)
{
    g2::StopWatch watch;
    {
       std::for_each(randoms.begin(), randoms.end(), [&](const Number& n)
       {
         auto itr = container.begin();
         for (; itr!= container.end(); ++itr)
         {
            if ((*itr) >= n)
            {  break; }
        }
        auto pool_itr = memory_pool_container.begin();
        (*pool_itr) = n; // set the random value
        container.splice(itr, memory_pool_container, pool_itr); // insert value from the pool
    });
    }
    auto time = watch.elapsedUs().count();
    return time;
}
 
// Used for debugging and verification, 
// normally disabled
template<typename Container>
void printValues(const std::string& msg, const Container& values)
{
  std::cout << msg << std::endl;
  std::for_each(values.begin(), values.end(),
    [&](const Number& n) { std::cout << " " << n << " "; }); 
 
  std::cout << "\n" << std::endl;
}
 
 
 
void linked_listPerformance(size_t nbr_of_randoms)
{
  // Generate n random values and push to storage
  NumbersInVector     values(nbr_of_randoms);
  std::for_each(values.begin(), values.end(), [&](Number& n) { n = random_int(0, nbr_of_randoms -1);}); 
 
  TimeValue list_time;
  TimeValue vector_time;  
  TimeValue list_time_preallocated;
 
  { // LL
    NumbersInList   list;
    list_time = linearInsertPerformance(values, list);
  }
 
  { // Vector
    NumbersInVector    vector; 
    vector_time = linearInsertPerformance(values, vector); 
  }
 
  { // LL - PreAllocated
    NumbersInList   memory_pool(nbr_of_randoms, -1); // pre-allocated LL used as memory pool
    NumbersInList   list_preallocated;
    list_time_preallocated = linearInsertPerformance(values, memory_pool, list_preallocated);
  }
 
  
 
  std::cout << nbr_of_randoms << ",  " << std::flush;
  std::cout << list_time << ", " << list_time_preallocated << ", " << vector_time << std::endl << std::flush;
}
 
 
 
 
int main(int argc, char** argv)
{ 
  std::cout << "Pre-allocated linked-list vs linked-list" << std::endl;
  std::cout << "This shows how much time is actually used for memory allocations in" << std::endl;
  std::cout << "perspective with cost for traversing. Both lists are in disjoint memory!" << std::endl;
  std::cout << "\n#items, LL (us), LL pre-allocated (us) , vector (us) " << std::endl;
 
 
  g2::StopWatch watch;
  linked_listPerformance(10);
  linked_listPerformance(100);
  linked_listPerformance(500);
  linked_listPerformance(1000);
  linked_listPerformance(2000);
  linked_listPerformance(10000);
  linked_listPerformance(20000);
  linked_listPerformance(40000);
  linked_listPerformance(100000);
  linked_listPerformance(500000);
  linked_listPerformance(1000000);
 
  auto total_time_ms = watch.elapsedMs().count();
  std::cout << "Exiting test,. the whole measuring took " << total_time_ms << " milliseconds";
  std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl; 
   return 0;
}