[ruby-trunk - Feature #5839][Open] Proposal: Bitmap Marking GC

luislavena · January 4, 2012, 1:33pm

Issue #5839 has been reported by Narihiro N…

Feature #5839: Proposal: Bitmap Marking GC

Author: Narihiro N.
Status: Open
Priority: Normal
Assignee: Yukihiro M.
Category: core
Target version: 2.0.0

あけましておめでとうございます。nariです。

ビットマップマーキングGCをRuby2.0向けに作りました。

ソースコード: GitHub - authorNari/ruby: The Ruby Programming Language
パッチ:
https://github.com/authorNari/patch_bag/blob/master/ruby/gc_bitmap_using_alignment_r33786.patch

以下の環境でr33786 に対するパッチで make check が通ること、
make TESTS=“–gc-stress” test-all が無事に動いてることを確認してます。

$ ruby -v
ruby 2.0.0dev (2011-11-18 trunk 33786) [x86_64-linux]

= 性能評価

== make benchmark
make benchmark OPTS=“-r 5” の結果は以下です。

gist.github.com

https://gist.github.com/authorNari/1542547

make-benchmark.txt

benchmark results:
minimum results in each 5 measurements.
name	ruby 2.0.0dev (2011-11-18 trunk 33786) [i686-linux]	ruby 2.0.0dev-bmap (2011-11-18 trunk 33786) [i686-linux]	average difference
app_answer	0.136	0.133	-0.002
app_erb	2.393	2.466	0.075
app_factorial	4.231	4.155	-0.076
app_fib	1.386	1.262	-0.127
app_mandelbrot	3.841	3.598	-0.231
app_pentomino	33.577	34.844	1.216
app_raise	0.919	0.912	-0.003

This file has been truncated. show original

skkzipcode-mem-usage.txt

Benchmark Program is here: https://github.com/authorNari/skkzipcode

= Origin
$ ruby -v
ruby 2.0.0dev (2011-11-18 trunk 33786) [x86_64-linux]

PRCOESS_CNT : 5
SHARED_TOTAL: 59124     kb
PRIV_TOTAL  : 224892    kb

This file has been truncated. show original

全体的に実行時間は若干遅くなるようです。

マークでRVALUEのフラグを立てるだけだったのが、ビットマップ上のフ
ラグを立てるようになるので遅くなるのはしょうがないかなと…。

== skkzipcode
ビットマップマーキングではマークでRVALUEに対して書き込みがなくなるので、
Linuxで複数の子プロセスを実行した場合にも無駄なCoWが発生せず、総メモリ
使用量が少なくなるという利点があります。

skkzipcodeというサンプルプログラムで上記の点を確認しました。
skkzipcodeは、親プロセスでたくさんメモリを使ってデータを保持しておいて、
生成した子プロセスで親プロセスと共有したデータを利用します。

（/proc/PID/smapsを使って計測しています）

origin - ビットマップマーキングなし
PROCESS_CNT : 5
SHARED_TOTAL: 59124 kb
PRIV_TOTAL : 224892 kb

bmap - ビットマップマーキングあり
PROCESS_CNT : 5
SHARED_TOTAL: 170744 kb
PRIV_TOTAL : 138336 kb

PROCESS_CNTは子プロセスの数、SHARED_TOTALは子プロセスで利用している共有
メモリ量、PRIV_TOTALは私有メモリ量です。bmapの方が共有メモリを沢山使っ
ていることがわかり、私有メモリ使用量も少なくなっています。

= 実装
実装について簡単にまとめます。

ビットマップ探索高速化のため、ヒープ1ブロックのアドレスは16KBでアライ
ンメントしている
– Linuxではposix_memalign(),memalign()を利用
– Windowsでは_aligned_malloc()を利用
無駄な書き込みを防ぐため、なるべくfreelistを繋ぎ変えないようにした
– GCの時にすでにfreelistに繋ながれていたオブジェクトを再度繋ぎ直さない
freelistはスロットが持つようになった
– 不要なスロットを解放するときにグローバルなfreelistにオブジェクトが繋
がれている可能性がでてくるため
struct heaps_slotをヒープブロックに埋め込んだ

Linuxでfork()を使わないようなプログラムに対してはビットマップマーキング
の恩恵はありません。ただ、CRubyで並列プログラミングしようとするときには
fork()を使って云々するライブラリがけっこう多いので（例えばpassengerとか…）
そういうものに対しては結構効くはずです。

GCの実行時間もそれほど遅くなりませんので、fork()を使わないプログラムで
もそれほど問題にならないと思っています。

Narihiro_N · January 4, 2012, 2:33pm

ささだです．

bitmap marking 化ご苦労様です．2つ教えて下さい．

(2012/01/04 21:33), Narihiro N. wrote:

無駄な書き込みを防ぐため、なるべくfreelistを繋ぎ変えないようにした
– GCの時にすでにfreelistに繋ながれていたオブジェクトを再度繋ぎ直さない

freelistはスロットが持つようになった
– 不要なスロットを解放するときにグローバルなfreelistにオブジェクトが繋
がれている可能性がでてくるため

freelist を見ずに，bitmap を見る，みたいなのだと，free obj 探索が遅く
なっちゃう感じでしょうか．

あと，nari さんが PRO で提案していた手法だと，「ビットマップ探索高速化
のため～」云々はあまり気にしなくていいんじゃないかと思ったんですが，そう
でもないでしょうか．

あと，REE との性能比較があると興味深いと思ったけど，

いろいろ難しいかな．

パッチをちらっと見ただけでの将来的な要望ですが，この辺は gc.c の中で綺
麗に API（というかマクロ）で切り離せるところだと思うので，うまいこと整理
できるといいんでないかと思います（以前，RubyConf2011 でも喋った話ですが）．

Narihiro_N · January 4, 2012, 2:48pm

$B$^$D$b$H(B $B$f$-$R$m$G$9(B

In message “Re: [ruby-dev:45086] Re: [ruby-trunk - Feature #5839][Open]
Proposal: Bitmap Marking GC”
on Wed, 4 Jan 2012 22:33:03 +0900, SASADA Koichi [email protected]
writes:

|(2012/01/04 21:33), Narihiro N. wrote:
|> - $BL5BL$J=q$-9~$$rKI$0$?$a!"$J$k$Y$/(Bfreelist$B$r7R$.JQ$($J$$$h$&$K$7$?(B
|> – GC$B$N;~$K$9$G$K(Bfreelist$B$K7R$J$,$l$F$$$?%%V%8%'%/%H$r:FEY7R$.D>$5$J$$(B
|> - freelist$B$O%9%m%C%H$,;}$D$h$&$K$J$C$?(B
|> – $BITMW$J%9%m%C%H$r2rJ|$9$k$H$-$K%0%m!<%P%k$J(Bfreelist$B$K%%V%8%'%/%H$,7R(B
|> $B$,$l$F$$$k2DG=@-$,$G$F$/$k$?$a(B
|
|$B!!(Bfreelist $B$r8+$:$K!$(Bbitmap $B$r8+$k!$$$?$$$J$N$@$H!$(Bfree obj
$BC5:w$,CY$/(B
|$B$J$C$A$c$&46$8$G$7$g$&$+!%(B

$B!V(Bbitmap$B$“$k$+$i(Bfreelist$B$J$/$9!W$N$b$”$j$($k$H;W$$$^$9$,!“@-(B
$BG=FC@-$O$I$&$J$k$N$+$J!#L@<(E*$J(Bsweep$B$,MW$i$J$$$V$s$H3d$jEv$F(B
$B;~$K%9%-%c%s$,H/@8$9$k$N$H$N%H%l!<%I%*%U$+$J$”!#(B

|$B!!$“$H!$(Bnari $B$5$s$,(B PRO
$B$GDs0F$7$F$$$?<jK!$@$H!$!V%S%C%H%^%C%WC5:w9bB.2=(B
|$B$N$?$a$(D"7$B!W1>!9$O$”$^$j5$$K$7$J$/$F$$$$$s$8$c$J$$$+$H;W$C$?$s$G$9$,!$$=$&(B
|$B$G$b$J$$$G$7$g$&$+!%(B

memalign$B$GD>@%Z!<%8$,F@$i$l$?J}$,!“(BPRO$B$N<jK!$h$j%S%C%H%^%C%W(B
$B%F!<%V%k$rF@$k$?$a$N%a%b%j%”%/%;%9$,#1CJ8:$C$F9bB.$N$O$:$G$9!#(B
$B%S%C%H%^%C%W%F!<%V%k<hF@$O%*%V%8%'%/%H$4$H$KH/@8$7$^$9$+$i8z(B
$B$$$F$/$k$O$:$G$9!#(B

|# $B$“$H!$(BREE $B$H$N@-G=Hf3S$,$”$k$H6=L#?<$$$H;W$C$?$1$I!$(B
|# $B$$$m$$$mFq$7$$$+$J!%(B

$B$&!<$s!“(B1.8$B$H(B1.9$B$N:9$NJ}$,Bg$-$9$.$F0UL#$N$”$k@-G=Hf3S$O%`%j(B
$B$G$7$g$&!#%a%b%j>CHqNLHf3S$/$i$$$J$iM-0U5A$JHf3S$,$G$-$k$+$J!#(B

                            $B$^$D$b$H(B $B$f$-$R$m(B /:|)

Narihiro_N · January 5, 2012, 12:26am

$B!!$5$5$@$G$9!%(B

(2012/01/04 22:48), Yukihiro M. wrote:

$B!V(Bbitmap$B$"$k$+$i(Bfreelist$B$J$/$9!W$N$b$"$j$($k$H;W$$$^$9$,!"@-(B
$BG=FC@-$O$I$&$J$k$N$+$J!#L@<(E*$J(Bsweep$B$,MW$i$J$$$V$s$H3d$jEv$F(B
$B;~$K%9%-%c%s$,H/@8$9$k$N$H$N%H%l!<%I%*%U$+$J$"!#(B

$B!!%a%b%j%"%/%;%9$,8:$k!J$+$b$7$l$J$$!K$N$G!$<BB,CM$rCN$j$?$$$H$3$m$G$9!%(B
$B$^$!!$$=$N$X$s$O<BAu$K$h$k$H;W$$$^$9$,!%(B

|$B!!$"$H!$(Bnari $B$5$s$,(B PRO
$B$GDs0F$7$F$$$?<jK!$@$H!$!V%S%C%H%^%C%WC5:w9bB.2=(B
|$B$N$?$a!A!W1>!9$O$"$^$j5$$K$7$J$/$F$$$$$s$8$c$J$$$+$H;W$C$?$s$G$9$,!$$=$&(B
|$B$G$b$J$$$G$7$g$&$+!%(B

memalign$B$GD>@%Z!<%8$,F@$i$l$?J}$,!"(BPRO$B$N<jK!$h$j%S%C%H%^%C%W(B
$B%F!<%V%k$rF@$k$?$a$N%a%b%j%"%/%;%9$,#1CJ8:$C$F9bB.$N$O$:$G$9!#(B
$B%S%C%H%^%C%W%F!<%V%k<hF@$O%*%V%8%’%/%H$4$H$KH/@8$7$^$9$+$i8z(B
$B$$$F$/$k$O$:$G$9!#(B

$B!!$=$&$G$9$M!%DjNLE*$JHf3S$,$b$7$"$k$H@bF@NO$,A}$9$H;W$$$^$7$?!%(B

|# $B$"$H!$(BREE $B$H$N@-G=Hf3S$,$"$k$H6=L#?<$$$H;W$C$?$1$I!$(B
|# $B$$$m$$$mFq$7$$$+$J!%(B

$B$&!<$s!"(B1.8$B$H(B1.9$B$N:9$NJ}$,Bg$-$9$.$F0UL#$N$"$k@-G=Hf3S$O%`%j(B
$B$G$7$g$&!#%a%b%j>CHqNLHf3S$/$i$$$J$iM-0U5A$JHf3S$,$G$-$k$+$J!#(B

$B!!$O$$!$Fq$7$$$H;W$$$^$9!%$,!$2?$i$+$N;XI8$,$"$k$H!$%^!<%1%F%#%s%0$K$ONI(B
$B$5$=$&$G$9!%(B

Narihiro_N · January 5, 2012, 1:31am

nari$B$G$9!#(B

2012$BG/(B1$B7n(B5$BF|(B8:26 SASADA Koichi [email protected]:

$B!!$5$5$@$G$9!%(B

(2012/01/04 22:48), Yukihiro M. wrote:

$B!V(Bbitmap$B$“$k$+$i(Bfreelist$B$J$/$9!W$N$b$”$j$($k$H;W$$$^$9$,!“@-(B
$BG=FC@-$O$I$&$J$k$N$+$J!#L@<(E*$J(Bsweep$B$,MW$i$J$$$V$s$H3d$jEv$F(B
$B;~$K%9%-%c%s$,H/@8$9$k$N$H$N%H%l!<%I%*%U$+$J$”!#(B

$B!!%a%b%j%"%/%;%9$,8:$k!J$+$b$7$l$J$$!K$N$G!$<BB,CM$rCN$j$?$$$H$3$m$G$9!%(B
$B$^$!!$$=$N$X$s$O<BAu$K$h$k$H;W$$$^$9$,!%(B

$B$=$NJU$j$O$I$&$J$s$G$7$g$&!D!#<BAu$9$k$N$O$=$l$[$IFq$7$/$J$$$N$G!";n$7(B
$B$K<BAu$7$F7WB,$7$F$_$^$9!#(B

$B<BAuE*$K$O!“(Bsweep$B;~$K2rJ|BP>]$N%%V%8%'%/%H$KBP$7$F$O(Bobj_free()$B$r8F$V$@(B
$B$1!“(Bflags$B$O(B0$B$K$7$J$$!”(Bfreelist$B$b7R$,$J$$!“%9%m%C%H$r(Bsweep$B$7$?$”$H$K(B
bitmap$B$r%/%j%“$7$J$$!”%%V%8%'%/%H%”%m%1!<%7%g%s;~$K(Bbitmap$B%9%-%c%s!"$_(B
$B$?$$$J$N$r9M$($F$$$^$9!#(B

$B<BAu$7$FHf3S$7$F$b$h$$$G$9$,!"<BAu<T$N463P$H$7$F$OD4$Y$k$^$G$b$J(B
$B$$$h$&$J5$$b!D!#(B

|# $B$“$H!$(BREE $B$H$N@-G=Hf3S$,$”$k$H6=L#?<$$$H;W$C$?$1$I!$(B
|# $B$$$m$$$mFq$7$$$+$J!%(B

$B$&!<$s!“(B1.8$B$H(B1.9$B$N:9$NJ}$,Bg$-$9$.$F0UL#$N$”$k@-G=Hf3S$O%`%j(B
$B$G$7$g$&!#%a%b%j>CHqNLHf3S$/$i$$$J$iM-0U5A$JHf3S$,$G$-$k$+$J!#(B

$B!!$O$$!$Fq$7$$$H;W$$$^$9!%$,!$2?$i$+$N;XI8$,$"$k$H!$%^!<%1%F%#%s%0$K$ONI(B
$B$5$=$&$G$9!%(B

REE$B$H%a%b%j>CHqNL$rHf3S$7$?$N$,$“$C$?$[$&$,$$$$$+$b$7$l$^$;$s$M!#(B
passenger$B$OLLE]$=$&$J$N$G!”$^$:$O(Bskkzipcode$B$rF0$+$7$F$_$^$9!#(B

REE$B$H$N(BGC$B$NB.EYLL$NHf3S$O$1$C$3$&BgJQ$J>e$K$=$l$[$I0UL#$,$J$5$=$&$J$N$G!"(B
$B5$$,?J$_$^$;$s!D!#(B

$B!!%Q%C%A$r$A$i$C$H8+$?$@$1$G$N>-MhE*$JMWK>$G$9$,!$$3$NJU$O(B gc.c $B$NCf$Ge:(B
$BNo$K(B API$B!J$H$$$&$+%^%/%m!K$G@Z$jN%$;$k$H$3$m$@$H;W$&$N$G!$$&$^$$$3$H@0M}(B
$B$G$-$k$H$$$$$s$G$J$$$+$H;W$$$^$9!J0JA0!$(BRubyConf2011
$B$G$bC}$C$?OC$G$9$,!K!%(B

$B$=$&$G$9$M!#$=$l$O$$$m$s$J(BGC$B$rABr$7$?$$$J$!!“$H$$$&;~$K$d$i$J$$$H$$$1(B
$B$J$$$3$H$@$H;W$C$F$$$^$9!#(B
$B$^$?!”$5$5$@$5$s$,$$C$7$c$C$F$k!V$&$^$$$3$H@0M}!W$N%$%a!<%8$,$“$^$jM/(B
$B$$$F$J$$$N$G!”$I$&$$$&$b$N$+Nc$r>e$2$F$/$l$k$HA[A|$7$d$9$$$G$9!#(B

Narihiro_N · January 5, 2012, 4:31am

nari $B$G$9!#(B

2012$BG/(B1$B7n(B5$BF|(B9:48 SASADA Koichi [email protected]:

$B!!8D?ME*$K$O!$(Ballocation $B$N%3%9%H$,$I$&JQ$o$k$+!$$,5$$K$"$C$F$$$^(B
$B$9!%(Bbitmap $B$rAm%9%-%c%s$9$k$HBgJQ$J$N$G!$:G8e$N%+!<%=%k$rJ]B8$9$k!$$H$+(B
$B$+$J$!$H;W$C$F$$$^$7$?!%$^$!!$F3F~$5$l$?8e$G;d$,$d$C$F$b$$$$$G$9$,!%(B

$B$G$O!"$*$^$+$;$7$^$9(B

passenger$B$OLLE]$=$&$J$N$G!"$^$:$O(Bskkzipcode$B$rF0$+$7$F$_$^$9!#(B
REE$B$H(BRuby2.0$B%S%C%H%^!<%-%s%0$N%a%b%j;HMQNL$rHf3S$7$^$7$?!#(B
make-benchmark.txt · GitHub

Ruby2.0$B$O(BREE$B$h$j$b>J%a%b%j$J$N$G!“Am%a%b%j;HMQNL$,JQF0$7$F$$$^$9$,!”(B
$B6&M-%a%b%j;HMQNL$H;dM-%a%b%j;HMQNL$N3d9g$O$[$H$s$IJQ$o$j$J$$$h$&$G$9!#(B

$B$H$+!$$=$s$J46$8$G$9!%$?$@!$$b$A$m$s$$$m$s$J@Z$j8}$N$"$kOC$@$H;W$$$^$9$N(B
$B$G?'!9G:$_$I$3$m$K$J$k$s$8$c$J$$$+$H;W$$$^$9!%(B

$B$A$J$_$K!$(BGC $B$rA*Br!$$H$$$&$N$O9-HO0O2a$.$F4m81$J8@MU$G$O$J$$$+$H(B

$B;W$C$F$$$^$9!%(Bcopy gc $B$K$9$k$N$OL5M}$@$m$&$7!%(B

$BM}2rNOITB-$G?=$7Lu$J$$$N$G$9$,!“2?$+6qBNE*$JL\E*$O$”$k$s$G$7$g$&$+!)(B
$B%“%m%1!<%7%g%s$N@oN,$rJQ$($?$j!”%^!<%-%s%0$NJ}K!$rJQ$($?$j!“$r4JC1$K$7(B
$B$?$$$H$+$=$&$$$&OC$G$7$g$&$+!)(B
$BNc$($PJBNs%^!<%-%s%0$K4JC1$K@Z$jBX$($i$l(B
$B$k$H$+!”(Btcmalloc$B$,4JC1$K;H$($k$h$&$K$J$k$H$+!D!#(B
$B8D?ME*$K$O6qBNE*$JL\E*$,$"$C$?$[$&$,(BAPI$B$bDj5A$7$d$9$$$H;W$C$F$$$^$9!#(B

Narihiro_N · January 5, 2012, 1:48am

$B!!$5$5$@$G$9!%(B

(2012/01/05 9:30), Narihiro N. wrote:

$B$=$NJU$j$O$I$&$J$s$G$7$g$&!D!#<BAu$9$k$N$O$=$l$[$IFq$7$/$J$$$N$G!";n$7(B
$B$K<BAu$7$F7WB,$7$F$_$^$9!#(B

$B<BAuE*$K$O!"(Bsweep$B;~$K2rJ|BP>]$N%*%V%8%’%/%H$KBP$7$F$O(Bobj_free()$B$r8F$V$@(B

$B$1!"(Bflags$B$O(B0$B$K$7$J$$!"(Bfreelist$B$b7R$,$J$$!"%9%m%C%H$r(Bsweep$B$7$?$"$H$K(B

bitmap$B$r%/%j%"$7$J$$!"%*%V%8%’%/%H%"%m%1!<%7%g%s;~$K(Bbitmap$B%9%-%c%s!"$_(B
$B$?$$$J$N$r9M$($F$$$^$9!#(B

$B!!8D?ME*$K$O!$(Ballocation
$B$N%3%9%H$,$I$&JQ$o$k$+!$$,5$$K$"$C$F$$$^(B
$B$9!%(Bbitmap
$B$rAm%9%-%c%s$9$k$HBgJQ$J$N$G!$:G8e$N%+!<%=%k$rJ]B8$9$k!$$H$+(B
$B$+$J$!$H;W$C$F$$$^$7$?!%$^$!!$F3F~$5$l$?8e$G;d$,$d$C$F$b$$$$$G$9$,!%(B

$B<BAu$7$FHf3S$7$F$b$h$$$G$9$,!"<BAu<T$N463P$H$7$F$OD4$Y$k$^$G$b$J(B
$B$$$h$&$J5$$b!D!#(B

$B!!$J$k$[$I!%<+L@!uBgJQ$=$&$J$i7k9=$G$9!%(B

$B!!%Q%C%A$r$A$i$C$H8+$?$@$1$G$N>-MhE*$JMWK>$G$9$,!$$3$NJU$O(B gc.c
$B$NCf$Ge:(B

$BNo$K(B
API$B!J$H$$$&$+%^%/%m!K$G@Z$jN%$;$k$H$3$m$@$H;W$&$N$G!$$&$^$$$3$H@0M}(B

$B$G$-$k$H$$$$$s$G$J$$$+$H;W$$$^$9!J0JA0!$(BRubyConf2011
$B$G$bC}$C$?OC$G$9$,!K!%(B

$B$=$&$G$9$M!#$=$l$O$$$m$s$J(BGC$B$rABr$7$?$$$J$!!"$H$$$&;~$K$d$i$J$$$H$$$1(B
$B$J$$$3$H$@$H;W$C$F$$$^$9!#(B
$B$^$?!"$5$5$@$5$s$,$$C$7$c$C$F$k!V$&$^$$$3$H@0M}!W$N%$%a!<%8$,$"$^$jM/(B
$B$$$F$J$$$N$G!"$I$&$$$&$b$N$+Nc$r>e$2$F$/$l$k$HA[A|$7$d$9$$$G$9!#(B

$B!!Nc$($P!$(Bmark $BItJ,$r%^%/%m2=$9$k$H$+!$(Bslot $B$N(B allocation
$B$r%^%/%m2=$9$k(B
$B$H$+!$$=$s$J46$8$G$9!%$?$@!$$b$A$m$s$$$m$s$J@Z$j8}$N$"$kOC$@$H;W$$$^$9$N(B
$B$G?’!9G:$_$I$3$m$K$J$k$s$8$c$J$$$+$H;W$$$^$9!%(B

$B$A$J$_$K!$(BGC

$B$rA*Br!$$H$$$&$N$O9-HO0O2a$.$F4m81$J8@MU$G$O$J$$$+$H(B

$B;W$C$F$$$^$9!%(Bcopy gc $B$K$9$k$N$OL5M}$@$m$&$7!%(B

Narihiro_N · January 6, 2012, 2:39am

(2012/01/05 12:30), Narihiro N. wrote:

$BM}2rNOITB-$G?=$7Lu$J$$$N$G$9$,!“2?$+6qBNE*$JL\E*$O$”$k$s$G$7$g$&$+!)(B
$B%"%m%1!<%7%g%s$N@oN,$rJQ$($?$j!"%^!<%-%s%0$NJ}K!$rJQ$($?$j!"$r4JC1$K$7(B
$B$?$$$H$+$=$&$$$&OC$G$7$g$&$+!)(B $BNc$($PJBNs%^!<%-%s%0$K4JC1$K@Z$jBX$($i$l(B
$B$k$H$+!"(Btcmalloc$B$,4JC1$K;H$($k$h$&$K$J$k$H$+!D!#(B
$B8D?ME*$K$O6qBNE*$JL\E*$,$"$C$?$[$&$,(BAPI$B$bDj5A$7$d$9$$$H;W$C$F$$$^$9!#(B

$B!!0lHV6qBNE*$JOC$H$7$F$O!$4JC1$K:#2s$N;EAH$_$r30$;$k$h$&$K$J$k!$$H$$$&46(B
$B$8$G$7$g$&$+!%<B9T;~$KJQ99$G$-$kI,MW$O$J$$$+$H;W$$$^$9$,!$3+H/;~$K;n9T:x(B
$B8m$7$d$9$/$J$k$N$O$h$$$s$G$O$J$$$+$H;W$$$^$9!%(B

$B!!$^$?!$6D$k$H$*$j!$JL$N<BAu$r;n$9$3$H$,?’!9$G$-$k$s$8$c$J$$$+$H!%$^$!!$(B
$B$3$NJU$b<u1W<TIiC4$H$$$&9M$($+$i!$:#EY;d$N$[$&$G@0M}$7$h$&$H;W$$$^$9!%(B

Narihiro_N · January 6, 2012, 4:31am

2012$BG/(B1$B7n(B6$BF|(B10:39 SASADA Koichi [email protected]:

$B$J$k$[$I!#M}2r$7$^$7$?!*!!;d$b$$$$$H;W$$$^$9!#(B

$B!!$^$?!$6D$k$H$*$j!$JL$N<BAu$r;n$9$3$H$,?'!9$G$-$k$s$8$c$J$$$+$H!%$^$!!$(B
$B$3$NJU$b<u1W<TIiC4$H$$$&9M$($+$i!$:#EY;d$N$[$&$G@0M}$7$h$&$H;W$$$^$9!%(B

$B$h$m$7$/$*4j$$$7$^$9(B

Narihiro_N · January 5, 2012, 6:46am

$B$^$D$b$H(B $B$f$-$R$m$G$9(B

$BNi57$H$7$F(Bruby-core$B$GJs9p$7$?$i!"%^!<%8$7$F$b$$$$$s$8$c$J$$!)(B

In message “Re: [ruby-dev:45085] [ruby-trunk - Feature #5839][Open]
Proposal: Bitmap Marking GC”
on Wed, 4 Jan 2012 21:33:17 +0900, Narihiro N.
[email protected] writes:

|Issue #5839 has been reported by Narihiro N…
|
|----------------------------------------
|Feature #5839: Proposal: Bitmap Marking GC
|Feature #5839: Proposal: Bitmap Marking GC - Ruby master - Ruby Issue Tracking System
|
|Author: Narihiro N.
|Status: Open
|Priority: Normal
|Assignee: Yukihiro M.
|Category: core
|Target version: 2.0.0
|
|
|$B$“$1$^$7$F$$a$G$H$&$4$6$$$^$9!#(Bnari$B$G$9!#(B
|
|$B%S%C%H%^%C%W%^!<%-%s%0(BGC$B$r(BRuby2.0$B8~$1$K:n$j$^$7$?!#(B
|
|$B%=!<%9%3!<%I(B: GitHub - authorNari/ruby: The Ruby Programming Language
|$B%Q%C%A(B:
patch_bag/ruby/gc_bitmap_using_alignment_r33786.patch at master · authorNari/patch_bag · GitHub
|
|$B0J2<$N4D6-$G(Br33786 $B$KBP$9$k%Q%C%A$G(B make check $B$,DL$k$3$H!“(B
|make TESTS=”–gc-stress" test-all $B$,L5;v$KF0$$$F$k$3$H$r3NG’$7$F$^$9!#(B
|
|$ ruby -v
|ruby 2.0.0dev (2011-11-18 trunk 33786) [x86_64-linux]
|
|= $B@-G=I>2A(B
|
|== make benchmark
|make benchmark OPTS=“-r 5” $B$N7k2L$O0J2<$G$9!#(B
|make-benchmark.txt · GitHub
|$BA4BNE$K<B9T;~4V$O<c43CY$/$J$k$h$&$G$9!#(B
|
|$B%^!<%/$G(BRVALUE$B$N%U%i%0$rN)$F$k$@$1$@$C$?$N$,!”%S%C%H%^%C%W>e$N%U(B
|$B%i%0$rN)$F$k$h$&$K$J$k$N$GCY$/$J$k$N$O$7$g$&$,$J$$$+$J$H!D!#(B
|
|== skkzipcode
|$B%S%C%H%^%C%W%^!<%-%s%0$G$O%^!<%/$G(BRVALUE$B$KBP$7$F=q$-9~$$,$J$/$J$k$N$G!“(B
|Linux$B$GJ#?t$N;R%W%m%;%9$r<B9T$7$?>l9g$K$bL5BL$J(BCoW$B$,H/@8$;$:!“Am%a%b%j(B
|$B;HMQNL$,>/$J$/$J$k$H$$$&MxE@$,$”$j$^$9!#(B
|
|skkzipcode$B$H$$$&%5%s%W%k%W%m%0%i%$G>e5-$NE@$r3NG'$7$^$7$?!#(B |skkzipcode$B$O!"?F%W%m%;%9$G$?$/$5$s%a%b%j$r;H$C$F%G!<%?$rJ];}$7$F$*$$$F!"(B |$B@8@.$7$?;R%W%m%;%9$G?F%W%m%;%9$H6&M-$7$?%G!<%?$rMxMQ$7$^$9!#(B |https://github.com/authorNari/skkzipcode |$B!J(B/proc/PID/smaps$B$r;H$C$F7WB,$7$F$$$^$9!K(B | |origin - $B%S%C%H%^%C%W%^!<%-%s%0$J$7(B |PROCESS_CNT : 5 |SHARED_TOTAL: 59124 kb |PRIV_TOTAL : 224892 kb | |bmap - $B%S%C%H%^%C%W%^!<%-%s%0$"$j(B |PROCESS_CNT : 5 |SHARED_TOTAL: 170744 kb |PRIV_TOTAL : 138336 kb | |PROCESS_CNT$B$O;R%W%m%;%9$N?t!"(BSHARED_TOTAL$B$O;R%W%m%;%9$GMxMQ$7$F$$$k6&M-(B |$B%a%b%jNL!"(BPRIV_TOTAL$B$O;dM-%a%b%jNL$G$9!#(Bbmap$B$NJ}$,6&M-%a%b%j$rBt;3;H$C(B |$B$F$$$k$3$H$,$o$+$j!";dM-%a%b%j;HMQNL$b>/$J$/$J$C$F$$$^$9!#(B | |= $B<BAu(B |$B<BAu$K$D$$$F4JC1$K$^$H$a$^$9!#(B | |- $B%S%C%H%^%C%WC5:w9bB.2=$N$?$a!"%R!<%W(B1$B%V%m%C%/$N%"%I%l%9$O(B16KB$B$G%"%i%$(B | $B%s%a%s%H$7$F$$$k(B |-- Linux$B$G$O(Bposix_memalign(),memalign()$B$rMxMQ(B |-- Windows$B$G$O(B_aligned_malloc()$B$rMxMQ(B |- $BL5BL$J=q$-9~$_$rKI$0$?$a!"$J$k$Y$/(Bfreelist$B$r7R$.JQ$($J$$$h$&$K$7$?(B |-- GC$B$N;~$K$9$G$K(Bfreelist$B$K7R$J$,$l$F$$$?%*%V%8%'%/%H$r:FEY7R$.D>$5$J$$(B |- freelist$B$O%9%m%C%H$,;}$D$h$&$K$J$C$?(B |-- $BITMW$J%9%m%C%H$r2rJ|$9$k$H$-$K%0%m!<%P%k$J(Bfreelist$B$K%*%V%8%'%/%H$,7R(B | $B$,$l$F$$$k2DG=@-$,$G$F$/$k$?$a(B |- struct heaps_slot$B$r%R!<%W%V%m%C%/$KKd$a9~$s$@(B | |Linux$B$G(Bfork()$B$r;H$o$J$$$h$&$J%W%m%0%i%$KBP$7$F$O%S%C%H%^%C%W%^!<%-%s%0(B
|$B$N287C$O$”$j$^$;$s!#$?$@!"(BCRuby$B$GJBNs%W%m%0%i%%s%0$7$h$&$H$9$k$H$-$K$O(B
|fork()$B$r;H$C$F1>!9$9$k%i%$%V%i%j$,$1$C$3$&B?$$$N$G!JNc$($P(Bpassenger$B$H$+!D!K(B
|$B$=$&$$$&$b$N$KBP$7$F$O7k9=8z$/$O$:$G$9!#(B
|
|GC$B$N<B9T;~4V$b$=$l$[$ICY$/$J$j$^$;$s$N$G!"(Bfork()$B$r;H$o$J$$%W%m%0%i%`$G(B
|$B$b$=$l$[$ILdBj$K$J$i$J$$$H;W$C$F$$$^$9!#(B
|
|
|
|–
|http://redmine.ruby-lang.org

Narihiro_N · October 23, 2012, 7:20am

Issue #5839 has been updated by dafiku (dafi harisy).

Everlastingly, an issue with the intention of I am passionate in this
vicinity. I be inflicted with looked for in rank of this feature for the
last numerous hours. Your locate is greatly valued.
http://www.yourhousecontents.com/
http://www.electroscanogram.com/
http://www.videophototravel.info/
http://www.supershinelaundry.com/
http://www.ywor.info/
http://www.bicity.info/
http://www.ubidyne.info/

Feature #5839: Proposal: Bitmap Marking GC

Author: authorNari (Narihiro N.)
Status: Closed
Priority: Normal
Assignee: matz (Yukihiro M.)
Category: core
Target version: 2.0.0

あけましておめでとうございます。nariです。

ビットマップマーキングGCをRuby2.0向けに作りました。

ソースコード: GitHub - authorNari/ruby: The Ruby Programming Language
パッチ:
patch_bag/ruby/gc_bitmap_using_alignment_r33786.patch at master · authorNari/patch_bag · GitHub

以下の環境でr33786 に対するパッチで make check が通ること、
make TESTS=“–gc-stress” test-all が無事に動いてることを確認してます。

$ ruby -v
ruby 2.0.0dev (2011-11-18 trunk 33786) [x86_64-linux]

= 性能評価

== make benchmark
make benchmark OPTS=“-r 5” の結果は以下です。

gist.github.com

https://gist.github.com/authorNari/1542547

make-benchmark.txt

benchmark results:
minimum results in each 5 measurements.
name	ruby 2.0.0dev (2011-11-18 trunk 33786) [i686-linux]	ruby 2.0.0dev-bmap (2011-11-18 trunk 33786) [i686-linux]	average difference
app_answer	0.136	0.133	-0.002
app_erb	2.393	2.466	0.075
app_factorial	4.231	4.155	-0.076
app_fib	1.386	1.262	-0.127
app_mandelbrot	3.841	3.598	-0.231
app_pentomino	33.577	34.844	1.216
app_raise	0.919	0.912	-0.003

This file has been truncated. show original

skkzipcode-mem-usage.txt

Benchmark Program is here: https://github.com/authorNari/skkzipcode

= Origin
$ ruby -v
ruby 2.0.0dev (2011-11-18 trunk 33786) [x86_64-linux]

PRCOESS_CNT : 5
SHARED_TOTAL: 59124     kb
PRIV_TOTAL  : 224892    kb

This file has been truncated. show original

全体的に実行時間は若干遅くなるようです。

マークでRVALUEのフラグを立てるだけだったのが、ビットマップ上のフ
ラグを立てるようになるので遅くなるのはしょうがないかなと…。

== skkzipcode
ビットマップマーキングではマークでRVALUEに対して書き込みがなくなるので、
Linuxで複数の子プロセスを実行した場合にも無駄なCoWが発生せず、総メモリ
使用量が少なくなるという利点があります。

skkzipcodeというサンプルプログラムで上記の点を確認しました。
skkzipcodeは、親プロセスでたくさんメモリを使ってデータを保持しておいて、
生成した子プロセスで親プロセスと共有したデータを利用します。

（/proc/PID/smapsを使って計測しています）

origin - ビットマップマーキングなし
PROCESS_CNT : 5
SHARED_TOTAL: 59124 kb
PRIV_TOTAL : 224892 kb

bmap - ビットマップマーキングあり
PROCESS_CNT : 5
SHARED_TOTAL: 170744 kb
PRIV_TOTAL : 138336 kb

PROCESS_CNTは子プロセスの数、SHARED_TOTALは子プロセスで利用している共有
メモリ量、PRIV_TOTALは私有メモリ量です。bmapの方が共有メモリを沢山使っ
ていることがわかり、私有メモリ使用量も少なくなっています。

= 実装
実装について簡単にまとめます。

ビットマップ探索高速化のため、ヒープ1ブロックのアドレスは16KBでアライ
ンメントしている
– Linuxではposix_memalign(),memalign()を利用
– Windowsでは_aligned_malloc()を利用
無駄な書き込みを防ぐため、なるべくfreelistを繋ぎ変えないようにした
– GCの時にすでにfreelistに繋ながれていたオブジェクトを再度繋ぎ直さない
freelistはスロットが持つようになった
– 不要なスロットを解放するときにグローバルなfreelistにオブジェクトが繋
がれている可能性がでてくるため
struct heaps_slotをヒープブロックに埋め込んだ

Linuxでfork()を使わないようなプログラムに対してはビットマップマーキング
の恩恵はありません。ただ、CRubyで並列プログラミングしようとするときには
fork()を使って云々するライブラリがけっこう多いので（例えばpassengerとか…）
そういうものに対しては結構効くはずです。

GCの実行時間もそれほど遅くなりませんので、fork()を使わないプログラムで
もそれほど問題にならないと思っています。