トップ «前の日記(2009-10-25) 最新 次の日記(2009-10-30)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|06|07|08|09|10|11|

ToDo:


2009-10-27

_ dame_rev

http://d.hatena.ne.jp/camlspotter/20091026/1256567062

http://twitter.com/shinh/status/5194338611

http://twitter.com/shinh/status/5194346481

さて読もう!

08049860 <camlDame_rev__dame_rev_58>:
 8049860:       83 ec 04                sub    $0x4,%esp
 8049863:       89 c1                   mov    %eax,%ecx    # なんか知らんが第一引数は eax なのかね…
 8049865:       83 f9 01                cmp    $0x1,%ecx    # なんか知らんが nil の内部表現は 1 なのかね…
 8049868:       74 46                   je     80498b0 <camlDame_rev__dame_rev_58+0x50>
 804986a:       a1 40 b5 05 08          mov    0x805b540,%eax    # 0805b540 B caml_young_ptr なんだこれは! とりあえず GC 関係ぽい。 young って世代別とかそいうやつかいな
 804986f:       83 e8 0c                sub    $0xc,%eax    # なんか知らんが値減らして保存しなおしてるみたいだ!
 8049872:       a3 40 b5 05 08          mov    %eax,0x805b540
 8049877:       3b 05 44 b5 05 08       cmp    0x805b544,%eax    # 0805b544 B caml_young_limit
 804987d:       72 3a                   jb     80498b9 <camlDame_rev__dame_rev_58+0x59>    # これの行き先が GC なので、まぁ GC 関係
 804987f:       8d 58 04                lea    0x4(%eax),%ebx    # ここから本番。なんかたぶんリストの確保が終わってて ebx に入るのですよ、たぶん
 8049882:       89 1c 24                mov    %ebx,(%esp)   # たぶんこれがいま ebx=[]
 8049885:       c7 43 fc 00 08 00 00    movl   $0x800,-0x4(%ebx)    # (%eax) じゃないのか悩むが謎の定数を元の eax のところに入れてて、うーんこれはなんだろう
 804988c:       8b 01                   mov    (%ecx),%eax    # x を eax に入れた
 804988e:       89 03                   mov    %eax,(%ebx)    # ebx=[] の car を [x] にした
 8049890:       c7 43 04 01 00 00 00    movl   $0x1,0x4(%ebx)    # ebx=[] の cdr に 1 (やっぱ nil やね) をつっこむ
 8049897:       8b 41 04                mov    0x4(%ecx),%eax    # xs を eax に入れて
 804989a:       e8 c1 ff ff ff          call   8049860 <camlDame_rev__dame_rev_58>    # 再帰呼び出し
 804989f:       8b 1c 24                mov    (%esp),%ebx    # スタックに置いておいた [x] を持ってきた
 80498a2:       83 c4 04                add    $0x4,%esp
 80498a5:       e9 16 08 00 00          jmp    804a0c0 <camlPervasives__$40_167>    # 0x40 は '@' なのでまぁそういうことだろう
 80498aa:       8d b6 00 00 00 00       lea    0x0(%esi),%esi    # 何これここ来ることあるんか!!! → とりあえず gdb で break しかけても止まらない。
 80498b0:       b8 01 00 00 00          mov    $0x1,%eax
 80498b5:       83 c4 04                add    $0x4,%esp
 80498b8:       c3                      ret    
 80498b9:       e8 3a d7 00 00          call   8056ff8 <caml_call_gc>
 80498be:       eb aa                   jmp    804986a <camlDame_rev__dame_rev_58+0xa>

わかったことは引数は eax, ebx と入れて渡す呼び出し規約だということだった。 あと GC まわりのコードはこれだけではよくわからん。 てか [x] のために allocate ぽいことしちゃうのはちょっといけてないなー

さて次は @ を読もう!

