[PATCH v4 7/7] malloc: performance improvements

[Cupertino Miranda]

Improving previous code for performance reasons.
Most significant changes are:
 - the addition of fast_csize2tidx function which is used in key
locations where we know we will only deal with chunks within
original fix size tcache bins, 
 - simplify conditions in hot locations and
 - hint the compiler for most likely condition outcomes with
__glibc_(un)likely macros (or __builtin_expect).

---
 malloc/arena.c  |  2 +-
 malloc/malloc.c | 60 ++++++++++++++++++++++++++++---------------------
 2 files changed, 35 insertions(+), 27 deletions(-)

diff --git a/malloc/arena.c b/malloc/arena.c
index 353b63488d..6b5a31d03f 100644
--- a/malloc/arena.c
+++ b/malloc/arena.c
@@ -261,7 +261,7 @@ static void tcache_key_initialize (void);
 static void
 ptmalloc_init (void)
 {
-  if (__malloc_initialized)
+  if (__glibc_likely (__malloc_initialized))
     return;
 
   __malloc_initialized = true;
diff --git a/malloc/malloc.c b/malloc/malloc.c
index c031ca0071..7fb0fdaee7 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -293,6 +293,7 @@
 /* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
 # define TCACHE_UNBOUND_SIZE_BINS	10
 # define TCACHE_MAX_BINS		64
+# define TCACHE_ALL_BINS	(TCACHE_MAX_BINS + TCACHE_UNBOUND_SIZE_BINS)
 # define MAX_TCACHE_SIZE	tidx2usize (TCACHE_MAX_BINS-1)
 # define TCACHE_FIXED_SIZE_BINS	\
 	   (mp_.tcache_bins < TCACHE_MAX_BINS ? mp_.tcache_bins : TCACHE_MAX_BINS)
@@ -3154,17 +3155,22 @@ tcache_key_initialize (void)
     }
 }
 
+#define fast_csize2tidx(nb) ((nb - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
+
 static __always_inline size_t
 csize2tidx(size_t nb)
 {
-  size_t idx = ((nb - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT);
-  if (__glibc_unlikely (idx >= TCACHE_MAX_BINS)
-      && __glibc_unlikely (mp_.tcache_bins > TCACHE_MAX_BINS))
+  if (__glibc_likely (nb < tidx2usize (TCACHE_MAX_BINS)))
+    return fast_csize2tidx(nb);
+  else if (__glibc_likely (mp_.tcache_bins < TCACHE_MAX_BINS))
+    return TCACHE_MAX_BINS;
+  else
     {
-      idx = TCACHE_MAX_BINS + __builtin_clz (tidx2usize (TCACHE_MAX_BINS-1)) - __builtin_clz (nb);
-      idx = idx < mp_.tcache_bins ? idx : mp_.tcache_bins - 1;
+      size_t idx = TCACHE_MAX_BINS
+	      + __builtin_clz (tidx2usize (TCACHE_MAX_BINS-1))
+	      - __builtin_clz (nb);
+      return idx < TCACHE_ALL_BINS ? idx : TCACHE_ALL_BINS - 1;
     }
-  return idx;
 }
 
 static __always_inline tcache_entry *tcache_next (tcache_entry *);
@@ -3172,19 +3178,21 @@ static __always_inline tcache_entry *tcache_next (tcache_entry *);
 static __always_inline tcache_entry **
 tcache_location_for_size (size_t nb, size_t tc_idx)
 {
-  tcache_entry **tep = &(tcache->entries[tc_idx]);
-  tcache_entry *te = REVEAL_PTR (*tep);
-  if (__glibc_unlikely (tc_idx >= TCACHE_MAX_BINS))
+  if (__glibc_likely (nb <= tidx2usize (TCACHE_MAX_BINS-1)))
+    return &(tcache->entries[tc_idx]);
+  else
     {
+      tcache_entry **tep = &(tcache->entries[tc_idx]);
+      tcache_entry *te = REVEAL_PTR (*tep);
       while (te != NULL
-	     && __glibc_unlikely (chunksize (mem2chunk (te)) < nb))
-	{
-	  tep = & (te->next);
-	  te = tcache_next (te);
-	}
-    }
+             && __glibc_unlikely (chunksize (mem2chunk (te)) < nb))
+        {
+          tep = & (te->next);
+          te = tcache_next (te);
+        }
 
-  return tep;
+      return tep;
+    }
 }
 
 /* Caller must ensure that we know tc_idx is valid and there's room
@@ -3228,7 +3236,7 @@ tcache_get (size_t nb, size_t tc_idx)
 {
   tcache_entry **entry = tcache_location_for_size (nb, tc_idx);
   tcache_entry *e = REVEAL_PTR (*entry);
-  if (tc_idx >= TCACHE_MAX_BINS
+  if (__glibc_unlikely (tc_idx >= TCACHE_MAX_BINS)
       && (e == NULL || chunksize (mem2chunk (e)) != nb))
     return NULL;
 
@@ -3246,8 +3254,7 @@ tcache_next (tcache_entry *e)
 static __always_inline bool
 tcache_available (size_t tc_idx)
 {
-  if (tc_idx < mp_.tcache_bins
-      && tcache != NULL
+  if (__glibc_likely (tcache != NULL)
       && tcache->counts[tc_idx] > 0)
     return true;
   else
@@ -3284,7 +3291,8 @@ tcache_free (mchunkptr p, INTERNAL_SIZE_T size)
 {
   bool done = false;
   size_t tc_idx = csize2tidx (size);
-  if (tcache != NULL && tc_idx < mp_.tcache_bins)
+  if (__glibc_likely (tcache != NULL)
+      && __glibc_likely (tc_idx < mp_.tcache_bins))
     {
       /* Check to see if it's already in the tcache.  */
       tcache_entry *e = (tcache_entry *) chunk2mem (p);
@@ -4040,7 +4048,7 @@ _int_malloc (mstate av, size_t bytes)
 #if USE_TCACHE
 	      /* While we're here, if we see other chunks of the same size,
 		 stash them in the tcache.  */
-	      size_t tc_idx = csize2tidx (nb);
+	      size_t tc_idx = fast_csize2tidx (nb);
 	      if (tcache != NULL && tc_idx < TCACHE_FIXED_SIZE_BINS)
 		{
 		  mchunkptr tc_victim;
@@ -4098,8 +4106,8 @@ _int_malloc (mstate av, size_t bytes)
 #if USE_TCACHE
 	  /* 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 < TCACHE_FIXED_SIZE_BINS)
+	  size_t tc_idx = fast_csize2tidx (nb);
+	  if (__glibc_likely (tcache != NULL) && tc_idx < TCACHE_FIXED_SIZE_BINS)
 	    {
 	      mchunkptr tc_victim;
 
@@ -4160,7 +4168,7 @@ _int_malloc (mstate av, size_t bytes)
 
 #if USE_TCACHE
   INTERNAL_SIZE_T tcache_nb = 0;
-  size_t tc_idx = csize2tidx (nb);
+  size_t tc_idx = fast_csize2tidx (nb);
   if (tcache != NULL && tc_idx < TCACHE_FIXED_SIZE_BINS)
     tcache_nb = nb;
   int return_cached = 0;
@@ -4241,8 +4249,8 @@ _int_malloc (mstate av, size_t bytes)
 #if USE_TCACHE
 	      /* Fill cache first, return to user only if cache fills.
 		 We may return one of these chunks later.  */
-	      if (tcache_nb > 0
-		  && tcache->counts[tc_idx] < mp_.tcache_count)
+	      if (__glibc_likely (tcache_nb > 0)
+		  && __glibc_likely (tcache->counts[tc_idx] < mp_.tcache_count))
 		{
 		  tcache_put (victim, tc_idx);
 		  return_cached = 1;
-- 
2.39.5