Identification of logically related heap regions - 昏論会ウィキ

Intro

ヒープ中のオブジェクトを、関連性によってグルーピングするヒューリスティクス3つ :

• 1. ヒープ中の再帰的なデータ構造を、リンクとか型とか使って特定
• 2. 複数オブジェクトで構成される "複合オブジェクト" を抽出
• 3. コレクションとか配列に入っているオブジェクトを、類似性でグルーピング

こういうグルーピングができると、

• オブジェクトの空間局所性を上げられたり、
• GCの効率あげられたり、
• 領域・データ構造単位で静的にdeallocateできたり して嬉しいです

ヒープのモデル化

Region

"Region" と呼ぶ単位で「グループ」を表す。

ヒープ上の Region N = (C, P, Rin, Rout) where

• C: オブジェクトの集合
• P: C内のオブジェクト同士をつなぐ全ポインタ
• Rin, Rout: Cに入ってくる/Cから出ていく全参照

実際のヒープ上のオブジェクトの構造を、上の Region を使った lssg (labeled storage shape graph) というモデルに落として解析をおこなう。

ssg (storage shape graph)

詳細な定義をとりあえず飛ばすと、

• ヒープを直に表すグラフ (変数集合V, オブジェクト集合O, {変数∪オブジェクト}→オブジェクトの参照集合R) の、オブジェクトOを、オブジェクトをまとめた単位"Region" Nで置き換えて、
• グラフ (変数集合^V, Region集合^N, {変数∪Region}→Regionのポインタ集合の集合^E) で表した物が ssg (storage shape graph)

lssg (labeled storage shape graph)

上のssgに制約となる関係 ^U を付け加えて lssg (labeled ssg) (^V, ^N, ^E, ^U) にする。

^U の例1: "type relation"

• ある Region に含まれるオブジェクトの型は {τ1, ... , τk} のどれかですよ

^U の例2: "linearity relation"

• Region n の linearity =
  • ω (n が複数のオブジェクトを含む)
  • 1 (n 中のオブジェクトが0か1)
• 「{変数∪Region}→Regionのポインタ集合」に対しても同様

実際の解析

上記の type relation とか linearity relation を使ってlssgを構成すると、例えば事前知識なしに linked list (再帰的なデータ構造の例) を抽出できる

• List の中央: ある型のオブジェクトのあるfieldから、同じ型のオブジェクトに参照のあるオブジェクトのRegion
• List のHead: 上のRegionへnxから参照を持つ linearity=1 のRegion
• List のTail: 上のRegion中のnxから参照される linearity=1 のRegion

とかまあいろいろできそうですよね (興味がそれてきたので省略)