fib の実行命令総数比較 - Scheme VM を書く

scheme

fib(26) における実行命令総数比較。

Gauche 自前
2811342 3435386


これはちょっと差がありすぎですね。

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

自前。

#(CLOSURE 38 1 #f 0
0    REFER_LOCAL0
1    PUSH
2    CONSTANT 2
4    BRANCH_NUMBER_LE 4
6      CONSTANT 1
8      LOCAL_JMP 24
10    FRAME 9
13      REFER_LOCAL0_PUSH
14      CONSTANT 1
16      NUMBER_SUB
17     PUSH
18     REFER_GLOBAL_TOP_LEVEL_APPLY fib 1
21   PUSH
22  FRAME 9
24    REFER_LOCAL0_PUSH
25    CONSTANT 2
27    NUMBER_SUB
28    PUSH
29    REFER_GLOBAL_TOP_LEVEL_APPLY fib 1
32    NUMBER_ADD
33    RETURN 1
  DEFINE_GLOBAL |top level | fib)

Gauche。

     0 LREF0-PUSH               ; n
     1 CONSTI(2) 
     2 BNLE 6                   ; (<= n 2)
     4 CONSTI(1) 
     5 RET 
     6 PRE-CALL(1) 12
     8 LREF0                    ; n
     9 NUMADDI(-1)              ; (- n 1)
    10 PUSH-GREF-CALL(1) #<identifier user#fib>; (fib (- n 1))
    12 PUSH-PRE-CALL(1) 18
    14 LREF0                    ; n
    15 NUMADDI(-2)              ; (- n 2)
    16 PUSH-GREF-CALL(1) #<identifier user#fib>; (fib (- n 2))
    18 NUMADD2                  ; (+ (fib (- n 1)) (fib (- n 2)))
    19 RET

考察

  • LREF0-PUSH 相等が存在するのに使われていない部分がある
  • CONSTI はインストラクションにオペランドが含まれていて一命令ですむ
  • BNLE のブランチ命令に比較対象の定数が含まれている
  • REFER_LOCAL0 + PUSH の合成命令が適用されていない部分がある
  • PUSH-GREF-CALL の合成命令がない
  • PUSH-PRE-CALL 相当の合成命令がない
  • NUM-ADDIはインストラクションにオペランドが含まれている
  • RETはインストラクションにオペランドが含まれている

つまりコードが短いって事ですね。
さてどうしようかな。