mt allocator documentation (draft)

[Felix Yen]

Re: where to put deallocated blocks on the deallocating thread's free  
list.  I was hallucinating; the issue isn't complicated.  On the one  
hand, there are two algorithms, FIFO and LIFO.  On the other hand, we  
have a set of performance tests.  If one algorithm produces better test  
results, it wins.  If the comparison is inconclusive, the simpler  
implementation wins.  There's no need for feedback here, only test  
results.  The documentation can just mention that the choice was made  
using this decision process.

Re: removing blocks from the global free list.
 >  Not sure that I understand. [...]

I should have been clearer: I like this part of the algorithm.

Forgot to mention: when the global free list is empty, the placement of  
the first block in the chunk is a detail that deserves consideration.   
See sections 4.1-4.3 in:
http://www.usenix.org/publications/library/proceedings/bos94/ 
full_papers/bonwick.a

I don't think is a critical enhancement, but it looks like something  
that wants to be done eventually.  It doesn't look like a lot of work,  
and the justification is plausible.

Re: whether to put deallocated blocks on the global free list.
 >  this should also be the piece of code that gets the most attention  
since this can
 >  further improve performance in real world applications. I have some  
ideas that
 >  I will submit at some time (when the doc and pending patches are  
done).

I'm very curious, and think the deallocation algorithm is just as  
important as the object's documentation.  The asymmetry between  
allocation and deallocation is due to the headroom concept, which also  
introduces potential contention between allocating and deallocating  
threads, i.e. use count access.  I think the contention can be finessed  
by incrementing/decrementing use counts atomically, but it's not clear  
to me if headroom adds enough value to justify the complexity it  
introduces.  If you just use chunk size to constrain deallocation,  
there is no need for use counts and other simplifications are also  
possible.  I suspect that these simplifications would lead to even  
better performance.

No matter how deallocation is done, the allocator shares an attribute  
with many allocators that reuse blocks carved from chunks: ignoring the  
case where #bytes exceeds _S_max_bytes, it never releases any memory!   
The previous default allocator also seems to be in this category, but  
the documentation should make this fact clear.


Felix