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 |

2011-05-14

(どうでも良い)SBCLクイズ: 空ループの最適化 回答

| 20:27 | (どうでも良い)SBCLクイズ: 空ループの最適化 回答 - わだばLisperになる を含むブックマーク はてなブックマーク - (どうでも良い)SBCLクイズ: 空ループの最適化 回答 - わだばLisperになる

先日の(どうでも良い)SBCLクイズ: 空ループの最適化でしたが、最適化だけに最適化のレベルによって変ってくるようで環境によってはfoo-slowもfoo-fastも同じ、ということになるようです。

なるほど、すっかり設定に依存するということが頭から抜けていました…。

ということで、とりあえずここでは、(proclaim '(optimize (compilation-speed 0) (debug 3) (safety 0) (space 3) (speed 3)))のようなアグレッシブな設定で行く、ということにします。

それで回答ですが、自分は色々調べたり試してみたりして、最初に下のようなものを書きました

(defun foo-fast ()
  (let* ((numbers (coerce (- 0 1) 'number))
         (numbers (+ numbers (coerce 1 'number))))
    (declare (type number numbers))
    (tagbody
      LL
      (if (> numbers (* 10000 10000))
          (go END))
      (setq numbers (+ numbers (coerce 1 'number)))
      (go LL)
      END)
    nil))
(foo-fast)
;⇒ NIL
----------
Evaluation took:
  0.051 seconds of real time
  0.050000 seconds of total run time (0.050000 user, 0.000000 system)
  98.04% CPU
  120,854,475 processor cycles
  0 bytes consed

Intel(R) Core(TM)2 Duo CPU     P8600  @ 2.40GHz
; disassembly for FOO-FAST
; 19C6CAF4:       31C9             XOR ECX, ECX               ; no-arg-parsing entry point
;      AF6:       EB0C             JMP L1
;      AF8:       90               NOP
;      AF9:       90               NOP
;      AFA:       90               NOP
;      AFB:       90               NOP
;      AFC:       90               NOP
;      AFD:       90               NOP
;      AFE:       90               NOP
;      AFF:       90               NOP
;      B00: L0:   4883C108         ADD RCX, 8
;      B04: L1:   4881F90008AF2F   CMP RCX, 800000000
;      B0B:       7EF3             JLE L0
;      B0D:       BA17001020       MOV EDX, 537919511
;      B12:       488BE5           MOV RSP, RBP
;      B15:       F8               CLC
;      B16:       5D               POP RBP
;      B17:       C3               RET
;      B18:       CC0A             BREAK 10                   ; error trap
;      B1A:       02               BYTE #X02
;      B1B:       18               BYTE #X18                  ; INVALID-ARG-COUNT-ERROR
;      B1C:       54               BYTE #X54                  ; RCX

これをDISASSEMBLEしてもカウンターの部分でCLの関数の+は使われず、

L0:   ADD RCX, 8
L1:   CMP RCX, 800000000
      JLE L0

のようにひたすらカウントアップしているのが分かります。

それで結局何が違うのかというと、SETQの位置が違うだけでFOO-SLOWは、

(defun foo-slow ()
  (let* ((numbers (coerce (- 0 1) 'number)))
    (declare (type number numbers))
    (tagbody
      LL
      (setq numbers (+ numbers (coerce 1 'number)))
      (if (> numbers (* 10000 10000))
          (go END))
      (go LL)
      END)
    nil))

IFの前にSETQがあるだけ、ということになります。

何が違ってくるのかは、結局のところ全然自分も追い切れていないのですが、どうもSB-C::MAYBE-INFER-ITERATION-VAR-TYPEという関数があって、コンパイル時に中身を走査して繰り返し用の変数をみつけたら最適化する、ということをやっているようです。

(例えば、(setq foo (+ foo x))のような形の場合fooは繰り返しのカウンターの可能性が高い、等々)

また、最初の回答以外にも繰り返し用の変数をFIXNUMにすることでも大体同じ結果になるようです。

(defun foo-fast ()
  (let* ((numbers (coerce (- 0 1) 'fixnum)))
    (declare (type fixnum numbers))
    (tagbody
      LL
      (setq numbers (+ numbers 1))
      (if (> numbers (* 10000 10000))
          (go END))
      (go LL)
      END)
    nil))

この場合は、どうやら上の最適化に加え、繰り返しの演算がFIXNUMになることによって高速化される、という微妙に別のルートの最適化のようです。

  • SETQを最適化しやすい位置に置く
L0:   ADD RCX, 8
L1    CMP RCX, 800000000
      JLE L0
  • 繰り返し変数をFIXNUMにする
L0:    ADD RCX, 8
       MOV RDX, RCX
       CMP RDX, 800000000
       JLE L0

以上、とりとめなく書き散らかしてしまいましたが、どうしてこの最適化をみつけたかというと、SBCLのLOOPの展開形と比較した際にSETQの位置しか違わなかった、というのがきっかけでした。

これ以外にも、知らないところで知らない機能が発動して最適化していることって結構あるんでしょうねー。