[PATCH] malloc: retire mechanism for older non used tcached chunks

[Cupertino Miranda]

Hi Wilco,

> So I'm not sure how the algorithm could work. On a free, you no longer
> limit the number of chunks that can be inserted into the freelist.
Right, that is the point of the patch. It frees the tcache bins based on 
a sort of collective size of chunks stored in large tcaches, instead of 
number of chunks in each bin.

> Instead
> tcache_location_large first moves any out of date blocks to the
> return_to_arena list and only then checks the count of the current tcache
> bin.
The count is not used in tcache_location_large at all. The num_slots is 
passed to tcache_get_n and is decremented, even if it would mean that it 
would get to become a negative value.
That value is later used to check if the mechanism should traverse this 
bin to attempt to retire further elements (code in the end of 
tcache_put_large)

> So doesn't that mean you can end up adding an unlimited number of
> blocks into the return_to_arena list without ever cleaning it?
Yes and no, because eventually they will start to be retired. And once 
num_slots <= 0 it will be eager to retire them in tcache_put_large.

> To make things
> worse, the default value of tcache_retire_size is set to 0 which means any
> freed block is considered out of date by definition...
No! Unless I made some terrible unnoticed mistake. Please look into 
do_set_tcache_max and do_set_tcache_unsorted_limit.
> 
> Also this adds a large overhead since you always check for out of date blocks
> during every free/malloc of a large block. If we only call tcache_large_cleanup
> if a large bin is full or empty, and then need the RETIRE_OLD_CACHED_CHUNKS
> scan, doesn't it make more sense to do this only in tcache_large_cleanup?
Well, in a practical use case, and considering it is only used for large 
chunks, I did not experience any overhead of this mechanism, unless it 
is somehow affecting the smaller chunks overhead too.

Regarding only doing it is tcache_large_cleanup, when the num_slots == 
0, it could still mean that 6*4MB could be retained in that largest 
tcache bin forever, if the program allocates and deallocates those sizes 
and never really allocates or deallocates something so big.

But this is all good discussion to when it makes sense to mark for 
retiring and actually retiring the chunk.

My thought was, I mark for retire as soon as it finds a chunks that must 
be retired. I will free it to the arena as soon as it will need to lock 
any arenas anyway, either in tcache_put_large or tcache_get_large.

The presented solution prioritizes performance, regardless of the 
smaller overhead it must add in any case.

> That way you avoid all the overheads and only do some extra work if the bin
> is full or empty. Also don't you need to do a full scan of all bins every now and
> again anyway?
I would personally leave that for the program to call tcache_trim, on 
idle times.

> Blocks can only get added to return_to_arena if there is a
> deallocation into that bin - if there isn't, blocks will forever stay in unused bins.
True! My solution to that would be the calls to tcache_trim from the 
program, on idle times. I did not want to periodically or randomly do 
this full traversals to retire.

> 
> So I'm wondering whether doing this when a bin is full/empty will work at all.
> Wouldn't it be simpler to use an allocation counter and if it goes below zero
> flush the current bin, and every now and again flush everything?
IMHO, considering that large chunks do not have single sized chunks, the 
counter is really useless to evaluate if the elements should be retired 
or not. Flushing everything will really be awful in the mysql use case I 
presented in Cauldron. I get performance improvements even with 
MAX_TCACHE==1.
> 
> In terms of implementation, there is a huge amount of special case code
> being force inlined into the fast paths, including adding lots of calls.
Do you mean that small chunk sizes are also being affected? If that is 
the case we should definitely fix it. If it is about the fast paths of 
the large chunks, that might be something that we will need to live 
with. Again, in practice I have seen no performance degradation. 
Allocating large amounts has a fix constant overhead while operating the 
data is linear with the size of the allocated data. For any real use 
case the allocation cost would be negligible comparing to operating the 
allocated memory (for the large chunks).

> This is
> terrible for performance - even for the small bins. The correct approach is to
> call a no-inline function to handle the special cases outside the fast paths.
Ok. That is surprising and unexpected to me. Can you please detail how 
it is affecting the small bins.

Cheers,
Cupertino