読者です 読者をやめる 読者になる 読者になる

Forthでハノイの塔

forth common lisp speed

Forthを触ってみたくなったので、試しにハノイの塔を実装してみた。
ついでにcommon lispC++でも実装し、Forthとの処理速度を比較してみた。
common lispの処理系にはSBCLを、Forthの処理系にはgforth及びVFX-Forthを使用した

Forthでの実装(gforth)

gforthはバイトコードタイプのForth実装。

\ gforth-0.7.0 (linux/64bit)
\ Forth版のハノイの塔

variable cnt             \ 再帰呼び出しの数をカウント用の変数

: hanoi-print ( to from -- to from )
    cr 2dup . ." -> " . ;

: hanoi-impl ( to tmp from level -- to tmp from )
    dup >r 0> if
        rot swap r@ 1- recurse                   ( tmp to from )
        cnt @ 1+ cnt ! 
        ( hanoi-print 計時用にコメントアウト )   ( tmp to from )
        rot r@ 1- recurse                        ( to from tmp )
        swap                                     ( to tmp from )
    then
    r> drop ;

: hanoi ( to tmp from level -- )
    0 cnt !                      \ カウント初期化
    hanoi-impl drop drop drop
    cr ." count: " cnt @ . cr ;  \ 再帰数表示

hanoi-printワードをコメントアウトしなかった場合の実行結果。

$ gforth      # shellからgforthコマンドを起動
1 2 3 3 hanoi 
3 -> 1 
3 -> 2 
1 -> 2 
3 -> 1 
2 -> 3 
2 -> 1 
3 -> 1 
count: 7 
 ok

gforthでの計時。

$ gforth-fast   # 高速版のコマンドを使用する

\ 計時用のワードを定義
: time ( word_pointer -- )
    utime drop >r
    execute
    utime drop r> - 1000 / ." elapsed " . ." ms " cr ;

\ 計時
1 2 3 25 ' hanoi time
count: 33554431 
elapsed 3359 ms  \ 結果: 3.34秒
 ok

Forthでの実装(VFX-Forth)

VFX-ForthはネイティブコードタイプのForth実装(? 不確か)。
ワードの定義はgforthのそれと同様なので計時部分だけ掲載。

# VFX-Forth-4.43 (linux/32bit ?)
$ vfxlin

\ 計時用のワードを定義
: time ( word_pointer -- )
    ticks >r
    execute
    ticks r> - ." elapsed " . ." ms " cr ;

\ 計時
1 2 3 25 ' hanoi time
count: 33554431 
elapsed 190 ms   \ 結果: 0.19秒
 ok

common lispでの実装(SBCL)

実装及び計時結果。

;;;; sbcl-1.0.49 (linux/64bit)

;; 関数定義
(defvar *count*)

(defun hanoi-impl (from tmp to level)
  (declare (fixnum level)
           (optimize (speed 3) (safety 0) (debug 0))
           (sb-ext:unmuffle-conditions sb-ext:compiler-note))
  (when (plusp level)
    (hanoi-impl from to tmp (1- level))
    (incf (the fixnum *count*))     ; (format t "~&~a => ~a~%" from to)
    (hanoi-impl tmp from to (1- level))))

(defun hanoi (from tmp to level)
  (let ((*count* 0))
    (hanoi-impl from tmp to level)
    `(:count ,*count*)))

;; 計時
(time (hanoi 'a 'b 'c 25))

Evaluation took:
  0.403 seconds of real time   ; 結果: 0.40秒
  0.390000 seconds of total run time (0.390000 user, 0.000000 system)
  96.77% CPU
  804,338,623 processor cycles
  0 bytes consed
  
(:COUNT 33554431)

C++での実装(GCC)

ソースコード

/*  ファイル名: hanoi.cc
 *  コンパイル: g++ -O3 -o hanoi hanoi.cc
 *  バージョン: gcc-4.4.3 (linux/64bit)
 */
#include <iostream>

int count;

void hanoi(int from, int tmp, int to, int level) {
  if(level > 0) {
    hanoi(from, to, tmp, level-1);
    count++;
    hanoi(tmp, from, to, level-1);
  }
}

int main() {
  count=0;
  hanoi(1, 2, 3, 25);
  std::cout << "count: " << count << std::endl;
  return 0;
}

コンパイル & 実行。

$ g++ -O3 -o hanoi hanoi.cc
$ time ./hanoi 
count: 33554431

real	0m0.168s  # 結果: 0.17秒
user	0m0.170s
sys	0m0.000s

ハノイの塔での処理速度比較した結果は、C++(0.17秒)、Forth-VFX(0.20秒)、lisp(0.40秒)、Forth-gforth(3.34秒)、の順となった。
Forthも処理系によっては、C++と同程度の速度がでるみたい。※ 雑な比較なので正確なところは分からないけど・・・

おまけ: 末尾再帰 => ループ変換 版

末尾再帰部分を手動でループに変換したソースコードも書いてみたので、載せておく。

variable cnt 

: 3dup ( a b c -- a b c a b c )
    dup 2over rot ;

: hanoi-impl ( to tmp from level -- )
    begin dup >r 0> while
            rot swap 3dup r@ 1- recurse ( tmp to from )
            cnt @ 1+ cnt !
            rot r> 1-                   ( to from tmp )
    repeat
    r> drop drop drop drop ;

: hanoi ( to tmp from level -- )
    0 cnt !                      
    hanoi-impl
    cr ." count: " cnt @ . cr ; 

この変換によって、gforthの場合は処理時間が短く(2.32秒)なったけど、VFX-Forthでは逆に長く(0.35秒)なってしまった。