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

[Cupertino Miranda]

Hi Wilco,

>>> 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)
> 
> That means that a bin can contain many thousands of blocks if recently
> released. And once the count goes negative, we check each block on
> average 1.5 times. And we keep doing these repeated whole-list checks
> for every insert until the count goes positive again. If we keep inserting
> new blocks, the list won't reduce in size even as we retire older blocks -
> it can actually keep growing. That's an O(N^2) bug.
> 
>>> 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.
> 
> Eventually, but one can keep inserting and walking the whole list 1.5 times
> on every insert starts to become very expensive.
No, the list is only traversed once at max, as it will not restart to 
traverse the list, it will continue from the entry location returned 
from tcache_location_large, but I get your point. Using the num_slots 
might not be the proper approach for this.

> 
>>> 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.
> 
> OK, so you require one to use the tunable first - it seems better to set a good
> default value. There is definitely something wrong there:
> 
> -  if (tc_idx < TCACHE_MAX_BINS)
> +  if (tc_idx < TCACHE_MAX_BINS || mp_.tcache_retire_size == 0)
> 
> This will allow huge tcache_max values that result in indexing beyond the tcache.
For large tcache in current upstream state that is always the case 
otherwise large tcache is not enabled, right ?
> 
>>> 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.
> 
> Obviously it adds more overhead to smaller chunks since you can free ~20000
> 1K chunks before you consider releasing them. That's a serious O(N^2) bug.
I see what you mean, if we keep being traversing the list of similar 
sizes chunks that should not be retired this would be a huge performance 
hit.

Should we not cache already cached sizes? Maybe we could limit the the 
number of similar sized chunks in the bin to some max value? Otherwise 
we would immediately free them to the arena ?

> 
>> 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.
> 
> Tcache_count=16 today and we're discussing increasing it to 24 or 32.
> So it means today you could have like 384MB of chunks cached in large tcache
> if you use a 4MB tcache_max. But even with the retire code, it will not retire
> anything if you don't happen to use those sizes ever again...
> 
> These are serious numbers, so we do need to find a robust way to limit the amount
> of memory cached by tcache.
Indeed, maybe waiting for tcache_count == 0 is not the proper solution 
to attempt to retire bigger cached values.
Please look at my patch as an approach to identify older cached chunks 
without having to keep an independent ordered list of chunks.
Everything else, I think is really open for discussion, i.e:
  - when to traverse bins for retiring,
  - should it be in the fast paths or not,
  - ... anything else ...

> 
>>> 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.
> 
> Most applications don't do that. There was a reason for the recently removed
> consolidation phase. You want something that mostly works automatically.
I really feel that those applications that are willing to switch to 
another allocator would not mind to do it, if that would bring them a 
performance benefit without the compromise on memory usage.

Maybe we can implement both solutions through a tunable.
Allow to automatically do it, with the extra overhead, or give back that 
responsibility to the program, without the extra overhead.
The automatic mode should be the default.

> 
>>> 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.
> 
> But so is only checking bins that are used. It's the bins that are unused but not
> empty that need to be checked...
> 
> I don't see how flushing is a particular issue. The point is to give back old blocks,
> and any block that is used frequently will quickly end up in tcache again.
> 
>>> 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.
> 
> I believe it is both. It should be easy to come up with testcases that show
> dramatic slowdowns due to all the redundant linked list traversals.
Right, there are problems with current approach.

> 
>>> 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.
> 
> Well adding huge amounts of code and function calls always makes code slow,
> especially if it was already highly optimized. Just keep only fastpath code in
> libc_malloc/free and use tailcalls to handle the slow paths.
I totally understand your concerns here. It is indeed a lot of inlined 
code in the __libc_free. I wonder what would be the performacne impact 
of not inlining tcache_put_large and making it a tailcall too.

Cheers,
Cupertino