diff mbox series

[RFT] malloc: reduce largebin granularity to reduce fragmentation

Message ID 20240409093352.M757838@dcvr (mailing list archive)
State Changes Requested
Headers
Series [RFT] malloc: reduce largebin granularity to reduce fragmentation |

Checks

Context Check Description
redhat-pt-bot/TryBot-apply_patch success Patch applied to master at the time it was sent
redhat-pt-bot/TryBot-32bit success Build for i686
linaro-tcwg-bot/tcwg_glibc_build--master-aarch64 success Testing passed
linaro-tcwg-bot/tcwg_glibc_check--master-aarch64 success Testing passed
linaro-tcwg-bot/tcwg_glibc_build--master-arm success Testing passed
linaro-tcwg-bot/tcwg_glibc_check--master-arm success Testing passed

Commit Message

Eric Wong April 9, 2024, 9:33 a.m. UTC 
  Anybody volunteers to help test and get reproducible results for
this?  Thanks in advance.

Testing and getting reproducible results is proving extremely
expensive due to trace sizes and CPU usage required to handle
my existing web/IMAP/NNTP-facing traffic.

But the theory works in my mind and could be a solution to a
problem I've noticed for decades at this point across long-lived
Ruby and Perl web daemons.

I'm also considering having this as a tunable and mallopt(3).

And perhaps limiting the alignment to pagesize can work, because
20% of a large sliding mmap_threshold on 64-bit is several
megabytes...

------8<------
From: Eric Wong <normalperson@yhbt.net>
Subject: [PATCH] malloc: reduce largebin granularity to reduce fragmentation

TL;DR: trade initial best fits for better fits over long process
lifetimes

Size classes in modern versions of jemalloc add a 0-20% overhead
in an attempt to get better fits over time when dealing with
unpredictably-sized allocations and frees.  Initially, this can
be more wasteful than the best (initial) fit strategy used by
dlmalloc, but less wasteful than buddy allocators (which can
have 0-99% overhead).

While the dlmalloc "best fit" strategy is ideal for one-off
permanent allocations and applications that only deal in uniform
allocation sizes; "best fit" gets bogged down over time when
dealing with variably-sized allocations with mixed and
interleaving lifetimes commonly seen in high-level language
runtimes.

Such allocation patterns are common in long-lived web app, NNTP,
and IMAP servers doing text processing with concurrent ("C10K").
Unpredictable lifetimes are often a result of resource sharing
between network clients of disparate lifetimes, but some of it
is outside the application developers control.

Fragmentation is further exacerbated by long-lived allocations
happening late in process life of high-level language runtimes
(e.g. Perl and Ruby).  These runtimes and their standard
libraries can trigger long-lived allocations late in process
life due to the use lazy loading, caching, and internal slab
allocators using malloc to create slabs.

This change only affects largebin allocations which are too
small for mmap, and too small for smallbins and fastbins.
---
 malloc/malloc.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)

Comments

Florian Weimer May 27, 2024, 1:06 p.m. UTC | #1 
* Eric Wong:

> Anybody volunteers to help test and get reproducible results for
> this?  Thanks in advance.
>
> Testing and getting reproducible results is proving extremely
> expensive due to trace sizes and CPU usage required to handle
> my existing web/IMAP/NNTP-facing traffic.
>
> But the theory works in my mind and could be a solution to a
> problem I've noticed for decades at this point across long-lived
> Ruby and Perl web daemons.
>
> I'm also considering having this as a tunable and mallopt(3).
>
> And perhaps limiting the alignment to pagesize can work, because
> 20% of a large sliding mmap_threshold on 64-bit is several
> megabytes...

I looked at the patch and you did not eliminate the mostly-unused bins.
(They can still get used due to fragmentation.)  So you get a strange
conflation of various effects with this patch.  If we're serious about
this, we need to test something that reduces the bin count.  I'm not
sure if it makes senst to test this current version.

Thanks,
Florian
diff mbox series

Patch

diff --git a/malloc/malloc.c b/malloc/malloc.c
index bcb6e5b83c..9a1057f5a7 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3288,6 +3288,56 @@  tcache_thread_shutdown (void)
 
 #endif /* !USE_TCACHE  */
 
+/*
+ * Use jemalloc-inspired size classes for largebin allocations to
+ * minimize fragmentation.  This means we pay a 0-20% overhead on
+ * allocations to improve the likelyhood of reuse across many
+ * odd-sized allocations and frees.  This should reduce fragmentation
+ * in long-lived applications processing various text fragments
+ * (e.g. mail, news, and web services)
+ */
+static inline void
+size_class_align (size_t *nb, size_t *req)
+{
+  // TODO: make this a mallopt + tunable?
+
+  if (in_smallbin_range (*nb))
+    return;
+
+  size_t mm_thresh = MAX (DEFAULT_MMAP_THRESHOLD_MAX, mp_.mmap_threshold);
+
+  if (*nb >= mm_thresh && mp_.n_mmaps < mp_.n_mmaps_max)
+    return;
+
+  size_t n = *req - 1;
+  for (size_t i = 1; i < sizeof (size_t) * CHAR_BIT; i <<= 1)
+    n |= n >> i;
+
+  size_t next_power_of_two = n + 1;
+
+  /*
+   * This size alignment causes up to 20% overhead which can be several
+   * megabytes on 64-bit systems with high mmap_threshold.  Perhaps we
+   * can clamp alignment to pagesize or similar to save space.
+   */
+  size_t align = next_power_of_two >> 3;
+  size_t areq = ALIGN_UP (*req, align);
+  size_t anb = checked_request2size (areq);
+
+  if (anb == 0)
+    return; // aligned size is too big, but unaligned wasn't
+
+  if (anb < mm_thresh || mp_.n_mmaps >= mp_.n_mmaps_max)
+    {
+      *nb = anb;
+      *req = areq;
+    }
+  else // too big for largebins, force it to mmap
+    {
+      *nb = mm_thresh;
+    }
+}
+
 #if IS_IN (libc)
 void *
 __libc_malloc (size_t bytes)
@@ -3308,6 +3358,7 @@  __libc_malloc (size_t bytes)
       __set_errno (ENOMEM);
       return NULL;
     }
+  size_class_align (&tbytes, &bytes);
   size_t tc_idx = csize2tidx (tbytes);
 
   MAYBE_INIT_TCACHE ();
@@ -3503,6 +3554,8 @@  __libc_realloc (void *oldmem, size_t bytes)
       return newmem;
     }
 
+  size_class_align (&nb, &bytes);
+
   if (SINGLE_THREAD_P)
     {
       newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
@@ -3713,6 +3766,13 @@  __libc_calloc (size_t n, size_t elem_size)
     }
 
   sz = bytes;
+  size_t nb = checked_request2size (sz);
+  if (nb == 0)
+    {
+      __set_errno (ENOMEM);
+      return NULL;
+    }
+  size_class_align (&nb, &sz);
 
   if (!__malloc_initialized)
     ptmalloc_init ();