0804a0c0 <camlPervasives__$40_167>:
 804a0c0:       83 ec 04                sub    $0x4,%esp
 804a0c3:       83 f8 01                cmp    $0x1,%eax    # 第一引数がカラだったらさっさと終わろうね☆
 804a0c6:       74 48                   je     804a110 <camlPervasives__$40_167+0x50>
 804a0c8:       8b 50 04                mov    0x4(%eax),%edx    # 第一引数の cdr
 804a0cb:       8b 08                   mov    (%eax),%ecx    # 第一引数の car
 804a0cd:       89 0c 24                mov    %ecx,(%esp)   # car の方は保存しておいて
 804a0d0:       89 d0                   mov    %edx,%eax    # cdr の方を次の関数 call の第一引数にして
 804a0d2:       e8 e9 ff ff ff          call   804a0c0 <camlPervasives__$40_167>   # 再帰! (ebx=第二引数は触ってないのでそのまま)
 804a0d7:       89 c1                   mov    %eax,%ecx    # 帰ってきたリストを ecx に。この時点で第二引数はくっついてるはず
 804a0d9:       a1 40 b5 05 08          mov    0x805b540,%eax    # また GC ゾ〜ン
 804a0de:       83 e8 0c                sub    $0xc,%eax
 804a0e1:       a3 40 b5 05 08          mov    %eax,0x805b540
 804a0e6:       3b 05 44 b5 05 08       cmp    0x805b544,%eax
 804a0ec:       72 28                   jb     804a116 <camlPervasives__$40_167+0x56>
 804a0ee:       8d 40 04                lea    0x4(%eax),%eax    # まぁこれで eax にカラリストが入ったんだろう
 804a0f1:       c7 40 fc 00 08 00 00    movl   $0x800,-0x4(%eax)
 804a0f8:       8b 1c 24                mov    (%esp),%ebx    # 保存しておいた car の方を
 804a0fb:       89 18                   mov    %ebx,(%eax)    # 確保したカラリストの car に入れるよ
 804a0fd:       89 48 04                mov    %ecx,0x4(%eax)    # cdr は帰ってきた値ね
 804a100:       83 c4 04                add    $0x4,%esp
 804a103:       c3                      ret    
 804a104:       8d b6 00 00 00 00       lea    0x0(%esi),%esi   # また使われてなさそうなコードがあるね…
 804a10a:       8d bf 00 00 00 00       lea    0x0(%edi),%edi   # また使われてなさそうなコードがあるね…
 804a110:       89 d8                   mov    %ebx,%eax    # ここは第一引数がカラリストだった場合なので、単に第二引数をかえせば良い!
 804a112:       83 c4 04                add    $0x4,%esp
 804a115:       c3                      ret    
 804a116:       e8 dd ce 00 00          call   8056ff8 <caml_call_gc>
 804a11b:       eb bc                   jmp    804a0d9 <camlPervasives__$40_167+0x19>
 804a11d:       8d 76 00                lea    0x0(%esi),%esi

ええとこれは… 正直どうしてこうなった…と思ってしまうな… これが関数型かー

何が言いたいかというとなんで list を append するのに allocation が大量発生してるんだよ! っていう

でまぁどう見ても O(n^2) でしかないので、 まぁ GC でこんだけ遅くなるのかなぁ。

(15:31)

本日のツッコミ(全6件) [ツッコミを入れる]
_ sumii (2014-05-24 01:31)

OCamlはよく知りませんが
http://www.google.com/search?q=%22garbage+collection+can+be+faster+than+stack+allocation%22
という話もあるので、generational copying GCのyoung heap allocationのコストはわりと小さいということになっています。まあlinear typeなり何なり使ってallocationしないようにできればそれに越したことはないですが。

_ shinh (2014-05-24 01:31)

とりあえずこれかなーと読んでみました。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.8219&rep=rep1&type=pdf

とりあえず

- 1986年
- free について
-- explicit free のコストは free する量 G に比例する
-- 一方 copying GC だとコストは実際に使ってるメモリの量に比例する
-- だから GC するまでの周期をすごく長くしてやる (==確保しておくメモリを大きくする) ことによって GC のコストは無視できる
-- GC が発動するまでに溜め込まないといけないメモリの量はこの人の見積りでは実際使っている量の7倍
-- Copying なのでさらに2倍して14倍と思いきやうまいことオーバーラップさせると8倍ですむよ
- malloc について
-- 限界が来たかの check は SEGV にやらせよう
-- メモリポインタの移動は VAX だとデクリメントしつつ代入できるアドレッシングモードがあるよん
-- よって stack と変わらん

思ったことは、

- 当時は知らないけどメモリが一番高い部品の一つになっちゃったし8倍は現実的でないなぁ
- そもそも8倍の見積りも現実的じゃなくて、やたら広い空間使うことによるキャッシュミスの影響は(当時はなかったかでかくなかったんだと思うけど)考えられてないしなぁ
- スタックの開放をまとめてやれるかもしれないが現実には困難って筆者は書いてるけど、一つの関数で何度か allocation したら自明にスタックの開放はまとめてやれるような
- Copying GC でメモリ領域オーバーラップさせるのって簡単なんですかね
- 一方現代は世代別なんちゃらとかもあるから論拠が強くなる面もあるのかなぁ
- allocation時にメモリ領域全部触ることが前提になってるから、デカいメモリ領域確保ーとかはきついのかなぁ

というようなことを思いました。ちょっと時代的に変わったかなぁと思える点も多かったんですが、たくさんメモリあれば GC は安いよーってのは面白い話でした。ありがとうございます。

_ shinh (2014-05-24 01:31)

ところで OCaml くわしくないはつっこんだ方が良かったでしょうか :-))))

_ kik (2014-05-24 01:31)

x86はよく知りませんがleaは6バイトnopのインテル推奨の書き方らしいですよ。

_ shinh (2014-05-24 01:31)

ああ使ってるレジスタ違うから気付いてなかったんですがこれ nop なんですね。やまぁ padding なんだろうなぁとは思ってたんですが、どいう事情でしょうかね。

_ shinh (2014-05-24 01:31)

ところで x86 くわし略 :-))))))))))))))))))

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2009年
10月
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
1.shinh(2014-05-24 01:31) 2.ょゎ(2014-05-24 01:31) 3.shinh(2014-05-24 01:31)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h