コードを読むな、理解しろ

コードを読まないで理解するというと何やら心眼で読めとかテレパシーを使えとか、そーゆー荒唐無稽な方向に走れという事ではなく大局的に理解しましょうという話である。

カーネル読書会のネタで今回はmallocのお話だったのだが、そこでRubyのささださんがいらっしゃっていて、GC(ごみ集め)と記憶域管理の関係について熱い議論が沸騰し、その後いろいろブログなどでフォローされていたりする。

わたしもRubyでmallocやGCがどう実装されているか興味があったのでoprofileで実行プロファイルをとってみたりした。日頃利用しているノートPCでRubyのテストプログラム(test/runner.rb)を実行してoprofileしたのは先日ブログに書いたとおりである。

「それとわたしのノートPCではキャッシュミスを測定できないので、Xeonのマシンでキャッシュミスを測定すると面白いと思った。GCの時ぼろぼろキャッシュミスが発生するということだが、それを巧みに減らすというのが課題になる」ユメのチカラ：Rubyのプロファイリング

思いたったら吉日ということで、会社の最新のDual Coreマシンでキャッシュミスも計測してみた。

そうすると案の定GCでキャッシュミスが多発しているので、そこにちょっとしたパッチをあてればキャッシュミスを減少できるだろうという仮定のもと1行パッチを作成し効果を測定した。キャッシュミスは約半分に減ったのだが実行時間にはほとんど影響がなかった。残念。

さて、oprofileで実行プロファイルを取ってからRubyのパッチを作るまでの道のりであるが、わたし自身はRubyのソースコードにはまったく土地勘がなくほぼ「まるで初めて(略して(まるは)」の初心者が、どのようにパッチを作るかというケーススタディは、初心者ハッカーが自分で獲得しなければいけない道のりという意味でなんかの参考になるのではないかと思い記してみる。

自分のノートにはruby 1.8.4しかはいっていなかったので、最新版の1.8.5をダウンロードする。パッチを作る時、最新版でやるというのは基本中の基本である。(まるはの皆さんここ重要です)

なぜ最新版でやらなければいけないかという理由は101以上あると思うのだが、2〜3あげると、1)最新版ではその問題はすでに解決しているかもしれない、2)コミュニティの力を借りるためには最新版の方が力を借りやすい、3)作成したパッチを本家にとりこんでもらうためには最新版で作成する必要がある、等々。

oprofileを効果的に利用するために、kernel-debuginfoパッケージをあらかじめインストールしておく必要がある。これはカーネルのシンボルを表示するためである。Asianux 2.0 (MIRACLE LINUX 4.0) では kernel-debuginfo-2.6.9-11.19AX というパッケージである。

キャッシュミスイベントを計測するためにインテルのマニュアルを参照する必要がある。Pentium4系のイベントとDual Core系のアーキテクチャでは計測できるハードウェアイベントが異なるので注意が必要である。

今回は下記のようなイベントを設定した。Weighted cycles of L1 miss outstanding というイベントで10万回ごとにサンプリングして、カーネルおよびユーザーモードのイベントを計測する。

opcontrol --event=DCACHE_PEND_MISS:100000:0:1:1

opreport -l
で関数ごとの頻度が表示されるので、最初の2〜3の関数から調査をする。

opreport -dg 詳細が下記のように表示される。

CPU: Core Solo / Duo, speed 2666.77 MHz (estimated)
Counted DCACHE_PEND_MISS events (Weighted cycles of L1 miss outstanding) with 
a unit mask of 0x00 (Weighted cycles) count 100000 
        vma      samples  %        linenr info                 app name symbol name
000000000042be50 244787   33.2383  gc.c:1661                   ruby         os_each_obj
  000000000042bfac 1        4.1e-04  gc.c:1599
  000000000042bfb9 5         0.0020  gc.c:1599
  000000000042bfbe 6         0.0025  gc.c:1599
  000000000042bfd0 4862      1.9862  gc.c:1601
  000000000042bfd3 228573   93.3763  gc.c:1601
  000000000042bfd6 2698      1.1022  gc.c:1601
  000000000042bfd8 250       0.1021  ruby.h:672
...

gc.c 1601行目でキャッシュミスが多発しているのが分る。

さてここからソースコードの旅がはじまる。

static VALUE
os_obj_of(of)
    VALUE of;
{
    int i;
    int n = 0;

    for (i = 0; i < heaps_used; i++) {
	RVALUE *p, *pend;

	p = heaps[i].slot; pend = p + heaps[i].limit;
	for (;p < pend; p++) {
	    if (p->as.basic.flags) { /* ここの部分 */
		switch (TYPE(p)) {
		  case T_ICLASS:
		  case T_VARMAP:
		  case T_SCOPE:
		  case T_NODE:
		    continue;
		  case T_CLASS:
		    if (FL_TEST(p, FL_SINGLETON)) continue;
		  default:
		    if (!p->as.basic.klass) continue;
		    if (rb_obj_is_kind_of((VALUE)p, of)) {
			rb_yield((VALUE)p);
			n++;
		    }
		}
	    }
	}
    }

    return INT2FIX(n);
}

コードを読まづして、高速道路で一気に目的地に到着した。キャッシュミスが多発している場合の性能向上のパターンとして、1) プリフェッチ、2) カラーリング、3) ブロッキング、等々いろいろある。

プリフェッチというのは、メモリにアクセスするかなり以前にあらかじめフェッチ(アクセス)しておいて、キャッシュに載せておき、実際にアクセスする時点ではキャッシュに載っているのでレイテンシーが低くなる(高速にアクセスできる)というテクニックである。

for ループだと次にアクセスする要素があらかじめわかっているので簡単にプリフェッチのコードを仕込むことができる。コード変更量最小化の法則にしたがうとこれは非常にやりやすい変更である。

ここまではコードを読まづにたどりついたわけだ。パフォーマンスボトルネックという現象を理解するためには、コードを読まづしてツールを利用すればできるという事である。コードの字面だけを追っていてはキャッシュミスや性能上の問題は発見できない。

# diff -u gc.c~ gc.c
--- gc.c~       2006-08-25 17:12:46.000000000 +0900
+++ gc.c        2006-10-03 10:47:08.000000000 +0900
@@ -1594,10 +1594,15 @@
     int n = 0;

     for (i = 0; i < heaps_used; i++) {
-       RVALUE *p, *pend;
+       RVALUE *p, *pend;

        p = heaps[i].slot; pend = p + heaps[i].limit;
        for (;p < pend; p++) {
+         if ( (p+1) < pend) {
+               __asm__ __volatile__ (
+                  " prefetch (%0)\n"
+                  : : "r" ((p+1)->as.basic.flags) );
+           }
            if (p->as.basic.flags) {
                switch (TYPE(p)) {
                  case T_ICLASS:

というパッチになった。

コードを読むな、コードを理解しろ

という事である。

参考：

まつもとさんの日記

未来のいつか/hyoshiokの日記　Rubyのキャッシュミスを測定する。

未来のいつか/hyoshiokの日記　Cache Aware Ruby Patch

Rubyソースコード完全解説という名著があるが、その第5章も大変参考になった。

Comments

[投稿： K.Tsuchiya]

はじめまして,吉岡さま.

プログラムの高速化で
頭を悩ませている点があったので,
今回の記事が大変参考になりました.

これからも記事を楽しみにしています.

K.Tsuchiya