Performance of the default node allocator.

[Dhruv Matani <dhruvbird at gmx dot net>]

I have here a program that allocates lots of list node, deallocates
them, and then reallocates them. It appears that the default node
allocator fails to preserve the locality or something, and it's
performance is reflected while sorting the list, when the 2nd time is 
observered to perform much worse compared to the first (double the
time). I wonder if the allocation starategy of the default node
allocator can be changed? BTW, an allocator calling malloc and free
performs better in terms of preserving order of elements in memory.


-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/


#include <iostream>
#include <algorithm>
#include <nstl/allocator.hpp>
#include <nstl/cheap_alloc.hpp>
#include <list>
#include <deque>
#include <memory>
#include <nstl/timer.hpp>
//Get nstl form CVS@sf.net. www.sf.net/projects/nstl/

#define alloc std::allocator

template <class T>
void clear_container (T& _cont) { T temp; std::swap (temp, _cont); }

int main ()
{
  std::deque <double, alloc<double> > id;
  std::list <double, alloc<double> > il;
  int temp, x = 2;
  nstd::timer t;

  while (x--) {
  t.start ();

  for (int i = 0; i < 700000; ++i)
    {
      id.push_back (rand()%300);
      //      id.push_front (rand()%300);
      il.push_back (rand()%300);
      //      il.push_front (rand()%300);
    }
  t.stop ();

  std::cout<<"Time taken to insert: "<<t.difference()<<" Seconds."<<std::endl;

  t.start ();
  il.sort();
  t.stop ();
  std::cout<<"Time taken to sort list: "<<t.difference()<<" Seconds."<<std::endl;

  t.start ();
  //id.sort();
  std::sort (id.begin(), id.end());
  t.stop ();
  std::cout<<"Time taken to sort deque: "<<t.difference()<<" Seconds."<<std::endl;

  //Check memory usage at this point.
  std::cout<<"Enter a number to continue:";
  std::cin>>temp;

  t.start ();
  //  il.clear ();
  clear_container (il);
  t.stop ();
  std::cout<<"Time taken to clear list: "<<t.difference()<<" Seconds."<<std::endl;
 
  t.start ();
  clear_container (id);
  //  id.clear ();
  t.stop ();
  std::cout<<"Time taken to clear deque: "<<t.difference()<<" Seconds."<<std::endl;
  }

}

Attachment: op.txt
Description: Text document