mimalloc のメモリ管理

Microsoft の mimalloc は面白い割り切り方で、小さいソースコードで高速なアロケータを実装しています。

確保するメモリブロックのサイズを、 Small (~8KiB), Large (~512KiB), Huge (512KiB~) の3つに分類し、 Small と Large は同じアルゴリズムで管理し、 Huge は OS 任せにして、 Small と Large は同じアルゴリズムをうまく利用しています。

基礎

OSはpage (x86では基本 4KiB) ごとにメモリをプロセスに割り当てています。

しかしアプリケーションではずっと小さいメモリブロックが必要になることが多くあります。また、必要になるたびに毎回OSからメモリを割り当ててもらうのはパフォーマンスも悪いです。

mimalloc やその他の malloc 実装 (以降 malloc と呼びます) は OS からまとめてメモリを割り当ててもらい、アプリケーションが要求するサイズのメモリブロック (4KiBよりもずっと小さいことが多い) を管理、再利用し、場合によってはページをOSに返します。

OSからメモリを割り当ててもらう場合、普通は実メモリがまだ割り当てられていないメモリ空間だけを割り当ててもらいます。例えば 64KiB (16 page) を割り当ててもらったときには実際にはメモリを消費しておらず、最初の1バイトにアクセスした時に1ページ分 (4KiB) の実メモリが割り当てられます。

Small (~8KiB) クラス

ボトムアップ (メモリブロックに近い方から) で解説していきます。

bin

まず要求されたメモリサイズを8バイト単位に切り上げ、さらにそのサイズ-1の上位 3bit を利用して bin というクラスに分けていきます。 (src)

bin	size [byte]	間隔 [byte]
1, 2, 3, 4	8, 16, 24, 32	8
5, 6, 7, 8	40, 48, 56, 64	8
9, 10, 11, 12	80, 96, 112, 128	16
13, 14, 15, 16	160, 192, 224, 256	32
17, 18, 19, 20	320, 384, 448, 512	64
...	...
33, 34, 35, 36	5KiB, 6KiB, 7KiB, 8KiB	1KiB

例えば malloc(50) は bin=7 になり、 56 byte のメモリブロックが返されます。

ただし malloc は (amd64では) 16 byte 以上の要求に対しては 16byte にアライメントされたメモリを返す必要があるので、アライメントを指定するAPIを使わない限りは bin=3, 5, 7 は使われず、 malloc(17) は bin=4 の 32 byte 分のメモリブロックを返します。

page と freelist

bin 分けされたメモリブロックは page と呼ぶメモリの塊から切り出していきます。 この page は OS のページとは違い mimalloc 内の用語で、 small クラスの場合は基本的に 64 KiB になります。

ある bin に割り当てられた page がまだ存在しない場合、新しい page を割り当て、その内の最初の 4KiB をメモリブロックのサイズに区切ります。そしてそのブロックの先頭に次のブロックのアドレスを書き、 freelist と呼ばれるリンクリストにしていきます。OSが割り当てる実際のメモリはこの 4KiB 分だけになります。もし freelist が空になった時に次の 4KiB 分をまたブロックに区切って freelist にします。

malloc() は freelist の先頭のメモリブロックを返し、freelist の先頭を次のメモリブロックに移します。

char *a = malloc(500);
char *b = malloc(500);
char *c = malloc(500);

free() は逆に返却されたメモリブロックを freelist の先頭に追加していきます。

free(a);
free(c);

segment

page は segment と呼ばれる、より大きなメモリブロックから切り出されます。 segment のサイズは通常 4MiB で、 mimalloc はこの segment 単位でOSからメモリを割り当ててもらいます。

1つの segment には 4096 KiB / 64 KiB =64 個の page があることになります。ただし segment の先頭には管理領域が確保されるために、segment内の最初のpageのサイズは 64KiB より小さくなります。 (ソース)

segment先頭の管理領域内には、segment内の各 page の管理領域も含まれています。これにより page は完全にメモリブロックを切り出すために利用できることになります。

Large (8~512KiB) クラス

