Efficient Type Inclusion Tests (2000)
they call packed encoding, bit-packed-encoding and compact encoding. All three perform worse than hierarchical encoding if the total size of the data tables is used as the only criterion. However, these algorithms are muh faster and are therefore more suitable for an environment where the class hierarchy maybe dynamically updated, as with Java or Smalltalk, for example.
オブジェクト指向言語では、型の包含関係(サブタイプ関係)をテストする必要がある。これは多くの場合で実行時に行われ、パフォーマンスに影響する。
従来の手法には、リンクリストやハッシュテーブルを用いる非定数時間のアルゴリズムと、バイナリマトリックスを用いる定数時間のアルゴリズムがあった。しかし前者は遅く、後者は空間効率が悪い。
本論文では、packed encoding、bit-packed encoding、compact encodingの3つの新しい符号化手法を提案している。これらは定数時間で型包含テストが可能で、かつ空間効率が良い。
Packed encodingは従来のCohenのアルゴリズムを多重継承に拡張したもので、テストが4命令で済む。
Bit-packed encodingはさらに空間を節約する可変長フォーマットである。
Compact encodingは分散型のディスパッチテーブルの手法を応用したものである。
11のベンチマークにおいて、これらの新しい手法は従来手法に比べてパフォーマンスと空間効率で優れていることが示された。特にpacked encodingが実行時間と生成時間の両面で優れていた。
階層構造の変更への対応も議論されており、新しい手法は増加変更には対応できるが、破壊的変更には全体の再計算が必要になる。
hr.icon
Packed Encoding
型をバケット(bucket)に割り当てる。同じバケットに入る型は、共通のsubtypeを持たないようにする。
各型には一意の識別子(tid)を割り当てる。ただし、同じバケット内の型には一意である必要はない。
実行時の型表現は、バケット番号とすべての祖先型のtidからなる列(row)で構成される。
型包含テストは、オブジェクトのバケット番号とrowから対象型のtidを取り出し、比較するだけで済む。この操作は4命令で実行可能。
バケットへの割り当ては、単一継承部分と多重継承部分を分けて効率的に行われる。
packed encodingの利点
テストが非常に高速(4命令)
空間効率が良い(バイナリマトリックスより優れる)
符号化の生成が高速
階層構造の増加変更に対応できる
一方で、階層が完全に平坦な場合は空間効率が悪化する点が欠点。しかし、そのような極端な階層は稀であると考えられます。全体として、packed encodingはオブジェクト指向言語における型包含テストに適した、実用的な手法であると評価されている
packed ecoding アルゴリズム
初めに、各型の子孫型の集合を計算し、同じバケットに割り当てられた型の子孫集合の和集合を維持するというシンプルなアルゴリズムを紹介しています。しかし、このアプローチでは大規模な集合の和集合・積集合の計算が必要となり、非常に非効率的であることを指摘しています。
そこで、単一継承部分と多重継承部分を分離し、より洗練されたバケット割り当てルールを提案しています。具体的には、以下の3つの型のサブセットを定義しています。
join型: 複数の親を持つが、子は全て単一継承の型 join(T) = {x ∈ multis(T) | ∄y ∈ multis(T) : y <: x}
spine型: join型のすべての祖先型 spine(T) = {x ∈ ancestors(y) | y ∈ join(T)}
plain型: join型でもspine型でもない、単一継承の型 plain(T) = T - (spine(T) ∪ join(T))
このように継承の種類で型を分類することで、バケット割り当てのルールを単純化し、効率的なアルゴリズムを実現できるという考え方です。この手法は単純でありながら、先行研究のアルゴリズムよりも1桁程度高速であると述べられています。
level_order(S)は、集合Sに含まれる型をレベル(ルートからの距離)の順に並べたリストを返す関数です。
code:text
ただし、
N = |S| (Sの要素数)
level(xi) ≤ level(xi+1) (xiのレベル ≤ xi+1のレベル)
rev_level_order(S)は、levelの降順で並べたリストを返す
code:text
ただし、
N = |S|
level(xi) ≥ level(xi+1) (xiのレベル ≥ xi+1のレベル)
Rule3
code:text
Rule 3 Bucket assignment (plain and join):
γ(x) = γ(y) ⇒ x ∉ ancestors(y) (a)
γ(x) = γ(y) ⇒ y ∉ ancestors(x) (b)
ただし、x ∈ join(T) ∪ plain(T), y ∈ join(T) ∪ plain(T), x ≠ y
単一継承の場合、ある2つの型xとyに共通の子孫型が存在するための必要十分条件が、xがyの祖先型またはyがxの祖先型であることだから (??? join は多重継承では? 違うか、join の descendants はひとつだけ)
これを満たせば Rule1 も満たされるはず
Rule4 (bucket assignment (spine)
code:text
Rule 4 Bucket assignment (spine):
γ(x) = γ(y) ⇒ joins(x) ∩ joins(y) = ∅
ただし、
x ∈ spine(T), y ∈ spine(T), x ≠ y
joins(z) = descendants(z) ∩ join(T)
joins(x)は、xの子孫で join型に属する型の集合を表します。 つまり、joins(x)に含まれる型が、xから多重継承の影響を受けている型となります。
同じバケットに割り当てられるspine型は、joins集合が共通部分を持ってはならない
joins(x)との共通部分があれば、xとyに共通の子孫(join型の子孫)が存在する可能性があるからです。
spine型は多重継承の影響を受ける型なので、単にancestors関係だけでは共通の子孫の有無を判別できません。そこで、join型の子孫に着目しています。
Evaluation
4つの指標
the runtime characteristics of the type test algorithms
space requirements of the associated encoding,
generation time of the encoding
suitability for incremental hierarchy modifications
binary matrix / NHE / packed encoding / bit-packed encoding / compact encoding
NHE has consistently better compression rates
413 to 47