GC can be faster than stack allocation

GC can be faster than stack allocation
辻祥太朗
峯松研 B4
June 23, 2014
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
1 / 32
はじめに
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
2 / 32
はじめに
紹介する論文について
今回紹介する論文は、
Andrew W Appel, ”Garbage Collection Can Be Faster Than Stack
Allocation,” Inf. Process. Lett., pp. 275-279, Elsevier North-Holland,
1987
どういう内容かをタイトルからざっくりと考えると、
”””GC はスタックにオブジェクトを割り当てるより速い”””
ということ。
しかし、それを言うためには、
どういう GC を使うのか
どういう条件なら GC が速いのか
をはっきりと述べなければならない。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
3 / 32
はじめに
論文の著者
論文の著者は Princeton 大学の Andrew W. Appel
教授。
主にコンパイラの理論、プログラム検証の研
究をしている。
コンパイラ作りのための教科書などを出して
いる。
最近はプログラム検証がメインらしい。
今回紹介する論文は Appel の初期の論文。
Figure: Prof. Andrew
W. Appel
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
4 / 32
メモリ割り当ての方法
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
5 / 32
メモリ割り当ての方法
Stack Allocation v. Heap Allocation
Stack Allocation
Storage Allocation の方法の一つに Stack Allocation[1] がある。
これは procedure の呼び出しごとに activation record を stack に push し、
procedure から抜けたときに pop する。以下のような特徴を持っている。
Procedure の異なる呼び出しの間で局所変数の束縛を共有しない。
すなわち再帰呼び出しが可能になる。
Stack に割り当てられた変数の値は一回の呼び出しの間だけしか寿
命を持たない。
オブジェクトのサイズが事前に分かっていないと割り当てられない。
多くの言語において手続き呼び出しに関しては Stack Allocation が採用さ
れている。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
6 / 32
メモリ割り当ての方法
Stack Allocation v. Heap Allocation
Heap Allocation
Stack は LIFO の構造なのでオブジェクトの寿命が分からないと使いづ
らい。
そこで activation record や動的なデータ構造が手続きを超えて生きられる
ように自由にメモリを割り当てられるようにするのが Heap Allocation[1]
である。
Heap Allocation の特徴として以下のことが挙げられる。
動的なデータ構造の構築が可能。
割り当てるメモリのサイズをプログラムの実行中に変化させること
ができる。
手続きを超えた寿命を持っているので戻り値として返すことがで
きる。
Activation record を heap に確保することで第一級のオブジェクトと
して手続きを扱える。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
7 / 32
メモリ割り当ての方法
Explicit Memory Management v. Garbage Collection
Explicit Memory Management
Heap Allocation で動的にオブジェクトを作れるとは言っても、寿命が尽
きたら割り当てられたメモリを解放する必要がある。
原始的にはプログラマが陽に free するという実装になる。
しかし、データ構造が複雑になるほどプログラマが管理するのは煩雑に
なる。（Lisp で自分で free しろと言われたらおそらく誰だって発狂する。）
そこで Garbage Collection が考案された。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
8 / 32
メモリ割り当ての方法
Explicit Memory Management v. Garbage Collection
Garbage Collection
Garbage Collection は Lisp のメモリ管理のために
McCarthy により考案された [2]。
最初に考案された GC のアルゴリズムは、free-list
につながれたメモリセルを cons で割り当てていき、
free-list が空になったら到達可能なメモリセルに
マークを付けて、マークされていないものを回収
して再び free-list につなぐというものであった。
（つまり Mark-Sweep 方式である。）
当然ながらこれはメモリセル全体を走査しないと
いけないので時間がかかる。
そのため GC では効率的なプログラムを作れないと Figure: Prof. John
McCarthy
思われてしまっていた。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
9 / 32
メモリ割り当ての方法
Explicit Memory Management v. Garbage Collection
Garbage Collection
当然ながらなるべく GC を使わないようなプログラムを作ることを目指
すのがトレンドになっていた。
例えば、Guy L. Steele はコンパイラの最適化手法を研究してなるべく GC
の負荷を減らすような Lisp コンパイラ1 を実装した [3]。
しかし、それではコンパイラが複雑になってしまう。
そこで十分な量のメモリがあれば GC のコストが減ることを Appel は示
そうと考えた。
1
Lisp というよりは、ALGOL-60 の影響を受けて Lexical scope を導入した
Scheme のコンパイラ。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
10 / 32
Copy GC とそのコスト
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
11 / 32
Copy GC とそのコスト
Copy GC
今回扱う GC のアルゴリズムとして Copy GC を選ぶ。
Copy GC ではメモリを tospace と fromspace の二つの領域に分けて、
fromspace 中の到達可能なセルを深さ優先探索で走査して、tospace にコ
ピーする。
探索にかかる時間は到達可能なセルの個数に比例する。コピーにかかる
時間は、コピーするセルのサイズに比例し、またセル毎に一定のオー
バーヘッドがある。
Copy GC で重要なのは、到達不可能なセルにはアクセスしないことであ
る。そのため Mark-Sweep のようにメモリセルの総量に比例する時間が
かかることはない。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
12 / 32
Copy GC とそのコスト
Copy GC
一回の GC にかかる時間を計算する。
A : 到達可能なセルの個数
s : セルの平均サイズ
M : 2 つのメモリ空間の 1 つ当たりのサイズ
深さ優先探索とコピーにかかる時間がセル毎に一定の値 c1 であり、さら
にポインタ毎に一定回数の操作 c2 が必要だとする。このとき求める時
間は、
(c1 + c2 s) A
(1)
となる。
したがって、GC は M には依存しない。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
13 / 32
Copy GC とそのコスト
Copy GC
毎回の GC で到達可能なセルの個数は一定だと仮定して、セル当たりの
GC コストを計算する。
G を GC と GC の間に割り当てることができるセルの個数として GC コス
トで割る。
まず、G は全体のセルの個数から到達可能なセルの個数を引いたものだ
から、
M
G=
−A
(2)
s
となる。
よってセル当たりの GC コスト g は、式 (1) を式 (2) で割って、
g=
(全体の GC コスト)
(c1 + c2 s)A
(c1 + c2 s)A
=
=
(割当可能なセルの数)
G
M/s − A
(3)
となる。（これは mark-cons 比に比例定数を除けば一致する。）
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
14 / 32
明示的解放のコストが高いこと
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
15 / 32
明示的解放のコストが高いこと
明示的解放のコストが高いこと
十分な量のメモリがあれば GC は低コストであることを示す。
Stack からの pop もしくは不要になったセルの明示的解放にかかるコスト
を定数 f とする。GC のコスト g と拮抗する点は、
f =g
(c1 + c2 s)A
f =
M/s − A
c1 + c2 s
f =
M/sA − 1
M
c1 + c2 s
=
+1
sA
f
(4)
となる。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
16 / 32
明示的解放のコストが高いこと
明示的解放のコストが高いこと
もし式 (4) の左辺 M/sA が右辺より大きくなれば GC は明示的解放より低
コストになる。
例えば、各定数の値を以下のように設定してみる。
c1 = 3 instructions
c2 = 6 instructions
s = 3 words
f = 2 instructions
このときの拮抗点での M/sA の値は、
M/sA = (3 + 6 × 3)/2 + 1 = 11.5
(5)
となる。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
17 / 32
実験結果
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
18 / 32
実験結果
実験結果 (1)
Appel は 128MB のメモリを搭載した VAX-11/785 において Standard-ML
のコードをコンパイルすることで実際に GC のコストが低下するか実験
した。
その結果を以下に示す。
Memory
4M
8
16
64
M
2M
4
8
32
辻祥太朗 (峯松研 B4)
CPU time
663 sec
467
439
431
GC time
232 sec
36
8
0
# GC’s
34
7
3
0
GC can be faster than stack allocation
time/GC
7 sec
5
3
*
M/sA − 1
0.5
2.5
6.7
29
June 23, 2014
19 / 32
実験結果
実験結果 (2)
-4-
only to calibrate the measurement, however, and come to the much stronger conclusion: As mem
increases, the number of garbage collections becomes proportionately fewer, and the time per garbage
lection does not increase.
Section 2 predicts that garbage collection time should be inversely proportional to M/sA − 1.
graph of 1/g versus M/sA − 1 supports the conclusion that total garbage collection time is approxima
inversely proportional to excess memory:
確かに実験結果から M を大きくするほど
GC にかかる時間が短くなり、GC の回数も
減っていることがわかる。また、M = 32 で
は GC は全く行われていない。
M/sA − 1 は M にだいたい比例して大きく
なっている。
0.3
0.2
1/g
0.1
0
2
4
6
M
− 1
sA
また、M/sA − 1 が g に反比例していること
5. Allocating from the heap
The previous section
shows that M/sA
freeing a heap −
cell by
collection との
is cheaper (if ther
が式 (4) から分かるが、これも実験データ
Figure:
1garbage
と 1/g
enough memory) than popping a stack. Now consider the cost of allocating a cell. In LISP, this is t
cally expressed as (cons A B), meaning ‘‘allocate a two-word cell containing the values A and B,
関係
に合致している。（図 3）
return a pointer to it. Let us assume that in any scheme, the values A and B must be stored into mem
any instructions other than the ones to store A and B count as overhead.
With a compacting garbage collector, the unallocated memory is always a contiguous region. T
is, there is not a free list; instead, there is a free area of memory. The function (cons A B) could be im
mented with these machine instructions:
1.
2.
3.
4.
5.
6.
辻祥太朗 (峯松研 B4)
Test free-space pointer against free-space limit.
If the limit has been reached, call the garbage collector.
Subtract 2 (the size of a cons cell) to the free-space pointer.
Store A into new cell.
Store B into new cell.
Return current value of free-space pointer.
Thisstack
code sequence
assumes that the cells are allocated starting
addresses and
GC can be faster than
allocation
Juneat the
23,higher
2014
20moving
/ 32tow
Heap からの割り当てとそのコスト
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
21 / 32
Heap からの割り当てとそのコスト
Heap からの割り当て
割り当てコスト
これまでは解放の方に焦点を当てていたが、割当についても考える。
Copy GC による割当の手順は次のようになる。
1
free-space pointer が free-space limit に到達していないかテスト。
2
もし limit に到達していれば GC を走らせる。
3
cons cell のサイズだけ pointer を減算する。
4
cons cell の car と cdr に値を書き込む。
5
free-space pointer の現在の値を返す。
一見、この手順は stack 操作よりもコストがかかるように見える。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
22 / 32
Heap からの割り当てとそのコスト
Heap からの割り当て
Stack Allocation との比較
1 番目の limit のテストは仮想記憶を用いれば trap を使って GC を起
動することができるので削ることができる。
VAX では mov 命令がポインタ減算をできるので 3 番目の操作も削
れる。
したがって、2 命令で cons を実装出来るので car と cdr に入れる値を
push するのと変わらない命令数になる。
うまく修正を加えれば手続きの activation record も stack に割り当てるの
と同じくらいのコストで heap に割り当てられる。
stack から pop するのは同様に 2 命令必要だが、GC は明示的解放を行わ
ないからこのオーバーヘッドがないから、GC の方が有利と言える。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
23 / 32
論文に対する考察
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
24 / 32
論文に対する考察
議論の要点
結局のところ、メモリの割当と解放には一定のコストが必要。どうあが
いてもタダでは手に入れられない。
Stack Allocation にしろ、Explicit な Heap Allocation にしろ、Garbage
Collection にしろ割当には同程度のコストがかかる。
解放のコストをどのタイミングで支払うかによって実行時間全体で見た
ときの単位当たりのコストが変わってくることが要点になる。
生きているオブジェクトよりもゴミの方が多ければ多いほど Copy GC は
効率的に動く。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
25 / 32
論文に対する考察
議論の問題点
この論文では実行時間全体で GC にかかる時間を均している。
確かに Appel が実験で用いた SML のコンパイラのようなプログラムでは
実行中に GC で停まってようが問題はない。
しかし、対話型のプログラムでは不都合が生じる。
→おそらく Incremental GC を用いれば対話型であっても問題ない。（e.g.
Baker のアルゴリズム [4]）
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
26 / 32
論文に対する考察
現代のアーキテクチャでも通用するか？(1)
スワップのことを考えると GC で大きな領域を操作するのはダメ
おそらく普通にプログラムを実行していれば page out されている page が
存在するはず。これにアクセスしてしまうとディスクから page を読み込
んでこないといけないので時間がかかる。（1 page アクセスするだけでも
数 msec は待たされる [5]。）
したがって、単純な Copy GC では性能の低下を招く可能性がある。
世代別 GC を導入すればよいだろう。
ただしその場合は M を 1 つの世代に対応する領域のサイズで、世代毎の
メモリセル数に応じた M/sA の値をうまく調整してやる必要がある。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
27 / 32
論文に対する考察
現代のアーキテクチャでも通用するか？(2)
式 (4) の左辺の値、
M
c1 + c2 s
=
+1
sA
f
は現在の x86-64 だとどうなるだろうか？
例えば、セルをコピーしてカウンタをインクリメントするのに word 毎に
約 2 命令、セルのアドレスを書き換えてから次のセルを処理するために
再帰するのに約 6 命令かかるとしよう。
また、セルの平均サイズは 24 bytes = 3 words とする。解放コストは約 2
命令だとしよう。
c1 = 2 instructions
c2 = 6 instructions
s = 3 words
f = 2 instructions
こうするとほぼ値は先ほどと変わらず、M/sA = 11 となる。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
28 / 32
論文に対する考察
結局どうなの？
さすがに到達可能なオブジェクト量の 10 倍の領域を用意するのは贅沢す
ぎる。
現実的なサイズで GC のコストを償却できれば嬉しいが、やっぱりそう
はいかなさそう。
結論
贅沢にメモリを使えば GC は速くなる。
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
29 / 32
参考文献
1
はじめに
2
メモリ割り当ての方法
3
Copy GC とそのコスト
4
明示的解放のコストが高いこと
5
実験結果
6
Heap からの割り当てとそのコスト
7
論文に対する考察
8
参考文献
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
30 / 32
参考文献
参考文献 I
[1] Richard Jones and Rafael Lins.
Garbage Collection: Algorithms for Automatic Dynamic Memory
Management.
John Wiley & Sons, Inc., New York, NY, USA, 1996.
[2] John McCarthy.
Recursive functions of symbolic expressions and their computation by
machine, part i.
Commun. ACM, 3(4):184–195, April 1960.
[3] Guy L. Steele, Jr.
Rabbit: A compiler for scheme.
Technical report, Cambridge, MA, USA, 1978.
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
31 / 32
参考文献
参考文献 II
[4] Henry G. Baker, Jr.
List processing in real time on a serial computer.
Commun. ACM, 21(4):280–294, April 1978.
[5] Abraham Silberschatz, Peter B. Galvin, and Greg Gagne.
Operating System Concepts.
Wiley Publishing, 9th edition, 2012.
[6] Andrew W. Appel.
Garbage collection can be faster than stack allocation.
Inf. Process. Lett., 25(4):275–279, June 1987.
辻祥太朗 (峯松研 B4)
GC can be faster than stack allocation
June 23, 2014
32 / 32

Download Report