Largeクラスは bin に分けられて page からメモリブロックを切り出す部分は完全に small クラスと同じです。 small クラスと違う部分は segment と page のサイズだけになります。 large クラスでは segment は引き続き 4MiB なのですが、 page はこのセグメントに1つだけになり、サイズは 4MiB-管理領域分 になります。

Huge (512KiB~) クラス

Huge クラスは bin に分けられておらず、 segment : page : block が 1 : 1 : 1 になります。

segment のサイズは 4MiB よりも小さくなることがありますが、segmentの先頭は 4MiB にアライメントしてあります。

heap と mi_page_t

最後に全体の管理領域となる heap があります。 (ソース)

([Mimalloc: Free List Sharding in Action -- Microsoft Technical Report MSR-TR-2019-18, June 2019.](https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf) より引用)

// Pages of a certain block size are held in a queue.
typedef struct mi_page_queue_s {
  mi_page_t* first;
  mi_page_t* last;
  size_t     block_size;
} mi_page_queue_t;

#define MI_BIN_FULL  (MI_BIN_HUGE+1)

// A heap owns a set of pages.
struct mi_heap_s {
  mi_tld_t*             tld;
  mi_page_t*            pages_free_direct[MI_SMALL_WSIZE_MAX + 2];   // optimize: array where every entry points a page with possibly free blocks in the corresponding queue for that size.
  mi_page_queue_t       pages[MI_BIN_FULL + 1];                      // queue of pages for each size class (or "bin")

heap の pages は mi_page_queue_t の配列で、各要素は mi_page_t のリンクリストになっています。 mi_page_t にも next, prev が入ってリンクリストを構成しています。

pages[1..MI_BIN_HUGE] は各 bin に対応する、空きがある page のリストになっています。 pages[MI_BIN_FULL] は空きがなくなった page のリストになっています。これで全部の page が管理されています。

segment は heap から直接には管理されていません。 page の管理領域 mi_page_t がセグメントの先頭に割り当てられていたことを思い出してください。 page のアドレスの下位 4MiB 分を切り捨てればそれが segment の先頭アドレスになるからです。

malloc するときは heap->pages[bin] から空きページを見つけてブロックを割り当てます。

free(p) するときは p の属する page を探さないといけないのですが、これはまず p の下位アドレス 4MiB を切り捨ててセグメントの先頭を見つけられるのと、 small クラスであれば p-segment先頭 からセグメント内のどの page に属しているかも判断できます。

実験

mimalloc のメモリ利用効率について調べてみます。

mimalloc のオプションと MADV_FREE

mimalloc にはいくつかオプションがあります。 (ソース)

