[PATCH 0/5] Add single-threaded fast path to malloc

[Wilco Dijkstra <Wilco dot Dijkstra at arm dot com>]

This patch series significantly speeds up malloc by adding fast
paths for single-threaded applications.  In this case we can execute
a simpler, faster path.  Doing this at a high level means we only
need a single check which can bypass multiple locks, atomic
instructions and related complexity.

The speedup for fastbin allocations on AArch64 is about 2.4x.
The number of atomic operations is now zero in single-threaded
scenarios.

Bench-malloc-thread is 11% faster for 1 thread and 5% faster with
8-32 threads.

The new bench-malloc-simple shows a speedup of ~2x for small
blocks on AArch64 in the new single-threaded paths, while the multi-
threaded path varies between a few percent faster to a few percent
slower. On x64 the gain is ~1.5x and 1.1x respectively, below are a
few typical results for 16-byte blocks:

   "malloc_block_size_0016": {
    "st_num_allocs_0025_time": 53.7072,
    "st_num_allocs_0100_time": 56.3621,
    "st_num_allocs_0400_time": 56.9713,
    "st_num_allocs_1000_time": 57.5048,
    "mt_num_allocs_0025_time": 93.9841,
    "mt_num_allocs_0100_time": 108.32,
    "mt_num_allocs_0400_time": 112.172,
    "mt_num_allocs_1000_time": 113.499
   },

   "malloc_block_size_0016": {
    "st_num_allocs_0025_time": 37.4045,
    "st_num_allocs_0100_time": 36.7491,
    "st_num_allocs_0400_time": 37.0647,
    "st_num_allocs_1000_time": 37.4376,
    "mt_num_allocs_0025_time": 84.2352,
    "mt_num_allocs_0100_time": 97.7985,
    "mt_num_allocs_0400_time": 101.453,
    "mt_num_allocs_1000_time": 102.858
   },


Patch 1: Inline tcache functions
Patch 2: Add single-threaded path to malloc/realloc/calloc/memalloc 
Patch 3: Add single-threaded path to _int_free
Patch 4: Fix deadlock in _int_free consistency check
Patch 5: Add single-threaded path to _int_malloc

 malloc/malloc.c | 202 +++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 141 insertions(+), 61 deletions(-)