Thoughts on memory allocation...

[Stefan Olsson]

Hi all!

Remember a couple of questions raised a few weeks ago related to the 
libstdc++ allocators and ideas on improvements etc?

Back then I was thinking of just writing down all the ideas, so I set 
out to read up on the subject and try to understand what others have 
done, what might be useful or not and ended up with a nice little heap 
of paper (Yes, I do like to read some stuff of paper still...) on my 
desk. Just writing it all down into a new document seemed somewhat 
redundant to what others have done so many times so I made a few design 
decisions:

- Try to do as few system (i.e. malloc) calls as possible to gain 
similar performance across various platforms.

- Since most of our applications are long running ones (application 
servers and such) keep the heap growth (due to fragmentation etc) to a 
minimum.

- Don't bother about memory consumption if needed to accomplish the 
previous task (I don't like to waste memory, but on the targets that we 
are working on memory is not that much of an issue).

- Improve thread concurrency

- "Solve" the "one thread allocates and anotherone freeing" memory issue 
that I discussed earlier (i.e. what happens when keeping a cache of data 
in a MT application)

After figuring out how to implement this (in terms of integrating with 
libstdc++) i decided to make a header and implementation file that is 
linked into the application to solve the "one instance" issue of having 
actual code in .h files (I'm sure there is a much better way of doing 
much of the implementation here, but once again: this is posted for 
discussion...) and then tell the containers to use this by wrapping it 
through the __allocator<> adapter available in stl_alloc.h (i.e. vector< 
int, __allocator< void, nn4us::nn4us_alloc > > foo;)

Oki, the source is obviously the best documentation (?) but here are 
some comments...
nn4us_alloc.hpp:

- There seems to something "missing" in the __allocator<> code since I 
had to add the operator == and != in order to get basic_string<> to 
compile, this does however not happen if I try to compile with 
malloc_allocator which is part of stl_alloc.h - why I don't know...

- There are defintions for new and delete as well...
...as I said above, this piece of code is here for discussion and the 
best way I could think of to get an entire application to behave similar 
on several plattforms as well as minimizing heap growth was to have new 
and delete use the same allocator as the containers.

nn4us_alloc.cpp
- The allocator gets chunks (CHUNK_SIZE) of memory from the system.

- Each size (up to the predetermined MAX_BYTES) are delt with by the 
allocator, the rest is sent to malloc()/free() directly.

- All requests are rounded to powers of two - even the ones that are 
larger than MAX_BYTES in order to minimize fragmentation in malloc() 
freelists.

- Each size (power of two) has it's own list of records and it's own 
mutex. This is done to improve concurrency (i.e. two requests of 
diffrent sizes can be delt with without locking if the threads already 
owns a record). What might seem as counterproductive to this is the 
malloc_mutex which actually syncronizes all malloc() calls...
...once again this is done for testing and was added after reading a 
paper on the Linux malloc() implementation that states "To reduce lock 
contention, ptmalloc searchs for the first unlocked subheap and grabs 
memory from it to fulfill a malloc() request. If ptmalloc doesnt find an 
unlocked heap, it creates a new one." (A very interesting read: 
http://www.citi.umich.edu/techreports/reports/citi-tr-00-5.pdf). My 
interpertation, and the goal with this experiment was to see if 
"helping" malloc() to avoid creating new heap would improve 
overall/longterm performance.

- All records are initially "owned" by a fiction thread id 0 (each 
thread is assigned a unique id by setting a key. BTW Does anyone know 
what the posix standard says about assigning the id returned by 
pthread_self()? I have tried to find this but with no luck and the 
source code did not make any sense to me...) When a thread requests 
memory the owner on this record is set to this thread id which means 
that subsequent deallocate calls can be done without locking the list 
and later on reused without locking. The "trick" with this is that we 
can now see if the thread that is deallocating the memory also was 
allocating it - if not we lock and return it to thread id 0 which 
effectively reduces the problems of "unbounded heap growth" with the 
current pthread_alloc implementation.

- In order to use the same set of methods as well as memory, the new and 
delete calls rely on the size being part of the actual data...
...see the implementation - it does not make much sense to write more 
about it here ;-)

NOTE! Some of the comments in the source may be a bit confusing since 
some parts have been rewritten a couple of times for testing ;-)

So where did this leave us? Well we have done quite a few tests, both on 
our real applications and on small testprograms. It seems that the goals 
where obtained even though this rough implementation does leave a lot to 
be tuned (see below) and fixed - but our main problem (fragmentation 
over time and the inabillity to use the __default_alloc_template due to 
concatenation) has more or less completly vanished and a small 
testprogram (which creates 10 threads, each of which are inserting 
values into a map<int,int> and then clearing the map over and over) 
shows that with malloc_allocator as index 1, the default 
(__default_alloc_template) allocator gains less than 10% on both single 
and dual processor x86 machines whilst this implementation improves 
performance with well over 100% on single processor machines and even 
more on dual processor machines...

Things that needs to be looked into is obviously cacheline behaviour etc 
but I thought I post this now and see if anyone find this of interest at 
all? I feel that some of the ideas (which aren't new but still...) could 
be added to the existing allocators to reduce fragmentation (i.e. fized 
size/power of two) in libstdc++ based applications...

Looking forward to your comments!

Brgds

/Stefan

-- 
Life is like a 10 speed bicycle.  Most of us have gears we never use.

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: nn4us_alloc.hpp
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20020627/22a9bf74/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: nn4us_alloc.cpp
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20020627/22a9bf74/attachment-0001.ksh>