  { 0, UNINIT, "page_reset" },
  { 0, UNINIT, "cache_reset" },
  { 0, UNINIT, "pool_commit" },
  { 0, UNINIT, "large_os_pages" },   // use large OS pages
  #if MI_SECURE
  { MI_SECURE, INITIALIZED, "secure" }, // in secure build the environment setting is ignored
  #else
  { 0, UNINIT, "secure" },
  #endif
  { 0, UNINIT, "show_stats" },
  { MI_DEBUG, UNINIT, "show_errors" },
  { 0, UNINIT, "verbose" }

このオプションはAPIで設定することもできますし、オプション名に "mimalloc_" の prefix をつけた環境変数 (変数名は大文字小文字を区別しません(case insensitive)) で指定することもできます。例えば show_stats を有効にするには次のようにします。

$ mimalloc_show_stats=1 LD_PRELOAD=$HOME/local/lib/libmimalloc.so ./m
heap stats:     peak      total      freed       unit      count
   elapsed:     0.006 s
   process: user: 0.000 s, system: 0.006 s, faults: 0, reclaims: 3971, rss: 16.4 mb

このうちメモリ使用量について影響するオプションが page_reset と cache_reset です。 page_reset は使わなくなった page を、 cache_reset は使わなくなったセグメントの内管理領域以降の部分に割り当てられた実メモリをOSに返すオプションです。
このときに madvice(2) を使うのですが、その advice 引数に MADV_FREE が使える場合は MADV_FREE を、使えない場合は MADV_DONTNEED を使います。

MADV_FREE を使った場合OSはメモリが欲しくなるまでその実メモリの割り当てを開放しません。これは速度を考えると良いオプションなのですが、RSSを使ってメモリ使用量を評価する時には、RSSが OS のメモリプレッシャーに依存してしまうので良くありません。なので評価時には MADV_FREE を使わず常に MADV_DONTNEED を使うようにします。

diff --git a/src/os.c b/src/os.c
index f6ca2ae..8bfcb9e 100644
--- a/src/os.c
+++ b/src/os.c
@@ -153,7 +153,8 @@ bool _mi_os_reset(void* addr, size_t size) {
   mi_assert(p == start);
   return (p == start);
 #else
-  #if defined(MADV_FREE)
+  //#if defined(MADV_FREE)
+  #if 0
     static int advice = MADV_FREE;
     int err = madvise(start, csize, advice);
     if (err!=0 && errno==EINVAL && advice==MADV_FREE) {

large クラス

smallクラスやlargeクラスで利用している、サイズをクラス別に分けて、固定サイズのメモリブロックを大きなメモリブロックから切り出す方式を Slab Allocation と呼んだりします。

このアロケータは固定長の比較的小さいオブジェクトを大量に確保、解放するときにはメモリ効率も速度も良い一方で、サイズクラスが違うメモリブロックには領域を再利用できないという弱点があります。次のプログラムは、指数関数的にバッファを大きくするケースを再現しています。Python でいえば list や StringIO で似た処理があります。

m.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int main(int argc, char *argv[]) {
    char *p = NULL;
    size_t s = 10, t = 0;
    size_t max = 2 * 1024 * 1024;
    size_t moved = 0;

    if (argc > 1) {
        max = (size_t)atol(argv[1]);
    }

    while (s < max) {
        char *p2 = realloc(p, s);
        assert(p2);
        if (p != p2) {
            //printf("moved when %zu -> %zu\n", t, s);
            moved++;
        }
        p = p2;
        memset(p, 42, s);
        t = s;
        s += s / 8 + 3;
    }

    printf("last size = %zu, moved = %zu\n", t, moved);
    return 0;
}

time コマンドを利用してこのプログラムの maxrss と、 realloc が何回メモリブロックを移動したかを観察してみます。

# glibc malloc
last size = 476688, moved = 4/83
0.00user 0.00system 0:00.00elapsed ?%CPU (0avgtext+0avgdata 2336maxresident)k
0inputs+0outputs (0major+215minor)pagefaults 0swaps

# mimalloc
$ LD_PRELOAD=$HOME/local/lib/libmimalloc.so /usr/bin/time ./m 512000
last size = 476688, moved = 56/83
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 5124maxresident)k
0inputs+0outputs (0major+954minor)pagefaults 0swaps

# mimalloc (cache_reset)
$ LD_PRELOAD=$HOME/local/lib/libmimalloc.so mimalloc_cache_reset=1 /usr/bin/time ./m 512000
last size = 476688, moved = 56/83
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 5088maxresident)k
0inputs+0outputs (0major+954minor)pagefaults 0swaps

# mimalloc (page_reset)
$ LD_PRELOAD=$HOME/local/lib/libmimalloc.so mimalloc_page_reset=1 /usr/bin/time ./m 512000
last size = 476688, moved = 56/83
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 5016maxresident)k
0inputs+0outputs (0major+953minor)pagefaults 0swaps

# jemalloc
$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 /usr/bin/time ./m 512000
last size = 476688, moved = 36/83
0.00user 0.00system 0:00.00elapsed 100%CPU (0avgtext+0avgdata 4484maxresident)k
0inputs+0outputs (0major+371minor)pagefaults 0swaps

mimalloc は glibc malloc の倍くらいメモリを利用しています。また、 glibc malloc が realloc で 4 回しかメモリブロックを移動しなかったのに対して mimalloc は 56回もメモリブロックを移動しています。（この回数には最初のアロケートを含んでいます。）

参考に jemalloc も試してみました。 jemalloc も小さいメモリブロックには slab allocator を利用しますが、 16KiB からは別になります。メモリ使用量は mimalloc よりはすくなく、またメモリコピーのコスト大きくなる領域では rellaoc でメモリブロックの移動を避けられています。

