こんにちは、tahara です。
たぶん第6回目となる社内エンジニア勉強会を開催しました。
持ちまわりで社内勉強会を開催しており、先日は私の担当でしたので、 このブログにも書いておこうと思います。
よくあるフィボナッチ数を求める fib 関数をネタにコードの最適化について話しました。
まず Ruby で
def fib(n) if n < 2 n else fib(n - 2) + fib(n - 1) end end require 'benchmark' Benchmark.realtime do fib(37) end # => 4.012619736
これを Common Lisp で書くと
(defun fib (n) (if (< n 2) n (+ (fib (- n 2)) (fib (1- n))))) (time (fib 37)) ;; 0.722 seconds of real time
ここから、最適化していきます。
普通に declare と the で最適化するとだいたい2倍になります。
(defun fib-optimize (n) (declare (optimize (speed 3) (safety 0)) (fixnum n)) (if (< n 2) n (the fixnum (+ (the fixnum (fib-optimize (- n 2))) (the fixnum (fib-optimize (1- n))))))) (time (fib-optimize 37)) ;; 0.277 seconds of real time
ディスアセンブルしてみるとよくわかります。
(disassemble 'fib) (disassemble 'fib-optimize)
次にコードウォークで最適化します。
#:g1: インライン展開手作り風味 からそのまま拝借させていただきました。
(defun-inline-self fib-inline 4 (n) (declare (optimize (speed 3) (safety 0)) (fixnum n)) (if (< n 2) n (the fixnum (+ (the fixnum (fib-inline (- n 2))) (the fixnum (fib-inline (1- n))))))) (time (fib-inline 37)) ;; 0.141 seconds of real time
こんな単純なコードでは関数呼び出しのコストは大きいですね。
ついでにコンパイラーマクロを使ってみます。
(defmacro はやくなるおまじない (f) `(define-compiler-macro ,f (&whole form &rest args) (if (every #'constantp args) (apply #',f args) form))) (はやくなるおまじない fib) (time (fib 37)) ;; 0.000 seconds of real time
もちろん実行前に次のコードに変換するのに、(fib 37) したのと同じ時間かかってます。
(time 24157817)
最後によいアルゴリズムで。
def fib_good(n, a=0, b=1) if n == 0 a else fib_good(n - 1, b, a + b) end end Benchmark.realtime do fib_good(1000) end # => 0.000527397
残念ながら Ruby から Common Lisp に乗り換える必要はなさそうです。 Common Lisp はいろいろ遊べておもしろいのに・・・
最後に、弊社ではデザイナ、エンジニアを募集しております。 まずはお話だけでも。よろしくお願いします！
Rails エンジニア枯渇していのでしょうか・・・
