はじめてのにき

_ 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)