mallocのはなし
mrubyのkhash.hでハッシュテーブルを生成するときのmallocを削ったパッチが取り込まれたので今日はmalloc記念日。
https://github.com/mruby/mruby/commit/cdb23edf312e868bad3a7f8e8fc1a8aa556bcf4a
■mallocとfree
Cで動的にメモリを確保するには、標準関数のmallocを使う。解放するときはfreeである。C初心者だとポインタがよくわからないということでこのへんが理解できないことも多いが、とりあえず配列として使っておけばなんとなく動くので問題ないとかいう人も多いだろう。
mallocは引数にサイズを渡すと確保されたメモリの先頭アドレスが返ってくる。それをポインタ変数に格納して使う。freeするときはmallocが返したアドレスを引数に渡す。malloc/freeを普通に使えるぐらいに理解できてる人は、ここで疑問を持つべきだ。freeするときにアドレスを渡しただけで、なぜメモリが解放できるのか。
■アドレスで管理する
何かしらの管理情報を構造体として作って、それのポインタをユーザーに返すというのは扱いやすいのでよく見かけるインターフェイスである。関数にはその構造体を渡してもらえばライブラリは適切に動作する。mrubyで言うところのmrb_state構造体がまさにそれだ。しかしmallocは確保したメモリのアドレスを返すし、freeはそれを受け取るしで、とりあえずこれは管理情報構造体ではない。
普通に考えると配列やハッシュテーブルでアドレスと管理情報の対応表を作って管理することになるのだろうが、それだとデータが増えた場合に動的にメモリを拡張する必要があって、mallocを作るのにmallocが必要になるというメタプログラミング的(?)な話になってきて、不可能ではないのだろうが作るのは大変そうである。
実際、世の中にたくさんあるmallocはそのようなﾅﾏﾇﾙｲ実装はしていないらしい。
■mallocの管理情報
世の中のmallocどもはたいがい、以下のような情報の持ち方をしている。
|---------- mallocが実際に確保するメモリ領域 ---------|
+----------------+------------------------------------+
| 管理情報 | ユーザが指定した容量のメモリ領域 |
+----------------+------------------------------------+
↑
ユーザに返すアドレスmallocは引数で渡された値よりも少し多くメモリを確保し、管理情報を先頭に作って、その後ろのアドレスを返す。ユーザは返されたアドレスから先を使用し、freeにアドレスを渡すと、freeは渡されたアドレスから少し前のメモリを覗いて管理情報を参照して、メモリの解放処理を行う。これを考えた人はおそろしく賢い。
この管理情報を使ってどのようにメモリを管理するのかと言う話は本題ではないので省くが、Googleで検索するとたくさん出てくる。具体例の一つとして以下のスライドを挙げておくので興味ある人は参考にするとよいかもしれない。
http://www.slideshare.net/kosaki55tea/glibc-malloc
■malloc削減パッチ
さて、今回mrubyに投げたパッチは単純に3つのmallocを1つにまとめたものだ。mallocがまとまったのでfreeもまとまった。ハッシュテーブルを生成するときの内部情報用mallocは3つあったが、3つとも同じタイミングで確保も解放もするのでバラバラにする必要がなかったのである。
mallocがまとまると以下の4点の効果が得られる。
・mallocの呼び出しが減るので単純に速くなる。
・管理領域が減るので消費メモリがちょっと減る。
・メモリの断片化を抑制できるのでメモリ効率が上がる。
・freeの呼び出しも減るのでGCの回収処理が速くなる。
つまり、どえりゃー速くなるがね(名古屋弁)ということである。実際、手元の128指定のao-render.rbでは96秒→85秒となって、ぷるりのコメントではabout10%と控えめに表現していたがとんでもなく速くなった。もちろんハッシュテーブルを作らないようなベンチマークでは効果は無い。
ちなみに、このパッチ適用後のmrubyではハッシュテーブル生成に計2回のmallocを実行しているが、がんばればこれを1回に減らすこともできる。その場合、ハッシュテーブルの管理情報とフラグ＆キー＆値の情報をまとめて確保することになるので、ハッシュの拡大時の再生成にほんの少しだけ時間がかかるようになってしまう。今回のパッチはデメリット無しで速くなるので受け付けられたが、1回にまとめるのは修正規模も大きいしデメリットもあるので受け付けられるかどうかはわからない。
