Performance of the default Node Allocator.

[Dhruv Matani <dhruvbird at gmx dot net>]

I was talking about the performance of the default node allocator in
situations where the list is sorted, and the nodes get splayed about in
memory, and then subsequent allocations/deallocations suffer due to bad
cache performance. I have here a bitmapped allocator that attempts to
remove those defects. I'm attaching a driver program that shows the
performance of the default node allocator v/s the bitmapped allocator.
You can see clearly that the bitmapped allocator not only allocates
memory faster, but also does not mess up the cache. If anyone wants the
source, I can send it by email. You can see that the sort is twice as
fast in the bitmapped allocator compared to the default node allocator
when used repeatedly. Also, could anyone test out these things for me on
other platforms?

Link to get the bitmapped allocator:
http://www.geocities.com/dhruvbird/nstl/nstl0.2.zip


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


#include <nstl/balloc.hpp>
#include <nstl/node_alloc.hpp>
#include <list>
#include <nstl/timer.hpp>
#include <cstdlib>
#include <iostream>

using namespace std;

using nstd::bitmap_allocator;


int main ()
{
  nstd::timer t;

  typedef std::list<int, bitmap_allocator<int> > My_List;

  //bitmap_allocator<int> ba;


  //  typedef std::list<int> My_List;

  //std::list<int, nstd::node_allocator<int> > il1;
  //  nstd::node_allocator<int> ba;

  My_List il1;

  int ctr = 3;
  while (ctr--)
    {

  t.start ();

  for (int i = 0; i < 550000; ++i)
    il1.push_back (rand()%10001);
    //    ba.allocate (1);
  t.stop ();

  cout<<"Time Taken to Insert: "<<t.difference()<<" Seconds."<<endl;

  My_List::iterator i = il1.begin();

  cout<<"Size is: "<<il1.size ()<<endl;

  t.start ();
  il1.sort ();
  t.stop ();

  cout<<"Time Taken to Sort: "<<t.difference()<<" Seconds."<<endl;

  //  il1.clear ();
  il1.erase (i, il1.end());

  cout<<"Size is: "<<il1.size ()<<endl<<endl;
    }


  il1.clear ();
  int x;
  cin>>x;


}