[PATCH v6 2/3] malloc: add tcache support for large chunk caching

[Wilco Dijkstra]

Hi Cupertino,

>> This does not make any sense. There are 2 options:  either keep the current definition of
>> mp_.tcache_bins for the small bins and use a new global for the larger bins, or use
>> mp_.tcache_bins for the larger bins only and TCACHE_MAX_BINS for the smaller ones.
>
> Well, I had the intention to keep original semantics unchanged and add
> support for large tcaches as well.
> Original code, allowed tcaches to be limited below the 1k size too.
> 
> Which of those options you would prefer ?
> I think recent code changes are redirecting code to option 2.

The code below is what I am working towards - essentially another step after that.
However existing code expects that tcache_max_bins remains capped at TCACHE_MAX_BINS.
So unless you want to add support for option 2, you could use tcache_max_bytes for large 
blocks since it is currently unused. Ultimately malloc would end up looking like this:

if (__glibc_likely (bytes <= MAX_TCACHE_SIZE))
   ... small tcache code
else if (bytes <= mp_.tcache_max_size)
   ... large tcache code
return __libc_malloc2 (bytes);

This has the advantage neither case pays for the cost of computing the tidx of the other.

>> -# define tidx2usize(idx)       (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)
>> +# define tidx2usize(idx)       (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - MALLOC_ALIGNMENT + 1)
>>
>> This is not correct.
> I have applied the reverse of the original csize2tidx formula, which has
> changed recently. Now I am not totally sure, but my impression was that
> this was more accurate.

Try it with idx=0, you get 24 bytes user memory for the smallest chunk for a 64-bit target.
The changed formula ends up with 17 which is a weird value. If you use a higher malloc
alignment of 32, you'd get 1.

>>> +  if (__glibc_likely (nb < tidx2usize (TCACHE_MAX_BINS)))
>>> +    return fast_csize2tidx(nb);
>>
>> This is incorrect, it should be <= MAX_TCACHE_SIZE. But it's also not needed
>> given this function is only used for large tcache.
> Side-effects of earlier versions. :(
> I think there are some functions like memalign and perhaps calloc that
> still would use it.

Only supporting small tcache for calloc and memalign would be fine for now.

>> This appears to be mapping all sizes into the last bin. There is no advantage in doing
>> this as really large sizes should not be in tcache - so this is just adding extra code for
>> no advantage.
> I don't necessarily agree with limiting once more the maximmum size for
> the tcache. If the user defines a higher valued tunable for
> tcache_max_size, why should we not allow it. Effects on performance are
> really negligible. Applications are not dominated anyway by allocation
> calls. ;)

Large blocks will typically be mmap'd, and we can't currently allow those to be cached in
tcache due to their different format. You will need to add a check for that in the
large block free until we fix this.

Caching huge blocks in tcache will significantly increase memory usage. You could have
a thread freeing a 1GB block but not allocating more large blocks - now that 1GB block
cannot be reused by other threads until the thread exits... We must release such blocks
back to the system. Also since such blocks are rare, there is no need to speed them up
using tcache. So there should be a limit on the size of blocks.

>> +tcache_location_for_size (size_t nb, size_t tc_idx)
>> +{
>> +  if (__glibc_likely (nb <= tidx2usize (TCACHE_MAX_BINS-1)))
>> +    return &(tcache->entries[tc_idx]);
>>
>> There is no need to handle small tcache here, it just adds unnecessary complexity.
> I think there are still some paths that rely on this for small sizes.
>Look into _mid_memalign.

It's not clear whether supporting large blocks in memalign is useful - actually I'm not
sure it is for small blocks! The chance of finding an aligned chunk will be very small,
especially for larger alignments.

>> So if we found a larger block than required, we are not going to use it after
>> doing all this extra work? What you want to do is to check how much larger
>> the returned block is, and use it if it is a little larger than the required size.
>> That should be in the function that searches for the block so we don't need to
>> repeat all the reveals and chunksize etc twice...
> Not sure about allowing tcaches to return non matching size chunks.
> This could result in more fragmentation. I think by having larger chunk
> sizes tcaches, would reduce arena contention enough to allow the non
> matching size allocation to lock and find a better match in main bins.

The fragmentation problem is caused by allowing way too many block sizes, being
overly picky about allocating a matching block size, splitting off tiny remainder
blocks from a larger block, and then also being very lazy about coalescing...
A perfect storm for fragmentation!

> Can we leave this for a future patch.
> Please notice the current approach also does not deal with releasing
> tcache large chunks back to arenas, this is another topic to look into.

Sure we don't need to solve this now.

>> +  /* Limit this call to chunks that fit in same dimention tcache bins.
>> +     Large chunk sizes are cached inside __libc_malloc2.  */
>> +  if (tc_idx < TCACHE_MAX_BINS
>> +      && tcache_available (tc_idx))
>> +    {
>> +      tcache_entry **entry = &tcache->entries[tc_idx];
>> +      return tag_new_usable (tcache_remove_entry (tc_idx, entry));
>> +    }
>
>> Again, it doesn't make any sense to make the fast path more complex.
> What do you mean ? How is it more complex? The presented code is a
> subset of what tcache_get does.

It does a lot of unnecessary extra work due to all the extra if statements.
I still get a 25% slowdown with this version.

> What I am understanding now is that, you clearly want 2 sets of
> functions, really separating tcaches in small/large implementations.
> Please allow me the release of some frustration here ...  you were the
> motivation for me to merge both implementations in the first place. :)

I've asked for keeping the small tcache code fast since your initial RFC.
The 25% slowdown shows that it is impossible to keep the small tcache code fast
when merging it with the large tcache code. So the only option is to keep the code
separate.

>> You need separate code paths for the small and large sizes, or this won't work. There
>> is no guarantee you will get a block of the right size - it seems to return immediately
>> if it finds any block that happens to be aligned enough...
> That is not true, please notice that tcache_location_for_size already
> places tep pointer in a matching size chunk in the list, and if size
> does not match it aborts.

It only does that for the first entry, but then it loops and it could in principle get any
other size as it follows the next links. If the blocks are kept sorted on increasing size
(as appears to be the case), you could return a block that is twice the requested size.

It seems best to add this in a later patch if we can prove it is useful.

>> There should be a limit on the maximum size and bins. There is no proper check on
>> the size, so as soon as the size is larger than MAX_TCACHE_SIZE, the large tcache is
>> enabled for all sizes without any control.
>Oh, I missed to check for tcache_max_bytes. Oups!

tcache_max_bytes is unused right now.

But what I meant is the maximum size is not limited due to csize2tidx - so once you allow
the largest bin, you allow all sizes.

Cheers,
Wilco