_ 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)
_ naruse [そーいえば、もう伝わってるかも知れませんが ゴルフ 12B http://d.hatena.ne.jp/nurse/..]
_ shinh [あーはい。ファイルだろうなぁとは思ってたのですが、まぁこのへんはなんとかします…]