[boost] [RFC] Boost Allocators.

From: Dhruv Matani (dhruvbird_at_[hidden])
Date: 2004-01-18 00:27:22

I have a suggestion about the organization allocators in the Boost
library. There is the pool allocators in the boost/pool/ directory, and
then there are allocators lile in boost/detail/ files named:
allocator.hpp and quick_alloc.hpp. Why not just have another
boost/allocators/ folder, and put them all there? Also, it would be nice
if quick_allocator would get a standard interface. We could then test
the performance of this allocator with other standard allocators when
used with standard containers, because I believe that the allocator
performance should be mesaured not only by how fast the
allocation/deallocation happens, but also by the region of memory that
the allocator returns for use by the standard containers. For example,
the pool based allocators I have seen so far, that maintain a list of
free blocks, and use header nodes and when a block needs to be freed,
they make that as the head. So, if such allocators are used in list like
data structures, where sorting of the list can make the nodes get
splayed about in memory. So, when the list releases the memory, the
order of nodes according to their address is pretty much random, so then
next time a list tries to acquire that memory, it will cause cache
misses.

Also, I have  bitmpped allocator that tries to eliminate these very
defects. Below are the test results for a file named balloc_test.cpp,
which I have attached, in case anyone wants to test it out for
himself/herself. The 1st part of the test results are using boost/pool's
fast_pool_allocator, and the 2nd part are using my bitmap_allocator.

If there is any need for such an allocator in Boost, I can upload it to
yahoo groups.

Test Results:
[dhruv_at_home test]$ ./balloc_test 
Time Taken to Insert: 0.19 Seconds.
Time Taken to Search: 0.5 Seconds.
Size is: 650000
Time Taken to Sort: 1.46 Seconds.
Time Taken to Search: 6.33 Seconds.
Size is: 631316

Time Taken to Insert: 0.19 Seconds.
Time Taken to Search: 6.99 Seconds.
Size is: 1281316
Time Taken to Sort: 3.12 Seconds.
Time Taken to Search: 12.45 Seconds.
Size is: 91650

Time Taken to Insert: 0.34 Seconds. //Note the values from here on.
Time Taken to Search: 6.63 Seconds.
Size is: 741650
Time Taken to Sort: 2.83 Seconds.
Time Taken to Search: 7.15 Seconds.
Size is: 165439

3
[dhruv_at_home test]$ compile balloc_test.cpp -O3
[dhruv_at_home test]$ ./balloc_test 
Time Taken to Insert: 0.15 Seconds.
Time Taken to Search: 0.51 Seconds.
Size is: 650000
Time Taken to Sort: 1.46 Seconds.
Time Taken to Search: 6.32 Seconds.
Size is: 631316

Time Taken to Insert: 0.14 Seconds.
Time Taken to Search: 6.87 Seconds.
Size is: 1281316
Time Taken to Sort: 3.09 Seconds.
Time Taken to Search: 12.41 Seconds.
Size is: 91650

Time Taken to Insert: 0.15 Seconds. //Note the values from here on.
Time Taken to Search: 1.88 Seconds.
Size is: 741650
Time Taken to Sort: 1.7 Seconds.
Time Taken to Search: 6.76 Seconds.
Size is: 165439

3
[dhruv_at_home test]$ 

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