WSLでのmallocのチューニング(小ネタ)

# はじめに
今回、2018年度のアドベントカレンダー記事[シクシク素数アドベントカレンダー sed 編](      https://qiita.com/angel_p_57/items/b9c13f7e6c22fcc8189c)を書いたのですが、そこで組んだsedスクリプトの性能が、WSL(Windows Subsystem for Linux)環境下では非常に劣化する現象が見られました。

この記事は、その原因の考察とちょっとした対策ということで小ネタです。

試した環境は、Windows10/WSL+Ubuntu16.04.5 libc6-2.23-0ubuntu10(glibc) です。

# 現象
当該記事のために組んだのは、4,9を桁に含む素数を指定個数(最大100個)リストアップするスクリプトなのですが、[ideone.com](ideone.com)では9秒程度で100個出力できたのに対し、手元では1分以上かかってしまいました。

```shell-session:手元での実行ログ
$ time sed -rf prime49.sed <<< 100
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593,599,619,641,643,647,659,691,709,719,739,743,769,797,809,829,839,859,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1019,1039,1049,1069,1091,1093,1097,1109,1129,1193,1229,1249,1259,1279,1289,1291,1297,1319

real    1m22.520s
user    0m28.656s
sys     0m49.813s
```

見ると、( userの30秒弱はCPUの違いとして納得できるものの ) sys で大半の時間が取られてしまっています。( ちなみにideone.comだと9秒中1.6秒程度がsys )
これは流石に異常です。なぜなら、単にメモリの中でデータをいじくりまわすことしかしていないのに、OSの処理(システムコール)で大量にCPU時間を消費していることになるからです。

## 目星
しかし、ここで1つ思い当たるモノがありました。それは、メモリ確保(malloc/realloc)と解放(free)に関わる処理です。
処理に必要なメモリが不足すればOSから借りてくるしかありません。ライブラリ(glibc)はmallocの度にOSから確保するわけではなく、ある程度まとまった単位で借りてくるはずですが、それでもOSの処理が絡む部分であることには違いがありません。

果たしてstraceで見たところ、大量のbrkシステムコールの発生を確認できました。readで入力を受け取ってから最後に出力して終了するまで、brk以外は呼んでない状態です。

```shell-session:strace実行の様子
$ strace -T sed -rf prime49.sed <<< 30
execve("/bin/sed", ["sed", "-rf", "prime49.sed"], [/* 16 vars */]) = 0 <0.053092>
(略)
read(0, "30\n", 4096)                   = 3 <0.000327>
brk(0x199e000)                          = 0x199e000 <0.000403>
brk(0x19bf000)                          = 0x19bf000 <0.000258>
(略)
brk(0x19c5000)                          = 0x19c5000 <0.000244>
brk(0x19b4000)                          = 0x19b4000 <0.000248>
brk(0x19b3000)                          = 0x19b3000 <0.000240>
brk(0x19d4000)                          = 0x19d4000 <0.004341>
brk(0x19c6000)                          = 0x19c6000 <0.000406>
brk(0x19b3000)                          = 0x19b3000 <0.000378>
brk(0x19d4000)                          = 0x19d4000 <0.000416>
brk(0x19c8000)                          = 0x19c8000 <0.000312>
brk(0x19b3000)                          = 0x19b3000 <0.000383>
(略)
brk(0x19f2000)                          = 0x19f2000 <0.000814>
brk(0x19b8000)                          = 0x19b8000 <0.000336>
fstat(1, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0 <0.000076>
write(1, "19,29,41,43,47,59,79,89,97,109,1"..., 11119,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409
) = 111 <0.000310>
read(0, "", 4096)                       = 0 <0.000207>
close(1)                                = 0 <0.000141>
close(2)                                = 0 <0.000139>
exit_group(0)                           = ?
+++ exited with 0 +++
```

## 原因
しかし、なぜこんなにbrkが呼ばれているんでしょうか。

ここでbrkというのは、OSに対してメモリ領域の端をずらすように依頼するシステムコールです。という観点でbrkの呼ばれている様子を眺めてみます。

```txt:brk呼び出しの一部
brk(0x19c5000)                          = 0x19c5000 <0.000244>
brk(0x19b4000)                          = 0x19b4000 <0.000248>
brk(0x19b3000)                          = 0x19b3000 <0.000240>
brk(0x19d4000)                          = 0x19d4000 <0.004341>
```

引数に指定してるのが、ずらした「先」のメモリアドレスです。**この値が増減している**というところが重要です。これは、ライブラリ的にはmallocで必要になってOSからメモリを確保するのと、freeで空いた領域をOSに返すのと、両方を頻繁に繰り返しているということを意味します。
ということは、**直ぐに必要になるメモリをわざわざ一旦返してまた再取得する**ということを行っているわけで、性能的にはムダな行為です。これ、なんとかできないでしょうか。

## 対処
ここで、実はglibcのmallocには、幾つか性能をチューニングするためのパラメータがあることが知られています。

詳細は[gnuのサイト](https://www.gnu.org/software/libc/manual/html_node/Malloc-Tunable-Parameters.html)をご覧いただきたいのですが、今回はM_TOP_PADに着目しました。

以下に説明を引用します。( 強調は @angel_p_57 による )

> **M_TOP_PAD**
> This parameter determines **the amount of extra memory to obtain from the system** when an arena needs to be extended. It also specifies **the number of bytes to retain when shrinking an arena**. This provides the necessary hysteresis in heap size such that excessive amounts of system calls can be avoided.
>
> The default value of this parameter is 0.
>
> This parameter can also be set for the process at startup by **setting the environment variable MALLOC_TOP_PAD_** to the desired value.

詳細は割愛しますが、重要なのは、このパラメータがmalloc/freeでメモリをOSから確保する/OSに返却するメモリ量の単位を制御するものであり、環境変数MALLOC_TOP_PAD_で設定できるということです。
この値を十分大きくすれば、brkの回数を減らすことができるのではないかと考えました。

## 検証
straceでは、`-e`オプションで情報をとるシステムコールを絞ることもできますし、`-c`でサマリーを得ることもできます。
そこで、MALLOC_TOP_PAD_ の値を変更して、brkの回数を測りました。

```shell-session:brk回数測定例
$ MALLOC_TOP_PAD_=100000 strace -c -e brk sed -rf prime49.sed <<< 50
19,29,41,43,47,59,79,89,97,109,139,149,179,191,193,197,199,229,239,241,269,293,347,349,359,379,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,509,541,547,569,593
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  0.00    0.000000           0      7274           brk
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000                  7274           total
```

また、それぞれでもCPU時間も測りました。( こちらはstraceを介さずに )

以下、入力値50に対する比較表です。

| MALLOC_TOP_PAD_ | brk回数 | user(秒) | sys(秒) |
|---:|---:|---:|---:|
|設定なし|6,137|1.875|1.734|
|100,000|7,274|1.781|2.141|
|1,000,000|17|1.625|0.047|
|10,000,000|3|1.578|0.031|

設定値100,000 (0.1MB) だとかえってbrkの回数が増え、sysも増加していますが、1,000,000(1MB), 10,000,000(10MB)と上げていくと劇的に減少が見られます。どうやら対処としては的を射ていたようです。

入力値50では設定値1,000,000と10,000,000の違いはさほどでもありませんが、入力値100ではそれなりの違いとなりました。

| MALLOC_TOP_PAD_ | brk回数 | user(秒) | sys(秒) |
|---:|---:|---:|---:|
|設定なし|100,751|28.656|49.813|
|1,000,000|18,241|25.922|20.469|
|10,000,000|3|24.750|0.031|

ただ、ideone.com ではそこまで影響がなくて、WSLでここまで brk の影響が出るのか。それについては詳細は分かりません。ただ、Linux kernelのメモリ管理の裏に、WSLでのWindowsOSとの仲介があるわけなので、その分オーバーヘッドが大きくなるのではないかと推測はできます。

# 終わりに
ということで結論です。

* メモリ確保・解放による brk システムコールの回数がかさむと処理時間増加として影響が出る場合がある
* MALLOC_TOP_PAD_環境変数を増やすことで brkの回数を減らせる
* WSLだと特に brkの性能影響が大きい