アセンブリ言語でフィボナッチ数
前回は、C++で単純なVMを書いて、その上でのフィボナッチ数の計算時間を測定した。
そのVM部分をネイティブコードに置き換えたら、どの程度処理速度が改善するのかを測ってみたかったので、その前にまずネイティブコード(x86)の勉強も兼ねて、common lispでアセンブラを書くことにした。
現状はまだまだ未完成で、以下のような制限があるが、一応フィボナッチ数が計算できるくらいまでには出来たので、その計算時間を参考までに残しておく。
制限:
- 使用可能な命令は mov/ret/push/pop/add/sub/inc/dec/cmp/jmp/jcc/call のみ
- 64bitのみ対応
- エラーチェックとか不十分
- SBCLのみで動作
コード
フィボナッチ数計算用のコード。
(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
