Memory, Allocator<T> & __USE_MALLOC & alternatives

[Tony Bryant <brd at paradise dot net dot nz>]

I'm using libstdc++ in a small (96K ROM, ~20K usuable RAM) embedded sh-elf
project. I've just tracked down what I thought was a memory leak,
but is actually a feature.

if you allocate 1000 items of 16bytes each with std::allocator<T>, then
you've used approx 16K of memory - fair enough. 

Now free it all. 

Nothing is returned to the system heap, std::allocator<T> keeps it cached - 
as it is designed to do.

Now try to allocate 500 items of 32bytes. CRUNCH. std::allocator<T> doesn't
reuse the cached 1000 16byte chunks - it allocates a bunch more memory for 32 
byte chunks. 32K doesn't comes out of 20K - funnily enough.

Not a problem when you've got 512Mb of SDRAM and a couple of gigs of swap 
space, but for my pissy 20K system it's just not a workable solution.

OK, so the solution seems obvious - use __USE_MALLOC, which, despite being 
not the greatest performing system in the world - it produces a workable 
solution.

I've written a nice heap allocator that I've got connected to malloc/free - 
which all works fine except free doesn't tell you how big the item being 
allocated was - so I've got to waste 4 bytes per allocation. Not a huge deal 
but it does add 50% to the size of a container like list<myFoo *> (12 bytes 
per node vs 8 with the std::allocator<T> )

This heap allocator doesn't _need_ to store the size if the size will be 
known at deallocation time, and since std::allocator<T> knows what the size 
is, its just a matter of getting the size information through somehow.

What I would love to implement is an equivilent to __USE_MALLOC that allows 
me to pass the size of the block being freed to the memory allocator, called 
perhaps __USE_USER_MEMORY_ALLOCATOR - which causes the std::allocator<T> to 
just call:

extern "C" void *user_allocator_allocate(size_t);
&&
extern "C" void user_allocator_free(void *,size_t);

thread safety is left as an exercise to the implementer of these functions 
(maybe?).

I'll do the work, if there's a chance of somebody applying it to the CVS. 

Comments?