RFC on mt_allocator.h

[Stefan Olsson <stefan at xapa dot se>]

Hi all,

the attached textfile is a summary of the ideas and questions that we 
would like to get comments on in order to write a new version of 
mt_allocator.h

Brgds

/Stefan
        Request for comments on further development of mt_allocator.h
        -------------------------------------------------------------

Introduction
------------
The MT allocator has quite a few things that can be improved. Back when
we first developed it was only used in one specific application in order
to solve an issue of fragmentation over time in a multithreaded application.

However since then we have used it ourselfs and, I hope, others in various 
applications and found that there are indeed an endless number of needs and
that brings us to the topic of this rfc; what should be added to this 
allocator - and how - in order to make it useful for a broader range of
applications?

All of the items below can be implemented fairly easy and will be implemented
based on the comments that we hope to receive. 
The main issue is how to set these values/settings since they are "global" 
and cannot be passed as arguments but rather must be set at compile time 
(using defines, commandline options, functions to be called - I don't know) 
or at startup using some env variables?

Item 1
------
The original application used a pool of worker threads. They are created once 
and then uses/frees memory every now and then but they always hold a certain
amount of memory - a number that is used in order to determine if to release 
it back to the treads own freelist or the "global" freelist in order to avoid 
that all memory is consumed (i.e. one thread needs lots of memory for one 
specific task, that memory is then returned to that thread's freelist and can 
never be reused by other threads).

At a bare minimum one should be able to set the "threshold" on how much 
"excess memory" each thread may hold on it's freelist(s). As of right now that
value is fixed to 10% (i.e. If a thread is using 10000 32-byte blocks, it may 
hold up to 1000 blocks on that freelist).

Item 2
------
When dealing with consumer/producer application (and of course in pool based 
as well - it's just less obvious) the approach described above is hurting 
performance if the thread never returns memory (such as most of the testcases
that hits the maillist from time to time) or is using very little "base memory".
Until the thread has allocated AND freed memory, each call will cause a global
thread lock since the allocator will grab memory from the global list.

One approach to improve this behaviour and to minimize global locking would
be to allocate chunks of memory directly to threads if the own freelist is
empty. Today, if the threads own freelist is empty the global freelist for
that size is locked, a block removed from this list, the global list is 
unlocked and the memory is returned. When there are no free blocks in the 
global list either, a chunk of memory is allocated and a new list is created
within that memory (based on the blocksize). With this change, if a threads
freelist for a certain blocksize was empty, a chunk of memory would be 
allocated by that thread, a list created and the memory returned. Subsequent
requests could then be satisfied without locking.

Q: Should this new behaviour be a parameter (on/off) since it could potentially
   use up more memory?

Item 3
------
If item 2 is implemented, it's somewhat more likely that there is more 
memory on the freelists when the thread dies than before but the question 
is already here - should all memory be returned to the global list when 
the thread dies or should there be a option allowing memory (i.e. freelists)
to "linger" on dead thread id's. The max number of threads is currently defined
to 4096 and each time a thread dies that "id" is pushed back on a list.

Q: Should the behaviour of the thread_id freelist be changed so that thread id's
   are reused as soon as possible and make it possible not to return memory
   to global pool? This could improve radically on the performance in 
   consumer/producer applications at the cost of potentially higher memory
   usage.

Item 4
------
The maximum block size handled by this allocator is currently fixed to 128.
The reason is that the SGI pool allocator used this value and it seemed apt to 
do the same. However, there are probably applications out there that does 
loads of let's say 178-byte requests which could be rounded up to 256 byte 
blocks and handled by the allocator if the max block size was adjustable.

Item 5
------
Security is always an issue, and one idea - that obviously would degrade
performance - would be to have an option that, if set, would clear memory when
it's deallocated.