再帰関数(ハノイの塔)にinline宣言をつけたら・・・

Forthでハノイの塔 - sileの日記でハノイの塔を解くcommon lispプログラムを載せたら「inline宣言を付けるともっと早くなりますよ」というコメントを頂いたので試してみた。

inline宣言付与結果

再帰関数をinline展開する際の深さはsb-ext:*inline-expansion-limit*変数で制御できるらしい。
今回はデフォルトの設定値をそのまま利用した。

;; sbcl-1.0.49(linux/64bit)
> sb-ext:*inline-expansion-limit*
--> 200 

;; inline宣言
(declaim (inline hanoi-impl))

;; 前回定義したhanoi-impl関数とhanoi関数を再コンパイル 
;; (*inline-expansion-limit*を越えました、という長いメッセージが出力される)
;; ... 略 ...

;; 実行
> (time (hanoi 'a 'b 'c 25))
Evaluation took:
  0.271 seconds of real time   ; 約 2.7 秒
  0.270000 seconds of total run time (0.270000 user, 0.000000 system)
  99.63% CPU
  541,031,826 processor cycles
  0 bytes consed
  
--> (:COUNT 33554431)

確かに速くなっている。

ついでにhanoi関数にもinline宣言をつけてみた。

;; inline宣言
(declaim (inline hanoi))

;; hanoi関数を再コンパイル 
;; ... 略 ...

;; 実行
> (time (hanoi 'a 'b 'c 25))   ; 実行時にinline展開される
;; (*inline-expansion-limit*を越えました、という長いメッセージが出力される)
Evaluation took:
  0.169 seconds of real time  ; 約 0.17 秒
  0.170000 seconds of total run time (0.170000 user, 0.000000 system)
  100.59% CPU
  337,858,167 processor cycles
  0 bytes consed
  
--> (:COUNT 33554431)

hanoi関数を実行時に展開するようにしたら、C++と同じくらいに高速になった。

ただsbclのtime関数はinline関数の展開時間は所要時間に含めていないようで、少し不公平な感があるので、別の方法でも図ってみた。

;; 実行時のinline展開時間も含めて図ってみる
> (get-internal-real-time) (hanoi 'a 'b 'c 25) (get-internal-real-time) (- * ***)
--> 304455 ; 開始時間
--> (:COUNT 33554431)
--> 304730 ; 終了時間
--> 275    ; 終了 - 開始 = 0.275 秒

展開時間も含めると、特別速いということはなさそう。
それでもinline宣言を全く使用しない場合に比べるとだいぶ良い。

表

各言語でのハノイの塔の処理時間をまとめておく。

C++ gcc	Forth gforth	Forth VFX-Forth	common lisp sbcl(宣言無)	common lisp sbcl(hanoi-implをinline宣言)	common lisp sbcl(hanoiとhanoi-implをinline宣言)
0.168s	3.359s	0.190s	0.403s	0.271s	0.169s (0.275s*1 )

教訓

再帰関数でもinline展開すると速くなることがある。
覚えておこう。

*1:実行時のinline展開処理も含めて計測した場合の数値