オブジェクトの*近さ*とパフォーマンス
あるプロジェクトで圧倒的なパフォーマンスを目指していろいろやってきた中で、「オブジェクトの*近さ*」、Locality、とパフォーマンスの関係に最近注目しています。
これについてはGarbage Collectorのフィールドでの調査・研究資料が十分にあるので簡単に紹介します。
"Since the cost of a page fault will be hundreds of thousands, or even millions, of cycles, additional CPU effort to avoid paging is worthwhile." John L. Hennessy and David A. Patterson, Comuter Architecture: A Quanttitative Approach, Morgan Kaufman, 1996
「ページフォルトの代償は、サイクルにして、１０万、いや１００万倍にもなるので、このページフォルトを避けるために支払うCPUサイクルはとても価値があるのです」
というわけで、
"It is desireble that relationships between data are reflected in their layout in the heap: the more closely data are related, the more closely they should be placed in the heap. Placing related data on the same pages reduces paging traffic since bringing one object into main memory also brings in its neighbours, and these are likely to be required by the user program." Richard Jones, Rafael Lins, Garbage Collection, WILEY, 1996
「データの関連性を、ヒープ内のデータの配置に反映することが求められます。データの関連性が深ければ深いほど、それだけ近くに配置するのです。このように関連するデータを同じページに配置すると、あるオブジェクトをその周辺オブジェクト、つまり関連するオブジェクトと一緒にメインメモリに展開することになります。こうしてユーザープログラムがアクセスしそうな関連オブジェクトがまとめて事前取得されるので、（コストの高い）ページへのアクセス数を減らすことができるというわけです。」
本当にそうなのかな・・・、
"Over 60 percent of the longest lived objects were allocated within one kilobyte of each other, and that this correlation was even stronger if younger objects were considered." Barry Hayes, Using key object opportunism to collect old objects. In OOPLSA '91.
「６０％超の長寿命オブジェクトは、関連するもの同士が1キロバイトの範囲内で生成されていました。もし寿命の短いオブジェクトも考慮すると、より強い相関関係が見出されます」
どうやって調べたの！？と思いますが、一応数字でも出されているようです。どうやらオブジェクトの*近さ*がパフォーマンスに大きな影響を与えるのは分かったから、どうやって２次元のオブジェクトグラフ（構造）を１次元に並べていくんだろう？
Layout Strategy
- Depth-First
- Breadth-First
分かりやすく説明するために、ツリー構造を考えて見ましょう。Depth-Firstで並べると、上から下へのパスに沿って並びます。一方Breadth-Firstで並べると、左から右、レベル（階層）に沿って並ぶわけです。こうして注意深くオブジェクトの関連性を考慮して配置するという涙ぐましい努力によって、非常に大きなパフォーマンスゲインが得られるようになります。
そしてこれはデータベースにも適用することができます。こういったオブジェクトの関連性を考慮できるのは、リレーショナルやフラットファイルでは無理で、オブジェクトデータベースならではの特徴・強みとなるでしょうね。
＊フォーラム内でもこの議論がオープンになっています
http://developer.db4o.com/forums/thread/33697.aspx
