[PATCH v2 0/4] malloc: Batched frees, tcache hysteresis behavior

[Florian Weimer]

This series implements batched frees.  The new addition is the last
patch, which avoids repeated unlinking and linking of bins, which is
very expensive.

Compared to the previous series, this one is actually faster than the
non-batched code.  I see very small regressions in cfrac and espresso,
possibly in the benchmark noise.  Other benchmarks are generally on par
with a tcache bump to 32 entries (despite using only 16 on average),
with some quite signifcant outliers such as
bench-malloc-simple/main_arena_mt_allocs_0400_time, which is ~39% faster
than mainline (a 32-depth tcache leads only to a ~%4 improvement).  The
larson application server/remote-free workload is about 7% faster as
well.

I also tried a deep merge implementation that inlines parts of
_int_free_merge_chunk and _int_free_create_chunk into the batched free
loop, avoiding even more repeated linking and unlinking.  However, that
was not generally beneficial, and it is quite a bit of additional code
to maintain.  However, I only implemented aggressive backwards
coalescing, forward coalescing was more limited in multi-threaded mode
because it's not possible to check if a chunk is allocated in a
race-free manner without taking the arena lock.

Another attempt tried to avoid arena lock switching more aggressively,
but like sorting, this leads to quadratic work in the number of tcache
entries.  It was not generally faster than what is posted here, but it's
also quite complicated.

Thanks,
Florian

Florian Weimer (4):
  malloc: Perform batched frees if tcache is full
  malloc: Only fill half of the tcache during batch allocation
  malloc: Increase tcache fill count from 16 to 32
  malloc: Implement merging of tcache chunks during batched frees

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


base-commit: 84c3993f1ff1546c8dd06c3ced5d2bed0be649c0
-- 
2.54.0