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://w...content-available-to-author-only...t.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
comments (?)
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
https://ideone.com/4hetC
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
public

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!