#:g1: Common LispでCより速いfib

Posted 2015-07-07 07:41:35 GMT

マイクロベンチでは良く見掛けるfibですが、fibはベンチとしては厄介なところがあると思います。
恐らく、元来、愚直な実装だと関数呼び出しが非常に多いことから、関数呼び出しの速度のベンチとなっているのだと思いますが、gccなどでは最適化をするとインライン展開をしてきます。
インライン展開がされると、関数呼び出しが減るのでfibには結構効いてきてしまうのですが、関数呼び出しの速度を見るのに、関数呼び出ししないから速いというようなことになってしまいます。

とはいえ、こういう類のマイクロベンチは速い方が勝ちというイメージなので、色々あるにせよ、インライン展開をしてくるgcc等に合せることになります。

インライン展開でfibを速くする

ということで、gccのようにインライン展開してみようという記事を過去に書いてみたのですが、

しばらくしてから、こんなことをしなくてもSBCLなら、labelsでインライン展開が効くことが分かりました。

labels+インライン展開は、どんな具合かというとgcc -O2よりちょっと速い位なので、この時点でCより速いです。

最適な展開回数を探す

これで終了という感じではあるのですが、gccの場合、欲張って-O3を付けると逆に遅くなったりします。
インライン展開もやりすぎは逆効果で、適度な規模に展開する必要があるようですが、SBCLでもsb-ext:*inline-expansion-limit*の設定値を越えたという警告が出てきたりしています。

今回は、この sb-ext:*inline-expansion-limit* の値で速度が変わったりするのかどうか探ってみようということで、こんな感じのfib.lispを用意して、

(defun fib (n)
  (declare (optimize (speed 3) (space 0) (compilation-speed 0) (safety 0)))
  (declare (fixnum n))
  (labels ((fib (n)
             (declare (fixnum n))
             (the fixnum
                  (if (< n 2)
                      n
                      (+ (fib (1- n))
                         (fib (- n 2)))))))
    (declare (inline fib))
    (fib n)))

sb-ext:*inline-expansion-limit* に、0から1000の値を設定して最適ポイントがあったりするのかどうかを力任せに調べます。

(let ((*error-output* (make-broadcast-stream)))
  (sb-int:collect ((ans '() ))
    (dotimes (i 1000)
      (let* ((limit i)
             (*inline-expansion-limit* limit))
        (load (compile-file "fib.lisp" 
                            :verbose nil
                            :print nil))
        (format t "~&========= limit:~D =================~%" limit)
        (call-with-timing (lambda (&key real-time-ms &allow-other-keys)
                            (ans (print (cons limit real-time-ms))))
                          (lambda ()
                            (fib 41)))))
    (print (subseq (sort (ans) #'< :key #'cdr) 0 10))))

調べてみた結果

fib 37から41位の所で調べてみた結果は下記の通りになりました(carが展開回数で、cdrがミリ秒)。

;;; (fib 37)
((89 . 66) (85 . 67) (91 . 67) (93 . 67) (82 . 68) (86 . 68) (88 . 68)
 (90 . 68) (92 . 68) (94 . 68))

;;; (fib 38) ((93 . 109) (85 . 110) (89 . 110) (95 . 111) (91 . 112) (96 . 112) (98 . 112) (102 . 112) (105 . 112) (46 . 113))

;;; (fib 39) ((56 . 179) (52 . 181) (89 . 182) (103 . 182) (110 . 182) (43 . 183) (49 . 183) (51 . 183) (62 . 183) (65 . 183))

;;; (fib 40) ((62 . 295) (64 . 295) (43 . 296) (121 . 296) (130 . 296) (51 . 297) (65 . 297) (69 . 297) (118 . 297) (119 . 297))

;;; (fib 41) ((68 . 471) (69 . 471) (70 . 475) (65 . 476) (56 . 477) (74 . 477) (136 . 477) (64 . 479) (130 . 479) (145 . 479))

調べてみると、どうもfibの場合は、デフォルト値の200より小さい値の方が良いらしいことが分かります。
また、fibの引数に与える数によっても変わってくるようです。

関数のサイズは、デフォルトだと、15800バイト、62展開制限の場合は、4884バイトです。

なお1000以上の展開についてですが、バイナリのサイズがどんどん大きくはなりますが、遅くなる傾向が見られます。
これは飽く迄、fibでの話なので、他の場合にはまた違った結果になると思われます。

計測結果: gccより15%位速くできる

最適ポイントが大体分かったので、デフォルトの設定、最適展開回数、gcc -O2とで比べてみます。

デフォルト 200展開

(time (dotimes (i 100) (fib 40)))

Evaluation took: 32.598 seconds of real time 32.608000 seconds of total run time (32.608000 user, 0.000000 system) 100.03% CPU 107,322,869,655 processor cycles 186,256 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz

62展開

(time (dotimes (i 100) (fib 40)))

Evaluation took: 29.277 seconds of real time 29.284000 seconds of total run time (29.284000 user, 0.000000 system) 100.02% CPU 96,391,129,167 processor cycles 226,496 bytes consed

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz

gcc -O2

time ./fib-O2          
./fib-O2  34.20s user 0.00s system 99% cpu 34.211 total

Intel(R) Xeon(R) CPU E3-1230 v3 @ 3.30GHz

(参考) stalin -O2

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

(fib 40)

$ chicken-stalin -copt -O2 -On fib.scm
t% time ./fib
./fib  0.34s user 0.00s system 98% cpu 0.344 total

ということで、最適な展開回数だと、Cより15%位速くなりました。

なお、Cはこんな感じに書いて、gcc -O2でコンパイルしています。

int fib(int n)
{
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

int main(int argc, char **argv) { int i; for (i=0;i<100;++i) { fib(40); } return 0; }

ちなみに、stalinだとこの程度の単純な問題だと最適化の余地がないようでgccまかせという感じです。

まとめ

fibだけ速くてもしょうがないのですが、こういうこともあるんだなーというところでした。

ディスアセンブルしてみると分かりますが、fibは単純なので、Common LispもCもこれ以上最適化のしようがないようで、大体似た感じになっています。

ちなみに、インライン展開されたバイナリのサイズが何にどう効いてきているのかは、全く理解できていません。
キャッシュに乗る乗らない等、色々考えられるかと思いますが、何かあれば是非とも教えてください。


HTML generated by 3bmd in SBCL 1.2.13

comments powered by Disqus