Gauche > Archives > 2011/07/14

2011/07/14 02:22:11 UTC齊藤
#
↑老人の擬人化キャラとか誰得…
2011/07/14 04:48:07 UTCひげぽん
#
何この面白い流れw
2011/07/14 04:51:23 UTCko1
#
返事が遅くなってしまいましたが,mark/sweep の手間は確実にboehm gcのほうがかかると思うので,その辺踏まえるとトータルでどうなのか,興味があります.
2011/07/14 04:53:34 UTCshiro
#
え、何でだろ>mark/sweep の手間は確実にboehm gcのほうがかかる
2011/07/14 04:55:56 UTCko1
#
conservative に mark する空間が大きいこと,mark bit をたてるのが若干面倒なことなどがあると思いましたが,微々たるものなのかな.
#
関係ないけど,ログ画面が見えないのは port が閉じてるからかしらん.
2011/07/14 04:57:52 UTCshiro
#
mark対象となる空間は広いですが、mark bitに関しては、ビットマップが固まっているのでむしろローカリティの面で(オブジェクトに直接マークするよりも)有利、って議論も見たことがあります。mark対象となるアドレスそのものには触る必要がないので。
#
ログ画面が見えないってChatonの画面のことかな? chaton_gaucheではport 9997を開けてもらわないと見えません。
#
mark対象空間が広いとfalse pointerが増える可能性は高いのか。
2011/07/14 05:07:47 UTCshiro
#
あとは、boehmはオブジェクトの大きさでページを分けているんで、ポインタ候補からページを出した後にビットマップインデックスを計算するところで整数除算が入る (除数が2^nとは限らない)。それは若干オーバヘッドだとは思うけど、cpu内で完結する話だからキャッシュミスに比べて問題にならなさそうにも思う。
2011/07/14 05:14:43 UTCshiro
#
sweepではreclaimされたオブジェクトをfreelistにつなぎ変えるので、オブジェクトそのものに触らないとならない。そこはローカリティが悪いな。一気に大量にアロケートして全部ごみになるってパターンだとsweepでたくさんのページに触りまくってきついかも。
2011/07/14 05:56:36 UTCshiro
#
でも固定長ヘッダ+malloc方式でもsweep時に大量のfreeが発生すれば同じことか。
2011/07/14 07:11:53 UTCko1
#
9997 は空いてないですね....
#
bitmap に関しては,Ruby もそれにするかって議論があります.
2011/07/14 07:16:51 UTCko1
#
自分の経験だと,markに比べてsweepの時間が短いので,実は sweep はあんまり気にしなくても良いかも,とかなんとか.sweep を並列化しても全然効かなかったという.
2011/07/14 07:20:04 UTCshiro
#
markはlive objectの量に比例して、sweepは総ヒープ量に比例するから、巨大な一時データ構造を作ってすぐ捨てるようなパターンでヒープが2Gとかなったらsweepもバカにならないんじゃないかなあ。そういうのは特殊なパターンだろうけど。
#
sweepを並列化してもメモリに触りに行くところがどうせボトルネックになる感じがする。
#
Rich HickeyがJVMはephemeral objectのGCが速いからがんがん使い捨ててもいいみたいなことを前に言ってたなあ。第0世代からtenureするとこだけでもcopying GCに出来たらバースト的にアロケートして捨てるパターンはカバーできるかも。
2011/07/14 08:22:21 UTCshiro
#
(第0世代から第1世代だけcopying、というのはGaucheではflonum限定でやってる。バースト的アロケーションがよく起きるオブジェクトだから。しかしconservative GCでcopyingするのはいろいろめんどい。)
2011/07/14 08:55:51 UTCzick
#
第0世代のflonumへのポインタはどうしてるんですか? remember setとかを使用?
#
いや、一段ポインタをかませて間接参照にした方が楽なのかな。
2011/07/14 08:58:48 UTCshiro
#
第0世代のflonumを指すポインタが存在できる場所を制限しています (VMのレジスタとスタックからのみ)。レジスタやスタックからヒープへポインタを移動するタイミングは全て把握できるので、その段階でnurseryを指してたらflonumの実体もヒープに移します。
2011/07/14 09:01:03 UTCzick
#
なるほど。そのタイミングでtenureさせるんですか。
2011/07/14 09:04:29 UTCshiro
#
なのでベクタやリストにflonumを入れちゃうと余分なコピーが発生するんですが、f64vectorとかそれにバックアップされたmatrixなんかをうまく使えば「flonumオブジェクト」としてヒープにアロケートする必要はかなり減ります。
2011/07/14 09:10:51 UTCzick
#
それじゃあflonumのcopying GCのコストはレジスタの数とスタックの深さに比例するんですかね。
2011/07/14 09:27:35 UTCshiro
#
うーん、作られるflonumのうちどのくらいの割合がephemeralかによりますね。例えば(sqrt (+ (* a a) (* b b))) でa,bがflonumの時、各*の結果と+の結果は即座に消費されて参照されなくなるので、コピーされることもありません。
2011/07/14 09:29:28 UTCzick
#
いえ、コピーのコストじゃなくて、copying GCのroot scanのコストです。
2011/07/14 09:31:41 UTCshiro
#
ああ、スキャンのコストはそうなります。実際にはレジスタ数ってごくわずかだし、スタックもアクティブエリアだけなのでたいした量になりませんが。
2011/07/14 09:33:01 UTCzick
#
スタックに比例するなら、スタックの浅いところでflonumの計算した場合と、スタックが深いところでflonumの計算した場合に差が出るんじゃないか、少し考えました。
2011/07/14 09:34:11 UTCshiro
#
あ、ちょいまち。ちょっと違う。
#
flonumがヒープに移されるのは(1)そのflonumへのポインタが特殊なroot setの外にコピーされる時と(2)第0世代スペースが溢れたとき、ですが、第0世代flonumへのポインタはたかだか一つに限るとしているので、(1)ではスキャンは発生しません。
#
(2)の場合は確かにスタックが深いところで溢れるとスキャンのコストが余分にかかりますね。
#
ただ、深いというのが、Gaucheの場合、クロージャ作成などのタイミングでスタックフレームチェインがヒープに移されることがよくあって、スタックポインタはかなり進んでいるんだけどアクティブなフレームは少ししかない、っていうケースもあります。
#
全てのスタックフレームをスタックに置いたままスタックぎりぎりのところまで使って、そこでflonumの計算を繰り返す、というのが最悪パターンですね。そこをチューンするにはランタイムに監視しといて適度にtenuringをトリガしてやるとかしないとだめかも。
2011/07/14 19:05:01 UTCshiro
#
ウランの遠心分離機を標的にしたワームStuxnetが如何にして解析されたか、という話。面白い。 http://www.wired.com/threatlevel/2011/07/how-digital-detectives-deciphered-stuxnet/all/1