mimalloc pow2 alloc size histograms on exit - `MIMALLOC_SHOW_HISTOGRAM=1`

mimalloc-histogram.patch

diff --git a/include/mimalloc-internal.h b/include/mimalloc-internal.h
index 7160bc474a71..3970e35a2c25 100644
--- a/include/mimalloc-internal.h
+++ b/include/mimalloc-internal.h
@@ -114,6 +114,8 @@ void       _mi_heap_set_default_direct(mi_heap_t* heap);
 
 // "stats.c"
 void       _mi_stats_done(mi_stats_t* stats);
+void       _mi_hist_log(size_t size);
+void       _mi_hist_dump(mi_output_fun* out);
 
 mi_msecs_t  _mi_clock_now(void);
 mi_msecs_t  _mi_clock_end(mi_msecs_t start);
diff --git a/include/mimalloc.h b/include/mimalloc.h
index a7849f863f35..68a60172c32c 100644
--- a/include/mimalloc.h
+++ b/include/mimalloc.h
@@ -299,6 +299,7 @@ typedef enum mi_option_e {
   // stable options
   mi_option_show_errors,
   mi_option_show_stats,
+  mi_option_show_histogram,
   mi_option_verbose,
   // the following options are experimental
   mi_option_eager_commit,
diff --git a/src/alloc.c b/src/alloc.c
index 7fcd6a49e1da..33dcc3481ff7 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -93,6 +93,7 @@ extern inline mi_decl_restrict void* mi_malloc_small(size_t size) mi_attr_noexce
 
 // The main allocation function
 extern inline mi_decl_restrict void* mi_heap_malloc(mi_heap_t* heap, size_t size) mi_attr_noexcept {
+  _mi_hist_log(size);
   if (mi_likely(size <= MI_SMALL_SIZE_MAX)) {
     return mi_heap_malloc_small(heap, size);
   }
diff --git a/src/bits.h b/src/bits.h
new file mode 100644
index 000000000000..7d7e70d28c9a
--- /dev/null
+++ b/src/bits.h
@@ -0,0 +1,131 @@
+/* ----------------------------------------------------------------------------
+Copyright (c) 2020 Michael Clark <michaeljclark@mac.com>
+This is free software; you can redistribute it and/or modify it under the
+terms of the MIT license. A copy of the license can be found in the file
+"LICENSE" at the root of this distribution.
+-----------------------------------------------------------------------------*/
+
+#include <stdint.h>
+
+/*
+ * GCC -O2 -x c -std=c11
+ * MSVC /O2 /TC /std:c11
+ */
+
+#if defined (_MSC_VER)
+#include <intrin.h>
+#endif
+
+#define _clz_defined 1
+#define _ctz_defined 2
+#define _popcnt_defined 4
+
+#if defined (__GNUC__)
+static inline unsigned clz_u32(uint32_t val) { return val == 0 ? 32 : __builtin_clz(val); }
+static inline unsigned clz_u64(uint64_t val) { return val == 0 ? 64 : __builtin_clzll(val); }
+static inline unsigned ctz_u32(uint32_t val) { return val == 0 ? 32 : __builtin_ctz(val); }
+static inline unsigned ctz_u64(uint64_t val) { return val == 0 ? 64 : __builtin_ctzll(val); }
+static inline unsigned popcnt_u32(uint32_t val) { return val == 0 ? 32 : __builtin_popcount(val); }
+static inline unsigned popcnt_u64(uint64_t val) { return val == 0 ? 64 : __builtin_popcountll(val); }
+#define _bits_defined (_clz_defined | _ctz_defined | _popcnt_defined)
+#elif defined (_MSC_VER) && defined (_M_X64)
+static inline unsigned clz_u32(uint32_t val) { return (int)_lzcnt_u32(val); }
+static inline unsigned clz_u64(uint64_t val) { return (int)_lzcnt_u64(val); }
+static inline unsigned ctz_u32(uint32_t val) { return (int)_tzcnt_u32(val); }
+static inline unsigned ctz_u64(uint64_t val) { return (int)_tzcnt_u64(val); }
+static inline unsigned popcnt_u32(uint32_t val) { return (int)__popcnt(val); }
+static inline unsigned popcnt_u64(uint64_t val) { return (int)__popcnt64(val); }
+#define _bits_defined (_clz_defined | _ctz_defined | _popcnt_defined)
+#elif defined (_MSC_VER) && defined (_M_IX86)
+static inline unsigned clz_u32(uint32_t val) { unsigned long count; return val == 0 ? 32 : (_BitScanReverse(&count, val) ^ 31); }
+static inline unsigned clz_u64(uint64_t val) { unsigned long count; return val == 0 ? 64 : (_BitScanReverse64(&count, val) ^ 63); }
+static inline unsigned ctz_u32(uint32_t val) { unsigned long count; return val == 0 ? 32 :_BitScanForward(&count, val); }
+static inline unsigned ctz_u64(uint64_t val) { unsigned long count; return val == 0 ? 64 : _BitScanForward64(&count, val); }
+#define _bits_defined (_clz_defined | _ctz_defined)
+#else
+#define _bits_defined 0
+#endif
+
+/*
+ * algorithms from stanford bit twiddling hacks
+ */
+
+#if (_bits_defined & _popcnt_defined) != _popcnt_defined
+static inline unsigned popcnt_u32(uint32_t val)
+{
+    val = (val & 0x55555555) + ((val >> 1) & 0x55555555);
+    val = (val & 0x33333333) + ((val >> 2) & 0x33333333);
+    val = (val & 0x0F0F0F0F) + ((val >> 4) & 0x0F0F0F0F);
+    val = (val & 0x00FF00FF) + ((val >> 8) & 0x00FF00FF);
+    val = (val & 0x0000FFFF) + ((val >>16) & 0x0000FFFF);
+    return (unsigned)val;
+}
+static inline unsigned popcnt_u64(uint64_t val)
+{
+    val = (val & 0x5555555555555555ULL) + ((val >>  1) & 0x5555555555555555ULL);
+    val = (val & 0x3333333333333333ULL) + ((val >>  2) & 0x3333333333333333ULL);
+    val = (val & 0x0F0F0F0F0F0F0F0FULL) + ((val >>  4) & 0x0F0F0F0F0F0F0F0FULL);
+    val = (val & 0x00FF00FF00FF00FFULL) + ((val >>  8) & 0x00FF00FF00FF00FFULL);
+    val = (val & 0x0000FFFF0000FFFFULL) + ((val >> 16) & 0x0000FFFF0000FFFFULL);
+    return (unsigned)((uint32_t)(val) + (uint32_t)(val >> 32));
+}
+#endif
+
+#if (_bits_defined & _clz_defined) != _clz_defined
+static inline unsigned clz_u32(uint32_t x)
+{
+    x = x | (x >> 1);
+    x = x | (x >> 2);
+    x = x | (x >> 4);
+    x = x | (x >> 8);
+    x = x | (x >>16);
+    return popcnt_u32(~x);
+}
+
+static inline unsigned clz_u64(uint64_t x)
+{
+    x = x | (x >> 1);
+    x = x | (x >> 2);
+    x = x | (x >> 4);
+    x = x | (x >> 8);
+    x = x | (x >>16);
+    x = x | (x >>32);
+    return popcnt_u64(~x);
+}
+#endif
+
+#if (_bits_defined & _ctz_defined) != _ctz_defined
+static inline unsigned ctz_u32(uint32_t v)
+{
+    unsigned c = 32;
+    v &= -(int32_t)v;
+    if (v) c--;
+    if (v & 0x0000FFFF) c -= 16;
+    if (v & 0x00FF00FF) c -= 8;
+    if (v & 0x0F0F0F0F) c -= 4;
+    if (v & 0x33333333) c -= 2;
+    if (v & 0x55555555) c -= 1;
+    return c;
+}
+
+static inline unsigned ctz_u64(uint64_t v)
+{
+    unsigned c = 64;
+    v &= -(int64_t)v;
+    if (v) c--;
+    if (v & 0x00000000FFFFFFFFULL) c -= 32;
+    if (v & 0x0000FFFF0000FFFFULL) c -= 16;
+    if (v & 0x00FF00FF00FF00FFULL) c -= 8;
+    if (v & 0x0F0F0F0F0F0F0F0FULL) c -= 4;
+    if (v & 0x3333333333333333ULL) c -= 2;
+    if (v & 0x5555555555555555ULL) c -= 1;
+    return c;
+}
+#endif
+
+/* C11 generics */
+#if __STDC_VERSION__ >= 201112L
+#define clz(X) _Generic((X), uint32_t: clz_u32, int32_t: clz_u32, uint64_t: clz_u64, int64_t: clz_u64)(X)
+#define ctz(X) _Generic((X), uint32_t: ctz_u32, int32_t: ctz_u32, uint64_t: ctz_u64, int64_t: ctz_u64)(X)
+#define popcnt(X) _Generic((X), uint32_t: ctz_u32, int32_t: popcnt_u32, uint64_t: ctz_u64, int64_t: popcnt_u64)(X)
+#endif
diff --git a/src/init.c b/src/init.c
index df5efd03a452..679732ba6ff6 100644
--- a/src/init.c
+++ b/src/init.c
@@ -523,6 +523,9 @@ static void mi_process_done(void) {
   mi_collect(true /* force */ );
   #endif
 
+  if (mi_option_is_enabled(mi_option_show_histogram)) {
+    _mi_hist_dump(NULL);
+  }
   if (mi_option_is_enabled(mi_option_show_stats) || mi_option_is_enabled(mi_option_verbose)) {
     mi_stats_print(NULL);
   }
diff --git a/src/options.c b/src/options.c
index 6e229f9fc626..9c24f63ce4b3 100644
--- a/src/options.c
+++ b/src/options.c
@@ -63,6 +63,7 @@ static mi_option_desc_t options[_mi_option_last] =
   { 0, UNINIT, MI_OPTION(show_errors) },
 #endif
   { 0, UNINIT, MI_OPTION(show_stats) },
+  { 0, UNINIT, MI_OPTION(show_histogram) },
   { 0, UNINIT, MI_OPTION(verbose) },
 
   // the following options are experimental and not all combinations make sense.
diff --git a/src/stats.c b/src/stats.c
index 8cd74e41c2b0..10f644099522 100644
--- a/src/stats.c
+++ b/src/stats.c
@@ -443,6 +443,54 @@ mi_msecs_t _mi_clock_end(mi_msecs_t start) {
 }
 
 
+/* -----------------------------------------------------------
+  Histogram
+----------------------------------------------------------- */
+
+#include "bits.h"
+
+static volatile size_t hist[64] = { 0 };
+
+void _mi_hist_log(size_t size)
+{
+  if (size == 0) return;
+  size_t bucket = 63 - clz_u64(size);
+  hist[bucket]++;
+}
+
+static void _make_bar(char *buf, size_t buflen, size_t value, size_t max, size_t width)
+{
+    static const char* a[] = { " ", "▏", "▎", "▍", "▌", "▋", "▊", "▉", "█" };
+
+    size_t v = value * width * 8 / max;
+    buf[0] = '\0';
+    while (v > 8) {
+      strncat(buf, a[8], buflen--);
+      v-=8;
+    }
+    strncat(buf, a[v], buflen--);
+}
+
+void _mi_hist_dump(mi_output_fun* out)
+{
+  char bar[256];
+  _mi_fprintf(out, NULL, "histogram: %s\n", "begin");
+  size_t max = 0;
+  for (size_t i = 0; i < 64; i++) {
+    if (hist[i] > max) max = hist[i];
+  }
+  for (size_t i = 0; i < 64; i++) {
+    if (hist[i]) {
+      _make_bar(bar, sizeof(bar), hist[i], max, 50);
+      _mi_fprintf(out, NULL, "%9zu - %-9zu [ %-9zu ] %s\n",
+        (size_t)(1ull << i),
+        (size_t)(1ull << (i+1))-1,
+        hist[i], bar);
+    }
+  }
+  _mi_fprintf(out, NULL, "histogram: %s\n", "end");
+}
+
 // --------------------------------------------------------
 // Basic process statistics
 // --------------------------------------------------------