[RFC] dlmalloc: use jemalloc-inspired size classes

[Eric Wong <e@80x24.org>]

For allocations too small for direct mmap and too large for
fastbins, use jemalloc-inspired size classes to reduce
fragmentation.  This means mid-sized allocations pay a 0-20%
overhead to improve the likelyhood of having a good fit
over repeated allocations and frees.
---
 dlmalloc_c.h | 32 ++++++++++++++++++++++++++++++--
 1 file changed, 30 insertions(+), 2 deletions(-)

diff --git a/dlmalloc_c.h b/dlmalloc_c.h
index e842a53..7193982 100644
--- a/dlmalloc_c.h
+++ b/dlmalloc_c.h
@@ -2239,7 +2239,7 @@ typedef unsigned int flag_t;           /* The type of various bit flag sets */
 
 /* pad request, checking for minimum (but not maximum) */
 #define request2size(req) \
-  (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))
+  (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(size_class_pad(req)))
 
 
 /* ------------------ Operations on head and foot fields ----------------- */
@@ -4899,6 +4899,34 @@ static mchunkptr try_realloc_chunk(mstate m, mchunkptr p, size_t nb,
   return newp;
 }
 
+static size_t size_align_(size_t size, size_t alignment)
+{
+	return ((size + (alignment - 1)) & ~(alignment - 1));
+}
+
+static inline size_t size_class_pad(size_t bytes)
+{
+  if (bytes <= MAX_SMALL_REQUEST || bytes >= MAX_REQUEST)
+    return bytes;
+  /*
+   * Use jemalloc-inspired size classes for mid-size allocations to
+   * minimize fragmentation.  This means we pay a 0-20% overhead on
+   * the initial allocations to improve the likelyhood of reuse.
+   */
+  size_t max = 256;
+  size_t nxt;
+  size_t mmap_threshold = mparams.mmap_threshold;
+  do {
+    if (bytes <= max) {
+      size_t sc_bytes = size_align_(bytes, max >> 3);
+      return sc_bytes <= mmap_threshold ? sc_bytes : bytes;
+    }
+    nxt = max << 1;
+  } while (nxt > max && max < mmap_threshold && (max = nxt));
+
+  return bytes;
+}
+
 static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {
   void* mem = 0;
   if (alignment <  MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */
@@ -5573,7 +5601,7 @@ void* mspace_malloc(mspace msp, size_t bytes) {
     else if (bytes >= MAX_REQUEST)
       nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */
     else {
-      nb = pad_request(bytes);
+      nb = pad_request(size_class_pad(bytes));
       if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {
         check_malloced_chunk(ms, mem, nb);
         goto postaction;