RFC on mt_allocator.h

[Dhruv Matani]

[This is a bit late, but it took me time to think over some stuff]

>         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?

How about using arguments to the constructors? That's because the
standard containers can be constructed from the allocators that have
already been constructed. So, the user can construct an mt_allocator
separately, and then give that instance to the container. I presume that
your mt_allocator will be stateless as far as the actual memory blocks
used is concerned, but stateful as far as the grow_size, initial_size
are concerned, because the first time I wrote an allocator, even I had
faced a similar problem. Effectively, it means that the memory blocks
may be interchanged between different threads if need be, but the size
for each thread when the size of growth is concerned can be controlled
by the constructor parameter. Also, if the above behaviour is
implemented, another question will be raised namely: What if different
threads have a different grow_size? Then the next parameter can control
whether the memory acqired by the current thread should be given back to
the main allocator or not (If it's not given back, it means that no
other thread can re-use it, and it has to be given back using operator
delete). If you go to see, there are may parameters that can be
controlled, but here it is a question of singling out *_those**
parameters that ***really*** do make a difference. As Bjarne Stroustrup
said (not an exact quote): It's not a question of how many tests a
compiler fails, but how important those features are, meaning that a
compiler can fail 15-20 small obscure language tests, while another
might pass all those, but fail one major language feature test. That
doesn't mean that the 1st one is worse than the 2nd for practial use...
Similarly, the number of confugurable parameters need to be controlled,
otherwise the code will become very difficult to manage, and stuff...

The first thing on your list should be to pin point those parameters
that will make a difference: I can see the following as poissible
candidates (list not complete):

1. Initial Size.
2. Grow Size.
3. Is the memory given back using operator delete?
4. Can different lists share memory if the list for one thread is only
little full (false sharing tradeoffs)
5. If (3) evaluates to false, then can the memory of one thread having a
different grow_size be given to another thread haing a different grow
size?
6. If (5) is true, then does this apply for all sizes or only if the
difference in the grow_size is <= SOME_THRESHOLD_VALUE.

We *Must* find out the most important ones from the above.

> 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?

I have a couple of things to say here. Please correct me if I'm wrong:

1. Even the global operator new which is thread safe will have to lock,
no matter which thread asks for the memory.

2. Now, the design of the mt_allocator should be such that there are 2
main parts:


	A). The MAIN allocator brain.
	B). It's clients.

The Main allocator brain is the one that makes all the decisions based
on whether it's client's support it or not, so it basically talks to
it's clients. The clients are the thread allocators which are stateful
in terms of the grow_size, etc...

The MAIN allocator brain has a Lock named (Brain_Lock). Whenever a
client's free list or whetever has run out of memory, it locks on
Brain_Lock, and asks the Brain for more memory depending on what the
grow_size is. And the brain does what it's suppsed to, which may include
keeping a track of how many free lists a client holds NOTE: This
information need not necessarily be in the Brain object itself. It may
be in the client object.

Therefore, if the main thread asks for memory, it will not affect the
Brain_Lock, because the brain is not responsible satisfying memory
requests from the user. Now, the brain has other bigger responsibilities
such as if a thread asks for memory, the Brain can say: Is there any
client of mine that's not using all it's memory (meaning that is any
thread's free list empty?). If so, is it possible for me to transfer it
to the current requester without asking the OS for more memory? So,
bascially, we make the Brain responsible to the clients and the clients
responsible to the user's requests. Major separation of concerens.

> 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.
> 
Maybe, we could have a parameter that says: If the size of the block is
<= SOME_THRESHOLD, then let it linger, else it should given back using
operator delete.

> 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.

Why not make the internal free-list allocator a type parameterized one,
so we no longer have to do any guess work about the sizes? The size of
an object would be sizeof(T). Now all node based containers like
list/map/multimap/deque would request 1 for allocate, so we need only
specialize and optimize for 1 (single) object allocations. (I'd like to
confirm whether deque passed 1 to the allocate() function or not?)

We do not need to optimize for vector, and let the global opearator new
handle all that.

> 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.

Probably, but that can be done at a later stage.


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