はじめに
今回、2018年度のアドベントカレンダー記事シクシク素数アドベントカレンダー sed 編を書いたのですが、そこで組んだsedスクリプトの性能が、WSL(Windows Subsystem for Linux)環境下では非常に劣化する現象が見られました。
この記事は、その原因の考察とちょっとした対策ということで小ネタです。
試した環境は、Windows10/WSL+Ubuntu16.04.5 libc6-2.23-0ubuntu10(glibc) です。
現象
当該記事のために組んだのは、4,9を桁に含む素数を指定個数(最大100個)リストアップするスクリプトなのですが、ideone.comでは9秒程度で100個出力できたのに対し、手元では1分以上かかってしまいました。
$ 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以外は呼んでない状態です。
$ 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の呼ばれている様子を眺めてみます。
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のサイトをご覧いただきたいのですが、今回は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の回数を測りました。
$ 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の性能影響が大きい