The bitmapped allocator in a standard form.

[Dhruv Matani]

I've re-organized the files, so that the bitmapped allocator can
function as a separate entity itself. In particular, there are just 2
files. Once you have those, you can use the bitmapped allocator. I have
completely separated it from NSTL. Currently, I have put the allocator
in namespace std::, but I can change that later on. I have tested the
allocator as a complete replacement to the pool allocator for std::list,
and the results show that for every operation, the time taken is lesser
than that for the default allocator. In particular, sorting, and linear
searching after sorting and clearing the container are much faster (a
few hundred order of magnitudes). I'm attaching the 2 files (balloc.hpp
and cheap_alloc.hpp), and the driver (balloc_test.hpp), and the test
resiults for the driver. Please let me know the status, and if there's
anything more I can do.


Test Results for Driver Program:

//Bit mapped Allocator
Time Taken to Insert: 0.14 Seconds.
Time Taken to Search: 0.47 Seconds.
Size is: 650000
Time Taken to Sort: 1.35 Seconds.
Time Taken to Search: 5.83 Seconds.
Size is: 631316

Time Taken to Insert: 0.14 Seconds.
Time Taken to Search: 6.32 Seconds.
Size is: 1281316
Time Taken to Sort: 2.83 Seconds.
Time Taken to Search: 11.46 Seconds.
Size is: 91650

Time Taken to Insert: 0.13 Seconds.
Time Taken to Search: 1.71 Seconds.
Size is: 741650
Time Taken to Sort: 1.57 Seconds.
Time Taken to Search: 6.26 Seconds.
Size is: 165439

3
[dhruv@home test]$ compile balloc_test.cpp -O3
[dhruv@home test]$ ./balloc_test 

//Default Node Allocator.

Time Taken to Insert: 0.15 Seconds.
Time Taken to Search: 0.6 Seconds.
Size is: 650000
Time Taken to Sort: 1.42 Seconds.
Time Taken to Search: 6.07 Seconds.
Size is: 631316

Time Taken to Insert: 0.15 Seconds.
Time Taken to Search: 6.77 Seconds.
Size is: 1281316
Time Taken to Sort: 3.07 Seconds.
Time Taken to Search: 12.85 Seconds.
Size is: 91650


Time Taken to Insert: 0.34 Seconds.
Time Taken to Search: 6.79 Seconds.
Size is: 741650
Time Taken to Sort: 2.98 Seconds.
Time Taken to Search: 7.46 Seconds.
Size is: 165439

3


NOTE: cheap_allocator<> is the same as new_allocator, except that I'm
working with the g++3.2 default STL, so the renaming has not affected
me. That's why I  do not use new_allocator or __new_alloc as the case
may be.

As of g++3.4, I'd like to know whether it compiles this particular piece
of code without errors:


//BEGIN CODE.
#include <vector>

template <typename T>
struct A {
  typedef int Type;
  typedef std::vector <T> Vec_Type;
  typedef typename Vec_Type::difference_type DType;
//g++3.2 Compiles the above line fine even without the typename, which
is probably incorrect.

  struct B {
    Type TVar;
//It seems that g++3.4 does not allow this. I tested the above code on
comeau online, and it works fine.
  };
};


int main ()
{
  A<int> Aobj;
  Aobj = Aobj;
  A<double>::B Bobj;
  Bobj = Bobj;
}
//END CODE.





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


-------------- next part --------------
A non-text attachment was scrubbed...
Name: balloc.hpp
Type: text/x-c-header
Size: 15798 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040117/d279c63e/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cheap_alloc.hpp
Type: text/x-c-header
Size: 2162 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040117/d279c63e/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: balloc_test.cpp
Type: text/x-c++
Size: 1785 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040117/d279c63e/attachment-0002.bin>