Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 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 | 11 |

2010-06-30

引数の順番を覚えられないならELTを使えば良いじゃない!

| 23:40 | 引数の順番を覚えられないならELTを使えば良いじゃない! - わだばLisperになる を含むブックマーク はてなブックマーク - 引数の順番を覚えられないならELTを使えば良いじゃない! - わだばLisperになる

Common Lispには、シーケンスのN番目の要素を取り出すのに、リスト専用ならNTH、ベクタならSVREFとかAREF、文字列ならCHAR、そして汎用には、ELTがありますが、NTHだけ順番が違っていたりする所為で、「おや、どっちの引数がインデックスだったかな」などと記憶が朧げになることがあります。(引数の順番が色々違うのは恐らく歴史的経緯+互換性のため)

そこで、とりあえず、ELTで書いて処理系の最適化に期待してみるのはどうかなと思い試してみました。

試した処理系はSBCLです。

まず、最初に最適化してないELTを呼ぶ関数ELEMENT

(DEFUN ELEMENT (OBJ INDEX)
  (ELT OBJ INDEX))

; disassembly for ELEMENT
; 0E4BA8EB:       488BD6           MOV RDX, RSI               ; no-arg-parsing entry point
;      8EE:       498BF8           MOV RDI, R8
;      8F1:       488B0598FFFFFF   MOV RAX, [RIP-104]         ; #<FDEFINITION object for ELT>
;      8F8:       B910000000       MOV ECX, 16
;      8FD:       FF7508           PUSH QWORD PTR [RBP+8]
;      900:       FF6009           JMP QWORD PTR [RAX+9]
;      903:       CC0A             BREAK 10                   ; error trap
;      905:       02               BYTE #X02
;      906:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;      907:       54               BYTE #X54                  ; RCX

ディスアセンブルすると、ELTを呼んでいるだけのようです。

NTHを使うとどうか

(DEFUN ELEMENT/LIST (OBJ INDEX)
  (NTH INDEX OBJ))

; disassembly for ELEMENT/LIST
; 0E6188ED:       488D5C24F0       LEA RBX, [RSP-16]          ; no-arg-parsing entry point
;      8F2:       4883EC18         SUB RSP, 24
;      8F6:       488B55F0         MOV RDX, [RBP-16]
;      8FA:       488B7DF8         MOV RDI, [RBP-8]
;      8FE:       488B058BFFFFFF   MOV RAX, [RIP-117]         ; #<FDEFINITION object for NTHCDR>
;      905:       B910000000       MOV ECX, 16
;      90A:       48892B           MOV [RBX], RBP
;      90D:       488BEB           MOV RBP, RBX
;      910:       FF5009           CALL QWORD PTR [RAX+9]
;      913:       8BC2             MOV EAX, EDX
;      915:       240F             AND AL, 15
;      917:       3C07             CMP AL, 7
;      919:       750F             JNE L0
;      91B:       488B52F9         MOV RDX, [RDX-7]
;      91F:       488BE5           MOV RSP, RBP
;      922:       F8               CLC
;      923:       5D               POP RBP
;      924:       C3               RET
;      925:       CC0A             BREAK 10                   ; error trap
;      927:       02               BYTE #X02
;      928:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;      929:       54               BYTE #X54                  ; RCX
;      92A: L0:   CC0A             BREAK 10                   ; error trap
;      92C:       02               BYTE #X02
;      92D:       02               BYTE #X02                  ; OBJECT-NOT-LIST-ERROR
;      92E:       95               BYTE #X95                  ; RDX

NTHCDRを呼ぶようです。

ここで、ELTの定義にジャンプ(M-.)して定義を眺めてみると、リストの場合、

(deftransform elt ((s i) (list *) * :policy (< safety 3))
  '(nth i s))

という風に最適化のための変形が定義されていて、(OPTIMIZE (SAFETY N))のNを3より低く0〜2にすれば変形が発動するようです。

ということで、オブジェクトがリストであることを指定しつつ、SAFETYを0にしてみてディスアセンブル

(DEFUN ELEMENT/LIST-OPT (OBJ INDEX)
  (DECLARE (OPTIMIZE (SAFETY 0))
           (LIST OBJ))
  (ELT OBJ INDEX))

; disassembly for ELEMENT/LIST-OPT
; 0E5468E7:       488B55F0         MOV RDX, [RBP-16]          ; no-arg-parsing entry point
;      8EB:       488D5C24F0       LEA RBX, [RSP-16]
;      8F0:       4883EC18         SUB RSP, 24
;      8F4:       488B7DF8         MOV RDI, [RBP-8]
;      8F8:       488B0591FFFFFF   MOV RAX, [RIP-111]         ; #<FDEFINITION object for NTHCDR>
;      8FF:       B910000000       MOV ECX, 16
;      904:       48892B           MOV [RBX], RBP
;      907:       488BEB           MOV RBP, RBX
;      90A:       FF5009           CALL QWORD PTR [RAX+9]
;      90D:       488B52F9         MOV RDX, [RDX-7]
;      911:       488BE5           MOV RSP, RBP
;      914:       F8               CLC
;      915:       5D               POP RBP
;      916:       C3               RET

NTHと同じようにNTHCDRが呼ばれるようになったようです。

他に、SBCLのELTは、SIMPLE-ARRAYにもDEFTRANSFORMを用意しているようです。

ちなみに、LISPマシンのようなタグアーキテクチャマシンでは、データ型をタグでハードウェア的に判別できたため、汎用のELTも専用のNTHと同じようにオーバーヘッドなしで処理できたようでマニュアルにもそういう説明があります。lispマシンイイ(・ ∀・)