mimallocの cache_reset や page_reset には効果が見られません。これは large 以下の page は、空になっても次のアロケーションに備えてすぐには freelist から削除せず、 reset 処理 (madvise) が呼ばれないからです。

huge クラス

先ほどのプログラムを100倍のサイズまで動かしてみましょう。

# glibc malloc
$ /usr/bin/time ./m 51200000
last size = 47119605, moved = 11/122
0.01user 0.01system 0:00.02elapsed 100%CPU (0avgtext+0avgdata 47816maxresident)k
0inputs+0outputs (0major+11601minor)pagefaults 0swaps

# mimalloc
$ LD_PRELOAD=$HOME/local/lib/libmimalloc.so /usr/bin/time ./m 51200000
last size = 47119605, moved = 95/122
0.07user 0.10system 0:00.17elapsed 99%CPU (0avgtext+0avgdata 123864maxresident)k
0inputs+0outputs (0major+103192minor)pagefaults 0swaps

# mimalloc (cache_reset)
$ LD_PRELOAD=$HOME/local/lib/libmimalloc.so mimalloc_cache_reset=1 /usr/bin/time ./m 51200000
last size = 47119605, moved = 95/122
0.05user 0.12system 0:00.17elapsed 99%CPU (0avgtext+0avgdata 86688maxresident)k
0inputs+0outputs (0major+103470minor)pagefaults 0swaps

# mimalloc (page_reset)
$ LD_PRELOAD=$HOME/local/lib/libmimalloc.so mimalloc_page_reset=1 /usr/bin/time ./m 51200000
last size = 47119605, moved = 95/122
0.06user 0.12system 0:00.18elapsed 100%CPU (0avgtext+0avgdata 86748maxresident)k
0inputs+0outputs (0major+103468minor)pagefaults 0swaps

# jemalloc
$ LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 /usr/bin/time ./m 51200000
last size = 47119605, moved = 55/122
0.03user 0.09system 0:00.12elapsed 99%CPU (0avgtext+0avgdata 283828maxresident)k
0inputs+0outputs (0major+72651minor)pagefaults 0swaps

最終的に47MBを確保しているのに対して、glibcは実際に47MB程度しか利用していません。

mimallocは120MB程度まで消費してしまっています。これはいくつか(最大で32個)の segment をすぐにはOSに返さずにキャッシュしておくからです。 mimalloc_cache_reset オプションを使うとこのキャッシュされた segment に割り当てられた実メモリを madvise でOSに返すのでメモリ使用量を削減できますが、それでも glibc malloc に比べると倍近くのメモリを使用しています。なお、large,hugeクラスでは 1 page = 1 segment ですので mimalloc_page_reset を使っても mimalloc_cache_reset と大した違いはありません。

jemalloc は、、、reallocでメモリを移動する回数はmimallocよりも少ないものの、デフォルトではOSにメモリをなかなか返さないようでデフォルトの mimalloc の倍以上メモリを消費していました。 strace で確認した感じでは MADV_FREE を多用しているわけでもなさそうでした。今回の調査対象は mimalloc だったので jemalloc の深追いはしていませんが、何か積極的にOSにメモリを返すようなオプションがあるのかもしれません。

考察

glibc malloc がすごく優秀に見えますが、これは用意したプログラムがシングルスレッドで単調なアロケーションしかしないからで、もっと複雑なパターンでアロケーションする実際のアプリケーションではまた結果が異なるはずです。

mimalloc は large クラスにも small クラスと同じ slab アロケータを使うことで実装をとてもシンプルにしています。その分のデメリットとして realloc が遅かったり、largeクラスの各binにいくつかのfree blockが残るケースで数MBから数十MB程度メモリ使用量が増えるケースもあります。

slab アロケータはフラグメンテーションが問題になった時にも解析しやすかったりといったメリットもあるので、これらのデメリットが許容できる場合にはいい選択肢になると思います。

一方シンプルなプログラムで Python のメモリ消費が10MBから20MB以上に増えてしまうケースがあったりしたので、 Python のデフォルトのメモリアロケータを mimalloc に置き換えるのはやめておきます。