RFC: Sharing of memory between containers.

[Dhruv Matani <dhruvbird at gmx dot net>]

An important question that I've been confronted with is that should
different containers/the same came container with a different
parameterized type be able to share their memory using a stateless
allocator? So, it would indirectly imply that should:
allocator<int> and allocator<float> be able to share theit memory, if
the sizeof(int) == sizeof(float)?

AFAIK, the current default node allocator just allocates 16 free lists
each of size 8 bytes greater than the previous, and the first one being
8 bytes, then the request for memory is rounded up to the next highest 8
byte, and then the corresponding free list is queried for the memory.
So, there is maximum possibility of different containers using up the
same memory region. This may be bad for cache locality. Consider for
example:

list<int> il;
list<float> fl;

for (int i = 0; i < 300000; ++i)
{
	il.push_back (i);
	fl.push_back (i);
}


Each element of the each of the lists would occupy adjacent memory
addresses wrt the internal free lists in the allocator. A straight run
through would mean that double the actually required memory for that run
through would be required to be paged in/out whenever a page fault
occurs, which would now double the number of times compared to the
scheme where the memory between the 2 containers is not gotten from the
same free list:

I have attached a driver file below. You can verify the results.
The output for the file below on my mahine with -O3 is:

//For bitmap_allocator.
[dhruv@home test]$ compile locality_test.cpp -O3
[dhruv@home test]$ ./locality_test 
Time for searching Int List: 0.84 Seconds.
Time for searching Float List: 0.84 Seconds.


//For the default node allocator.
[dhruv@home test]$ compile locality_test.cpp -O3
[dhruv@home test]$ ./locality_test 
Time for searching Int List: 2.04 Seconds.
Time for searching Float List: 2.04 Seconds.
[dhruv@home test]$ 


On the other hand, you could argue that the memory is saved when the
different allocators share the memory. I'm confused on this particulat
count?

Surprisingly though, the bitmap allocator is taking up lesser memory!
Now, I'm really confused???



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


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

using namespace std;

// typedef std::list<int> int_l;
// typedef std::list<float> float_l;

typedef std::list<int, __gnu_cxx::bitmap_allocator<int> > int_l;
typedef std::list<float, __gnu_cxx::bitmap_allocator<float> > float_l;


struct Nothing {
template <typename X>
void operator() (X const&) { }
};

int main ()
{
  int_l il;
  float_l fl;
  nstd::timer t;

  for (int i = 0; i < 300000; ++i)
    {
      il.push_back (i);
      fl.push_back (i);
    }

  t.start ();
  for (int i = 0; i < 100; ++i)
    std::for_each (il.begin(), il.end(), Nothing ());
  t.stop ();

  cout<<"Time for searching Int List: "<<t.difference ()<<" Seconds."<<endl;

  t.start ();
  for (int i = 0; i < 100; ++i)
    std::for_each (fl.begin(), fl.end(), Nothing ());
  t.stop ();

  cout<<"Time for searching Float List: "<<t.difference ()<<" Seconds."<<endl;

  int x;
  cin>>x;

}