fork download
/* 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://w...content-available-to-author-only...t.com/Articles/340797/Number-crunching-Why-you-should-never-ever-EVER-us?msg=4253843#xx4253843xx*/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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(t1 - t0);}

  milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  {return std::chrono::duration_cast(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           NumbersInList;
typedef std::vector         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 Distribution;
  static Distribution distribution;
  return distribution(engine, Distribution::param_type(low, high));
}


// Measure time in milliseconds for linear insert in a std container
template
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
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
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;
}
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