mimalloc を Python で使う

Microsoft が [microsoft/mimalloc](https://github.com/microsoft/mimalloc) という新しいアロケータを公開しました。

https://www.microsoft.com/en-us/research/publication/mimalloc-free-list-sharding-in-action/ によると、

> One increasing use-case for allocators is as back-end implementations of
languages, such as Swift and Python, that use reference counting to
automatically deallocate objects. We present mimalloc, a memory allocator
that effectively balances these demands,  ...

ということで、 Swift や Python のような参照カウントを利用している言語向けにチューニングされているらしいです。

pyperformance という実際のライブラリを利用したベンチマークスイートを実行してみたところ、確かにいくつかのベンチマークが速くなっていました。

```
$ ./python  -m pyperf compare_to pymalloc.json mimalloc.json -G --min-speed=3
Faster (10):
- spectral_norm: 199 ms +- 1 ms -> 182 ms +- 1 ms: 1.10x faster (-9%)
- mako: 23.2 ms +- 0.2 ms -> 21.6 ms +- 0.3 ms: 1.07x faster (-7%)
- regex_effbot: 3.62 ms +- 0.04 ms -> 3.41 ms +- 0.03 ms: 1.06x faster (-6%)
- json_dumps: 16.7 ms +- 0.2 ms -> 15.9 ms +- 0.1 ms: 1.05x faster (-4%)
- crypto_pyaes: 162 ms +- 1 ms -> 155 ms +- 1 ms: 1.05x faster (-4%)
- json_loads: 38.5 us +- 1.8 us -> 37.1 us +- 1.2 us: 1.04x faster (-4%)
- float: 156 ms +- 2 ms -> 150 ms +- 2 ms: 1.04x faster (-4%)
- pathlib: 29.2 ms +- 0.6 ms -> 28.1 ms +- 0.6 ms: 1.04x faster (-4%)
- scimark_fft: 498 ms +- 6 ms -> 483 ms +- 3 ms: 1.03x faster (-3%)
- regex_v8: 27.7 ms +- 0.1 ms -> 26.8 ms +- 0.4 ms: 1.03x faster (-3%)

Benchmark hidden because not significant (50): ...
```

できるだけ多くのユーザーにいろんなアプリを動かした時のパフォーマンスやメモリ使用量を見てもらいたいので、使い方をまとめておきます。 (ただし mimalloc は MADV_FREE を使うので見た目 RSS が大きくなることには注意してください。)

以下の手順は Linux 用になります。私は Ubuntu 19.04 で確認しました。

### インストール

cmake と make を使います。次の例では `CMAKE_INSTALL_PREFIX` を指定することで `$HOME/local/lib` にインストールしていますが、デフォルトの `/usr/local/lib` にインストールしたい場合は `-D CMAKE_INSTALL_PREFIX=$HOME/local` を外し、 `make install` の代わりに `sudo make install` になります。

```
$ git clone https://github.com/microsoft/mimalloc.git
$ cd mimalloc
$ vim include/mimalloc-types.h  # enable MI_STAT=2
$ mkdir build
$ cd build
$ cmake .. -D CMAKE_INSTALL_PREFIX=$HOME/local
...
$ make -j8
...
$ make install
-- Install configuration: "Release"
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/libmimalloc.so
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/libmimalloc.a
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/include/mimalloc.h
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/cmake/mimalloc-config.cmake
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/cmake/mimalloc-config-version.cmake
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/cmake/mimalloc.cmake
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/cmake/mimalloc-release.cmake
-- Installing: /home/inada-n/local/lib/libmimalloc.so
-- Installing: /home/inada-n/local/lib/mimalloc-1.0/mimalloc.o
```

### 利用方法

ビルド済みの Python を利用する場合は、 `LD_PRELOAD=$HOME/local/lib/libmimalloc.so python` のようにして実行することで、 glibc malloc をオーバーライドして利用することができます。

Python をビルドするときに静的リンクしたい場合は `cp $HOME/local/lib/mimalloc-1.0/mimalloc.o .` してから、 configure 後に Makefile の次の部分を修正して mimalloc.o を追加すると libpython.a と python 実行ファイルに mimalloc をリンクすることができるはずです。

```
LIBRARY_OBJS=   \
        $(LIBRARY_OBJS_OMIT_FROZEN) \
        Python/frozen.o \
        mimalloc.o
```

ただしリンクしただけではデフォルトの pymalloc が使われます。 環境変数 `PYTHONMALLOC=malloc` をすることで mimalloc によってオーバーライドされた malloc を利用することができます。

環境変数 `MIMALLOC_SHOW_STATS=1` を設定しておくとプログラム終了時に rss などの統計情報が出力されるので、それをみて mimalloc がリンクされていることを確認することができます。 (詳しい統計情報を表示したい場合は、 mimalloc をインストールする前にソースコードから `MI_STAT` を探して `#define MI_STAT 1` に書き換えます。)

ちなみに pymalloc で統計情報を出力するには `PYTHONMALLOCSTATS=1` です。こちらは終了時ではなくOSから追加でメモリを割り当ててもらう (mmap) たびに統計を stderr に出力します。これを使うことで pymalloc が使われなくなったことを確認することができます。

```
# mimalloc を静的リンクした場合

# PYTHONMALLOC=malloc を指定し忘れると pymalloc が使われる
$ MIMALLOC_SHOW_STATS=1 PYTHONMALLOCSTATS=1  ./python -c '[*map(str, range(1000))]'
...
# bytes in allocated blocks        =              468,256
# bytes in available blocks        =              456,256
153 unused pools * 4096 bytes      =              626,688
# bytes lost to pool headers       =               11,088
# bytes lost to quantization       =               10,576
# bytes lost to arena alignment    =                    0
Total                              =            1,572,864  # ここまで pymallocの統計、以降 mimalloc の統計
heap stats:     peak      total      freed       unit      count
   elapsed:     0.012 s
   process: user: 0.013 s, system: 0.000 s, faults: 0, reclaims: 884, rss: 8.0 mb

# PYTHONMALLOC=malloc を指定した場合、 pymalloc が使われなくなって mimalloc の統計だけが表示される。
$ MIMALLOC_SHOW_STATS=1 PYTHONMALLOCSTATS=1 PYTHONMALLOC=malloc ./python -c '[*map(str, range(1000))]'
heap stats:     peak      total      freed       unit      count
   elapsed:     0.009 s
   process: user: 0.010 s, system: 0.000 s, faults: 0, reclaims: 868, rss: 7.9 mb
```