Yet Another Ruby VM (YARV) での ack や tarai との速度比較

Squeak Smalltalk OOPL


http://www.namikilab.tuat.ac.jp/~sasada/diary/200602.html#d17
http://eigenclass.org/hiki.rb?yarv+ueber+algorithmical+optimization

なにやら YARV で Ruby が（限定的にせよ）最適化が効いてむっちゃ速くなる！というお話。（追記：以降、ネタにマジレスもーど… orz ）ベンチマーク好きとしては見過ごせない情報です。実際どの程度のものなのか、Squeak や VisualWorks との比較をかねて、手元の環境（PowerBook G4 Ti DVI/1GHz/OS X 10.4.5）で make して試してみました。


ack と tarai については、青木さんの日記に Haskell と Ruby のスクリプトと簡単な説明が。端的にはちょっとしたことで処理が膨大になる関数だということのようです。

http://i.loveruby.net/d/20030315.html#p03


ところで、冒頭の引用もとで本来の答えとは異なる 42 を無理矢理出力させているのは、おそらく、ＳＦ小説「銀河ヒッチハイク・ガイド」に絡めたこの種のお遊びからでしょう。この部分は、今回は省きました。（追記：ちょｗｗｗおまｗｗｗ。省くな、バカ…）



tarai 関数と tak 関数については「ぬえ,鵺,NUE（New Unified Environment Research Project）」に LISP のコードを見つけることができます。

http://www.nue.org/nue/index.html#tak-function


余談ですが、tarai（tak）関数のエピソード（正しい使い方？ｗ）についてはこちらに。

http://www5a.biglobe.ne.jp/~sasagawa/MLEdit/Scheme/math6.html


Smalltalk 版は、SqueakPlugin-dev（Squeakland 3.8-05。Squeak 3.8 ベース）、VisualWorks 7.4nc の双方で共通で使えるコードで書いてあります。ブロックを用いたものに関しては、Squeak では ClosureCompiler が必要です。ClosureCompiler のインストール方法については、id:sumim:20060210:p1 などを参考にしてください。

メソッドを用いた Smalltalk 版 ack

Ack class >> m: mm n: nn
   mm = 0 ifTrue: [^ nn+1].
   nn = 0 ifTrue: [^ Ack m: mm-1 n: 1].
   ^ Ack m: mm-1 n: (Ack m: mm n: nn-1)
| result |
Array
   with: #millisecs -> (Time millisecondsToRun: [result := Ack m: 3 n: 7])
   with: #result -> result
Squeak
=> #(#millisecs->298 #result->1021)
VisualWorks 7.4nc
=> #(#millisecs->136 #result->1021)

ブロックを使った Smalltalk 版 ack

| ack result |
ack := nil.
ack := [:mm :nn |
   mm = 0 ifTrue: [nn+1] ifFalse: [
      nn = 0 ifTrue: [ack value: mm-1 value: 1] ifFalse: [
         ack value: mm-1 value: (ack value: mm value: nn-1)]]].

^ Array
   with: #millisecs -> (Time millisecondsToRun: [result := ack value: 3 value: 7])
   with: #result -> result
Squeak
=> #(#millisecs->2852 #result->1021)
VisualWorks
=> #(#millisecs->164 #result->1021)

Ruby 版 ack

def ack(m, n)
  if m == 0 then
    n+1
  elsif n == 0 then
    ack(m-1, 1)
  else
    ack(m-1, ack(m, n-1))
  end
end

puts ack(3, 7)
Ruby
# ruby -v
ruby 1.8.2 (2004-12-25) [powerpc-darwin8.0]

# time ruby ack.rb
1021

real    0m7.523s
user    0m6.765s
sys     0m0.176s
# ./ruby-1.9.0/ruby -v
ruby 1.9.0 (2006-02-15) [powerpc-darwin8.5.0]

# time ./ruby-1.9.0/ruby ack.rb
1021

real    0m3.640s
user    0m3.080s
sys     0m0.075s
# ./yarv/miniruby -v
ruby 1.9.0 (2005-11-18) [powerpc-darwin8.5.0]
YARVCore 0.3.3 (rev: 319) [opts: ]

# time ./yarv/miniruby ack.rb
1021

real    0m0.727s
user    0m0.669s
sys     0m0.012s

メソッドを用いた Smalltalk 版 tarai

Tarai class >> x: xx y: yy z: zz
   xx <= yy ifTrue: [^ yy].
   ^ Tarai
      x: (Tarai x: xx-1 y: yy z: zz)
      y: (Tarai x: yy-1 y: zz z: xx)
      z: (Tarai x: zz-1 y: xx z: yy)
| result |
Array
   with: #millisecs -> (Time millisecondsToRun: [result := Tarai x: 12 y: 6 z: 0])
   with: #result -> result
Squeak
=> #(#millisecs->3675 #result->12)
VisualWorks
=> #(#millisecs->635 #result->12)

ブロックを用いた Smalltalk 版 tarai

| tarai result |
tarai := nil.
tarai := [:xx :yy :zz |
   xx <= yy ifTrue: [yy] ifFalse: [
      tarai
         value: (tarai value: xx-1 value: yy value: zz)
         value: (tarai value: yy-1 value: zz value: xx)
         value: (tarai value: zz-1 value: xx value: yy)]].

^ Array
   with: #millisecs -> (Time millisecondsToRun: [result := tarai value: 12 value: 6 value: 0])
   with: #result -> result
Squeak
=> #(#millisecs->25402 #result->12)
VisualWorks
=> #(#millisecs->3575 #result->12)

Ruby 版 tarai

# cat tarai.rb
def tarai(x, y, z)
  if x <= y then
    y
  else
    tarai(tarai(x-1, y, z),
          tarai(y-1, z, x),
          tarai(z-1, x, y))
  end
end

puts tarai(12, 6, 0)
# time ruby tarai.rb
12

real    0m46.012s
user    0m43.538s
sys     0m0.221s
# time ./ruby-1.9.0/ruby tarai.rb
12

real    0m29.366s
user    0m27.364s
sys     0m0.138s
# time ./yarv/miniruby tarai.rb
12

real    0m9.984s
user    0m9.072s
sys     0m0.045s


遅いとあなどっていた Ruby でしたが、YARV が標準になると、Squeak は単純なベンチマークではかなわなくなりそうです。そうなったあかつきには対決は（Smalltalk vs Ruby …ということにして）、爆速の VisualWorks に登場してもらうことにしましょう…(^_^;)。