Rubyのキャッシュミスを測定する。

会社のマシンでoprofileを取った。oprofile利用方法(キャッシュミスの測定方法)は会社のブログを参照してほしい。ruby-1.8.5で計測した。

イベントマスクはCPU_CLK_UNHALTEDとDCACHE_PEND_MISSで、前者はクロックごとにイベントが発生し、後者はL1キャッシュミスのイベントである。それぞれ10万回ごとにサンプリングするようにした。

CPU: Core Solo / Duo, speed 2666.77 MHz (estimated)
Counted CPU_CLK_UNHALTED events (Unhalted clock cycles) with a unit mask of 0x00 (Unhalted core cycles) count 100000
Counted DCACHE_PEND_MISS events (Weighted cycles of L1 miss outstanding) with a unit mask of 0x00 (Weighted cycles) count 100000
samples  %        samples  %        app name                 symbol name
132649   10.6887  122439   33.1370  ruby                     os_each_obj
89183     7.1863  1026      0.2777  libcrypto.so.0.9.7a      (no symbols)
60353     4.8632  17284     4.6778  vmlinux                  copy_page_range
57827     4.6596  8810      2.3843  ruby                     rb_eval
53387     4.3019  17372     4.7016  ruby                     gc_mark_children
47991     3.8671  8398      2.2728  ruby                     garbage_collect
43420     3.4987  4320      1.1692  libc-2.3.4.so            memcpy
37168     2.9950  17395     4.7078  ruby                     gc_mark
33726     2.7176  10043     2.7180  ruby                     st_lookup
33245     2.6788  9428      2.5516  vmlinux                  unmap_vmas

ここで、
132649 10.6887 122439 33.1370 ruby os_each_obj
の行の読み方であるが、132649回CPU_CLK_UNHALTEDというイベントをサンプリングして、それは全体の10.6887%であり、DCACHE_PEND_MISSイベントを122439回サンプリングしDCACHE_PEND_MISSイベントのうち33.1370%で、その場所はrubyのos_each_objという関数である。以下同様に見ていく。

libcrypto.so.0.9.7a の中にはシンボルが見あたらないのはデバッグモードでコンパイルされていなかったのであろう。複数のイベントを同時に表示しているので、rubyのos_each_objという関数はクロック毎のサンプル(約10.7%)よりキャッシュミス(33.1%)が多いので、この場所はキャッシュに優しくない場所であるということが分る。逆にlibcrypto.so.0.9.7aの関数は非常にキャッシュに優しい(キャッシュミスが少ない)。

libcだけを見てみると下記のとおり。memcpyはキャッシュミスは少ないが、malloc_consolidateはキャッシュミスが多い。

43420     3.4987  4320      1.1692  libc-2.3.4.so            memcpy
26100     2.1031  6039      1.6344  libc-2.3.4.so            _int_malloc
14779     1.1909  8181      2.2141  libc-2.3.4.so            malloc_consolidate
12857     1.0360  4756      1.2872  libc-2.3.4.so            free
11840     0.9541  3896      1.0544  libc-2.3.4.so            _int_free
5931      0.4779  224       0.0606  libc-2.3.4.so            malloc
2847      0.2294  340       0.0920  libc-2.3.4.so            strcmp
2182      0.1758  245       0.0663  libc-2.3.4.so            strlen
1937      0.1561  15        0.0041  libc-2.3.4.so            msort_with_tmp
1657      0.1335  7         0.0019  libc-2.3.4.so            memchr

os_each_objから呼ばれている下記の/* ここの部分 */でキャッシュミスが多発しているようなので、何か作戦をねればキャッシュミスを削減することはできそうである。

ソースは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);
}

素人考えだとprefetchだろうなあと思う。