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

レガシーコード生産ガイド

私に教えられることなら

NASM / Linux x86-64でForth開発日誌3 ベンチマーク

Cog VM リリース記念: Squeak、Ruby、Python を恒例のフィボナッチベンチで戦わせてみる - Smalltalkのtは小文字ですを見てて、どれぐらいの速度が出るのか気になったので計ってみた。

(2016-03-05追記) なおこの記事でのForthは自作の処理系(最適化一切ナシ)なので遅いです。かなり高速な商用処理系での結果も含めた記事もあります

コードはbuiltin.fsに入れてる、こういうコード。

private/
  ( naive )
  : fib ( n -- x )
    dup 2 < if return then
    1- dup ( n n -- )
    recur swap ( n-1 n -- )
    1- recur + ;
  
  ( tail-recur )
  : fib-tail { n fn-2 fn-1 -- x }
    2 n > if fn-1 fn-2 + return then
    n 1-  fn-1  fn-2 fn-1 +  tail-recur ;
  
  reveal>>

  : fib ( n -- ) fib n. cr ;
  : fib-tail ( n -- x ) 2 - 1 1 fib-tail n. cr ;
/private

39 fibの方は、平均で1.66秒だった。参考記事のC、Squeak4.5、Gaucheの実行結果と比較すると

C (-O2) 0.22
C 0.45
Squeak(method) 0.99
forth 1.66
Squeak(block) 2.27
Gauche 6.52

厳密ではないけど、こんな結果になった。

正直に言うと、そこまで速くないと思う。拙い知識ながらも理由を想像すると、

  1. スタック操作はレジスタを直に使うコードに比べて命令数が多い。メモリアクセスの遅さも加わる。
  2. call/retではなくNEXTルーチンで動かすことで命令数が増える。(レジスタの退避も考えたらそこまで変わらないかも)
  3. 常に64bit幅で計算しているのでその分命令数が増える

あたりかな、と思う。3はともかく1と2は設計的にどうしようもないのかもしれない。Forthでも最適化はできるって情報見た記憶あるけど、基本的に難しかったはず。

ただ、

  • アセンブラで簡単に書け、自己拡張で高いレベルまで抽象化できることを考えると速い方
  • Forthには、伝統的なコンパイルされたコードをいじる自己拡張と、Factorみたいにコードをリストとして扱うマクロでの自己拡張があって、後者を前提とした設計にすれば、他の言語と同じように最適化できる

と考えてるので、そこまで残念な状況でもないかな、という感想。

ちなみに、fib-tailの方だと、書き方は末尾再帰だけどコンパイルされるコードは単なるジャンプなので、当たり前だけどめちゃくちゃ速くなる。92 fibも一瞬で求まる。(93以上も一瞬だけど、64bitから溢れる)。本当に当たり前なんだけど、速度が必要な部分だけ最適化すれば十分使えるでしょう。

広告を非表示にする