[PATCH 0/2] [RFC] malloc: tcache improvements

[Cupertino Miranda]

Hi everyone,

On 09-12-2024 11:35, Cupertino Miranda wrote:
> Hi Wilco,
> 
> On 06-12-2024 19:01, Wilco Dijkstra wrote:
>> Hi Cupertino,
>>
>>> As expected, the amount of VM allocated by glibc can be reduced to
>>> practical levels by configuring it to use only one arena (arena_max=1),
>>> however increasing thread contention and killing performance.
>>
>> Did you try other options besides the two extremes of arena_max=1 and
>> arena_max=8*nr_hw_threads?
> Yes, even with arena_max=2, RSS would keep growing. The lower the 
> arena_max, the slower, but still fast enough. :(
> I tried with other options as well, but without any relevant effect.
> 
> I also tried a much much bigger arena_max then default (4000 in 2000 
> threads example), just considering that RSS issue was related to 
> concurrency problems in glibc and that without the threads racing, RSS 
> would stabilize.
> That was not the case and RSS kept growing even faster.
>>
>> This subject has come up before - it seems to me 8 times the number of
>> cores is way overkill. That's 2048 arenas if you have 256 cores!
> Experiments were with 32 cores.
>>
>> In your tests, how many arenas do you actually end up with? Would you
>> see improvements if say we limited arenas to say 1 arena per core or even
>> less for higher core counts? Or do having 2 arenas already result in a 
>> huge
>> increase in RSS?
> Two arenas already results in a continuous grow of RSS.
>>
>> As for tcache improvements, would it be sufficient to increase the 
>> minimum
>> tcache size? Eg. doubling the array would be relatively simple and low 
>> cost.
> Doubling the array would limit at the double. It simply does not scale 
> properly. IMHO, that is really not enough. It would still not allow any 
> proper tuning of the caches.
> We really want to be able to cache "any" size chunk. I honestly think 
> that we need to be able to allow caches to collect larger contiguous 
> amounts of data and allow the cache to manage it, i.e. split and merge 
> chunks without having to lock.
> This would also be good in per-core allocation strategies.
>>
>> My worry with extending the complexity of tcache is that small blocks 
>> will
>> now get an extra penalty. 
> I think the only overhead introduced to original tcache was a condition 
> on the chunk size to make sure what caching mechanism it is dealing with 
> (small or large). Otherwise performance is the same.
> 
> Now that I think about it, if we drop the 2 dimensional arrays from 
> tcache implementation, we can make both implementation the same without 
> that check overhead. Placing or grabbing chunks from those bins would 
> just be a simple add/remove from tail/head of the linked-list, 
> respectively. I don't think that would be much of a performance difference.
> We can keep the counts per bin to preserve the semantics of previous 
> implementation.
Oups, it is not a 2 dimentional array but rather array of linked lists.

Just realized that code around tcache has been updated once again.
Since I will need to rebase my changes, should I go ahead and better 
integrate the large tcache with the existing tcaches?

I am fully aware that large tcache, as presented so far, is incomplete 
and although bringing performance for mysql example, it is an 
intermediate state.

In my head we need to do the following before this could be considered a 
complete solution.

- At the first perthread allocation, tcache would request a big chunk to 
arena, which would be split in two, the first with the allocation 
specific size and the remaining to max tcache capacity. The first would 
be returned in malloc and the second added to tcache bins.
- Further allocations would split new chunks from existing chunks in tcache.
- Once the thread starts to free data, chunks would be re-consolidated 
and added back to tcache. This can be done by checking if neighbor 
chunks belong are cached in the same thread and are not in use. Perhaps 
using a different ekey perthread to identify if chunks are cached within 
the same thread.
- When freeing chunks that would exceed the maximum size of the tcache, 
we would (considering there is no way around locking), lock the arena, 
attempt to re-consolidate the tcache chunks, updating the tcache bins 
and returning to the arena any excess space chunks in tcache (still to 
define strategy). First approach would be to release to arena the older 
freed chunks.
- If there is a malloc and there are no chunks that could be split in 
tcache (or directly used), we should like in the beginning, request a 
bigger chunk to the arena which we will split (for example allocate half 
the tcache max capacity).

What do you think ?
> 
>> So at some point someone will propose to add
>> yet another cache layer to speed up small blocks again! Then we have fast
>> tcache, large tcache, fastbins, small bins, large bins, unsorted bins 
>> and mmap...
>>
>> Another possibility is to make the locking scheme more finegrained. The
>> consolidation approach used currently requires taking malloc locks for 
>> very
>> long periods - and that is the underlying cause for the concurrency 
>> issues.
> I don't know precisely what are the concurrency issues you refer to. 
> However, I tend to believe that, if you have finer grain locking you 
> will have a higher chance to miss a lock in an essential location.
> 
> Also, I think if we would focus on fine grain tuning we will likely just 
> tight the implementation to the existing architecture and lose the 
> opportunity to make it a more configurable solution and address the 
> requirements of these applications (mysql, jvm, etc.).
> However that is likely unrelated to any tcache work.
> 
> Cheers,
> Cupertino