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

[Wilco Dijkstra]

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