fork download
  1. /* 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.
  2.  
  3. Comparison 1: Compare LL pre-allocated vs LL non-allocated for random insertions.
  4.  
  5. Article question: "Another test you can do"
  6. http://www.codeproject.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us?msg=4253843#xx4253843xx*/
  7.  
  8. #include <list>
  9. #include <vector>
  10. #include <iostream>
  11. #include <iomanip>
  12. #include <functional>
  13. #include <random>
  14. #include <iostream>
  15. #include <chrono>
  16. #include <string>
  17. #include <numeric>
  18. #include <algorithm>
  19. #include <cassert>
  20.  
  21. namespace g2
  22. {
  23. typedef std::chrono::high_resolution_clock clock;
  24. typedef std::chrono::microseconds microseconds;
  25. typedef std::chrono::milliseconds milliseconds;
  26.  
  27. clock::time_point now(){return clock::now();}
  28.  
  29. microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  30. {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  31.  
  32. milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  33. {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  34.  
  35.  
  36. class StopWatch
  37. {
  38. clock::time_point start_;
  39. public:
  40. StopWatch() : start_(clock::now()){}
  41. clock::time_point restart() { start_ = clock::now(); return start_;}
  42. microseconds elapsedUs() { return intervalUs(now(), start_);}
  43. milliseconds elapsedMs() {return intervalMs(now(), start_);}
  44. };
  45. } // g2
  46.  
  47.  
  48. typedef unsigned int Number;
  49. typedef std::list<Number> NumbersInList;
  50. typedef std::vector<Number> NumbersInVector;
  51. typedef long long int TimeValue;
  52.  
  53.  
  54. int random_int(int low, int high)
  55. {
  56. using namespace std;
  57. static default_random_engine engine;
  58. typedef uniform_int_distribution<int> Distribution;
  59. static Distribution distribution;
  60. return distribution(engine, Distribution::param_type(low, high));
  61. }
  62.  
  63.  
  64. // Measure time in milliseconds for linear insert in a std container
  65. template<typename Container>
  66. TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
  67. {
  68. g2::StopWatch watch;
  69. {
  70. std::for_each(randoms.begin(), randoms.end(), [&](const Number& n)
  71. {
  72. auto itr = container.begin();
  73. for (; itr!= container.end(); ++itr)
  74. {
  75. if ((*itr) >= n)
  76. { break; }
  77. }
  78. container.insert(itr, n);
  79. });
  80. }
  81. auto time = watch.elapsedUs().count();
  82. return time;
  83. }
  84.  
  85. // Measure time in milliseconds for linear insert in a std container
  86. template<typename Container>
  87. TimeValue linearInsertPerformance(const NumbersInVector& randoms,
  88. Container& memory_pool_container, Container& container)
  89. {
  90. g2::StopWatch watch;
  91. {
  92. std::for_each(randoms.begin(), randoms.end(), [&](const Number& n)
  93. {
  94. auto itr = container.begin();
  95. for (; itr!= container.end(); ++itr)
  96. {
  97. if ((*itr) >= n)
  98. { break; }
  99. }
  100. auto pool_itr = memory_pool_container.begin();
  101. (*pool_itr) = n; // set the random value
  102. container.splice(itr, memory_pool_container, pool_itr); // insert value from the pool
  103. });
  104. }
  105. auto time = watch.elapsedUs().count();
  106. return time;
  107. }
  108.  
  109. // Used for debugging and verification,
  110. // normally disabled
  111. template<typename Container>
  112. void printValues(const std::string& msg, const Container& values)
  113. {
  114. std::cout << msg << std::endl;
  115. std::for_each(values.begin(), values.end(),
  116. [&](const Number& n) { std::cout << " " << n << " "; });
  117.  
  118. std::cout << "\n" << std::endl;
  119. }
  120.  
  121.  
  122.  
  123. void linked_listPerformance(size_t nbr_of_randoms)
  124. {
  125. // Generate n random values and push to storage
  126. NumbersInVector values(nbr_of_randoms);
  127. std::for_each(values.begin(), values.end(), [&](Number& n) { n = random_int(0, nbr_of_randoms -1);});
  128.  
  129. TimeValue list_time;
  130. TimeValue vector_time;
  131. TimeValue list_time_preallocated;
  132.  
  133. { // LL
  134. NumbersInList list;
  135. list_time = linearInsertPerformance(values, list);
  136. }
  137.  
  138. { // Vector
  139. NumbersInVector vector;
  140. vector_time = linearInsertPerformance(values, vector);
  141. }
  142.  
  143. { // LL - PreAllocated
  144. NumbersInList memory_pool(nbr_of_randoms, -1); // pre-allocated LL used as memory pool
  145. NumbersInList list_preallocated;
  146. list_time_preallocated = linearInsertPerformance(values, memory_pool, list_preallocated);
  147. }
  148.  
  149.  
  150.  
  151. std::cout << nbr_of_randoms << ", " << std::flush;
  152. std::cout << list_time << ", " << list_time_preallocated << ", " << vector_time << std::endl << std::flush;
  153. }
  154.  
  155.  
  156.  
  157.  
  158. int main(int argc, char** argv)
  159. {
  160. std::cout << "Pre-allocated linked-list vs linked-list" << std::endl;
  161. std::cout << "This shows how much time is actually used for memory allocations in" << std::endl;
  162. std::cout << "perspective with cost for traversing. Both lists are in disjoint memory!" << std::endl;
  163. std::cout << "\n#items, LL (us), LL pre-allocated (us) , vector (us) " << std::endl;
  164.  
  165.  
  166. g2::StopWatch watch;
  167. linked_listPerformance(10);
  168. linked_listPerformance(100);
  169. linked_listPerformance(500);
  170. linked_listPerformance(1000);
  171. linked_listPerformance(2000);
  172. linked_listPerformance(10000);
  173. linked_listPerformance(20000);
  174. linked_listPerformance(40000);
  175. linked_listPerformance(100000);
  176. linked_listPerformance(500000);
  177. linked_listPerformance(1000000);
  178.  
  179. auto total_time_ms = watch.elapsedMs().count();
  180. std::cout << "Exiting test,. the whole measuring took " << total_time_ms << " milliseconds";
  181. std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl;
  182. return 0;
  183. }
Time limit exceeded #stdin #stdout 15s 4024KB
stdin
Standard input is empty
stdout
Pre-allocated linked-list vs linked-list
This shows how much time is actually used for memory allocations in
perspective with cost for traversing. Both lists are in disjoint memory!

#items, LL (us), LL pre-allocated (us) , vector (us) 
10,  2, 1, 3
100,  11, 7, 13
500,  118, 112, 116
1000,  412, 456, 396
2000,  1471, 1780, 1461
10000,  95107, 98522, 33494
20000,  588622, 603722, 138968
40000,  3434945, 3556232, 626431