第6回社内エンジニア勉強会 コードの最適化

区分
勉強会
報告者

こんにちは、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 エンジニア枯渇していのでしょうか・・・

トップページに戻る

技師部隊からの
お知らせ

【求人】エンジニア募集しています。

本頁の来客数
八十七万千百七十六名以上(計測停止中)

メンバー一覧

アクトインディ技師部隊員名簿

アクトインディ技師部元隊員

アクトインディへ

カテゴリー

アクトインディ

aaaa