アセンブリ言語でフィボナッチ数

前回は、C++で単純なVMを書いて、その上でのフィボナッチ数の計算時間を測定した。
そのVM部分をネイティブコードに置き換えたら、どの程度処理速度が改善するのかを測ってみたかったので、その前にまずネイティブコード(x86)の勉強も兼ねて、common lispアセンブラを書くことにした。
現状はまだまだ未完成で、以下のような制限があるが、一応フィボナッチ数が計算できるくらいまでには出来たので、その計算時間を参考までに残しておく。
制限:

  • 使用可能な命令は mov/ret/push/pop/add/sub/inc/dec/cmp/jmp/jcc/call のみ
  • 64bitのみ対応
  • エラーチェックとか不十分
  • SBCLのみで動作

github: cl-asm-0.0.1

コード

フィボナッチ数計算用のコード。

(use-package :sb-alien)

;; Fibonacci用のアセンブリコード
(defparameter *fib*
 '((:push %rbp) (:mov %rbp %rsp) (:push %rdi) (:push %rsi) (:push %rbx)  ; 関数呼び出し時の定形処理

   (:mov %eax %edi)  ; 引数取得
   (:call &fib-beg) 
   
   (:pop %rbx) (:pop %rsi) (:pop %rdi) (:pop %rbp)  ; 関数から返る時の定形処理
   :ret
  
  &fib-beg
  (:cmp %eax 2)      ; arg < 2
  (:jl &fib-end)
  
  (:push %rax)
  (:sub %eax 2)
  (:call &fib-beg)   ; x = (fib (- arg 2))
  (:pop %rbx)

  (:push %rax)
  (:mov %eax %ebx)
  (:dec %eax)
  (:call &fib-beg)   ; y = (fib (- arg 1))
  (:pop %rbx)
  
  (:add %eax %ebx)   ; (+ x y)
  &fib-end
  :ret))
--> *FIB*

;; 生成されるマシン語
(cl-asm:assemble *fib*)
--> (85 72 137 229 87 86 83 137 248 232 5 0 0 0 91 94 95 93 195 131 248 2 124 23 80
     131 232 2 232 242 255 255 255 91 80 137 216 255 200 232 231 255 255 255 91 1
     216 195)

;; 実行
(time
 (cl-asm:execute
   *fib*
  (function int int)  ; 関数の型
  35)                 ; 引数:  (fib 35)
Evaluation took:
  0.059 seconds of real time
  0.060003 seconds of total run time (0.060003 user, 0.000000 system)
  101.69% CPU
  117,246,804 processor cycles
  32,624 bytes consed
--> 9227465

比較

前回の他言語での測定結果に、上での計測結果を追加したもの。

言語 所要時間(最適化オプションなし) 所要時間(最適化オプションあり)
gcc-4.6.1 0.112s 0.056s
sbcl-1.0.54 0.320s 0.110s
pvm 3.600s
ruby1.9.1 2.816s
ruby1.8.7 14.497s
cl-asm 0.059s

やっぱりマシン語直出力は速い。最適化されたGCCよりは遅いけど。