[PATCH v8 1/2] malloc: add tcache support for large chunk caching

[Cupertino Miranda]

Hi Wilco,

Unfortunately locally I did not get that performance difference.
I will work on your suggestions very closely to avoid further delays 
having this patch approved.
Sorry for the setback.

I realized the mistake in using tcache_index in do_set_tcache_max. Of 
course it would not work ... tcache == NULL. :(

Cheers,
Cupertino

On 30-05-2025 18:29, Wilco Dijkstra wrote:
> Hi Cupertino,
> 
> Unfortunately the latest version is significantly slower on the tcache bench - 21% on
> latency... It now shares more code between the small and large tcache cases which is
> what we need to avoid. For example, tcache_index should never be used on fast paths
> that are for the small tcache. It also doesn't act like an index, which causes buggy code
> in do_set_tcache_max.
> 
>   
> +# define TCACHE_SMALL_BINS             64
> +# define TCACHE_LARGE_BINS             12 /* Up to 4M chunks */
> +# define TCACHE_MAX_BINS       (TCACHE_SMALL_BINS + TCACHE_LARGE_BINS)
> +# define MAX_TCACHE_SMALL_SIZE tidx2usize (TCACHE_MAX_BINS-1)
> 
> Small bins surely???
> 
> +tcache_index (size_t bytes)
>   {
> -  if (tc_idx < mp_.tcache_bins
> -      && tcache != NULL
> -      && tcache->counts[tc_idx] > 0)
> -    return true;
> +  size_t tc_idx = csize2tidx (bytes);
> +
> +  if (__glibc_unlikely (tcache == NULL))
> +    return TCACHE_MAX_BINS;
> +
> +  if (__glibc_likely (tc_idx < TCACHE_SMALL_BINS))
> +    return tc_idx;
>     else
> -    return false;
> +    {
> +      tc_idx = large_csize2tidx (bytes);
> +      return  tc_idx;
> +    }
> +  return TCACHE_MAX_BINS;
> 
> That looks like dead code? It feels wrong not to check mp_.tcache_max_bytes
> since it means we're always going to call tcache_get_large for large blocks
> even if they are disabled. However it's best not to use tcache_index at all.
> 
> 
>   __libc_malloc (size_t bytes)
>   {
>   #if USE_TCACHE
> -  size_t tc_idx = usize2tidx (bytes);
> +  size_t nb = checked_request2size (bytes);
> +  size_t tc_idx = tcache_index (nb);
>   
> -  if (tcache_available (tc_idx))
> -    return tag_new_usable (tcache_get (tc_idx));
> +  if (tc_idx < TCACHE_MAX_BINS
> +      && tcache->entries[tc_idx] != NULL)
> +    {
> +      if (tc_idx < TCACHE_SMALL_BINS)
> +        return tag_new_usable (tcache_get (tc_idx));
> +      else
> +       {
> +         void *victim = tcache_get_large (tc_idx, nb);
> +         if (victim != NULL)
> +           return tag_new_usable (victim);
> +       }
> +    }
>   
> To avoid slowdowns due to tcache_index, this should be written like:
> 
> if (size <= TCACHE_SMALL_SIZE)
>    {
>       size_t tc_idx = csize2tidx (bytes);
>       if (tcache != NULL && tcache->entries[tc_idx] != NULL)
>          return tag_new_usable (tcache_get (tc_idx));
>     }
> else if (size <= mp_.tcache_max_bytes && tcache != NULL)
>    {
>      size_t tc_idx = large_csize2tidx (bytes);
>      void *victim = tcache_get_large (tc_idx, nb);
>      if (victim != NULL)
>         return tag_new_usable (victim);
>    }
>   
> This way you clearly separate the 2 cases and get optimal code for both.
> We can then optimize the tcache != NULL checks like in calloc.
> 
> 
> @@ -3428,10 +3529,10 @@ __libc_free (void *mem)
>     check_inuse_chunk (arena_for_chunk (p), p);
>   
>   #if USE_TCACHE
> -  size_t tc_idx = csize2tidx (size);
> -
> -  if (__glibc_likely (tcache != NULL && tc_idx < mp_.tcache_bins))
> +  if (__glibc_likely (tcache != NULL && size < mp_.tcache_max_bytes))
>       {
> +      size_t tc_idx = tcache_index (size);
> 
> Using tcache_index here is *really* bad for performance...
> 
>   
> @@ -3440,7 +3541,15 @@ __libc_free (void *mem)
>           return tcache_double_free_verify (e);
>   
>         if (__glibc_likely (tcache->counts[tc_idx] < mp_.tcache_count))
> -        return tcache_put (p, tc_idx);
> +       {
> +          if (__glibc_likely (tc_idx < TCACHE_SMALL_BINS))
> +           return tcache_put (p, tc_idx);
> +          else if (!chunk_is_mmapped (p))
> +            {
> +             size_t tc_idx = tcache_index (size);
> +             return tcache_put_large (p, tc_idx);
> +           }
> 
> Same as for malloc, just keep things simple and keep both cases completely
> separate.
> 
> 
> @@ -3825,21 +3919,24 @@ __libc_calloc (size_t n, size_t elem_size)
>       }
>   
>   #if USE_TCACHE
> -  size_t tc_idx = usize2tidx (bytes);
> -  if (__glibc_likely (tc_idx < mp_.tcache_bins))
> -    {
> -      if (__glibc_unlikely (tcache == NULL))
> -        return tcache_calloc_init (bytes);
> -
> -      if (__glibc_likely (tcache->entries[tc_idx] != NULL))
> -       {
> -         void *mem = tcache_get (tc_idx);
> +  size_t nb = checked_request2size (bytes);
> +  size_t tc_idx = tcache_index (nb);
>   
> -         if (__glibc_unlikely (mtag_enabled))
> -            return tag_new_zero_region (mem, memsize (mem2chunk (mem)));
> +  void *mem = NULL;
> +  if (__glibc_likely (tc_idx < TCACHE_MAX_BINS
> +                     && tcache->entries[tc_idx] != NULL))
> +    {
> +      if (tc_idx < TCACHE_SMALL_BINS)
> +       mem = tcache_get (tc_idx);
> +      else
> +       mem = tcache_get_large (tc_idx, nb);
> +    }
> +  if (mem != NULL)
> +    {
> +      if (__glibc_unlikely (mtag_enabled))
> +       return tag_new_zero_region (mem, memsize (mem2chunk (mem)));
>   
> -          return clear_memory ((INTERNAL_SIZE_T *) mem, tidx2usize (tc_idx));
> -       }
> +      return clear_memory ((INTERNAL_SIZE_T *) mem, memsize (mem2chunk (mem)));
> 
> 
> Calloc has the same issue as malloc with tcache_index. It also adds code outside the tcache
> paths and removes optimizations for the small tcache case. The extra assignment and check for
> NULL is unnecessary - you only need that for the large tcache path. Also large tcache should not
> use clear_memory since the size is always too large for it, so it just adds unnecessary overheads.
> 
> 
> @@ -3946,7 +4043,7 @@ _int_malloc (mstate av, size_t bytes)
>                 /* While we're here, if we see other chunks of the same size,
>                    stash them in the tcache.  */
>                 size_t tc_idx = csize2tidx (nb);
> -             if (tcache != NULL && tc_idx < mp_.tcache_bins)
> +             if (tcache != NULL && nb < mp_.tcache_max_bytes)
> 
> This is not correct - this is only for small tcache (and will remain so).
>   
> @@ -4007,7 +4104,7 @@ _int_malloc (mstate av, size_t bytes)
>             /* While we're here, if we see other chunks of the same size,
>                stash them in the tcache.  */
>             size_t tc_idx = csize2tidx (nb);
> -         if (tcache != NULL && tc_idx < mp_.tcache_bins)
> +         if (tcache != NULL && tc_idx < mp_.tcache_max_bytes)
> 
> Likewise.
>   
> @@ -4069,7 +4166,7 @@ _int_malloc (mstate av, size_t bytes)
>   #if USE_TCACHE
>     INTERNAL_SIZE_T tcache_nb = 0;
>     size_t tc_idx = csize2tidx (nb);
> -  if (tcache != NULL && tc_idx < mp_.tcache_bins)
> +  if (tcache != NULL && nb < mp_.tcache_max_bytes)
> 
> Likewise (while we could possibly add large tcache support here in the future, it's likely
> a bad idea to preload tcache with large blocks).
>   
> 
> @@ -5482,13 +5579,16 @@ do_set_arena_max (size_t value)
>   static __always_inline int
>   do_set_tcache_max (size_t value)
>   {
> -  if (value <= MAX_TCACHE_SIZE)
> +  size_t nb = request2size (value);
> +  size_t index = tcache_index (nb);
> +  LIBC_PROBE (memory_tunable_tcache_max_bytes, 2, value, mp_.tcache_max_bytes);
> +
> +  if (index < TCACHE_MAX_BINS)
>       {
> -      LIBC_PROBE (memory_tunable_tcache_max_bytes, 2, value, mp_.tcache_max_bytes);
> -      mp_.tcache_max_bytes = value;
> -      mp_.tcache_bins = csize2tidx (request2size(value)) + 1;
> +      mp_.tcache_max_bytes = nb;
>         return 1;
> 
> This won't work, now we will never set mp_.tcache_max_bytes...
> 
> This also no longer sets mp_.tcache_bins which we still need for the above cases (after the
> counts are reversed we can just use TCACHE_SMALL_BINS).
> 
> Cheers,
> Wilco