久しぶりに竹内関数で JavaScript、Python、Ruby、Scheme と Smalltalk とを戦わせてみる

OOPL


AO bench で味を占めたので。

今回は上のリンク先の結果と対比できるように tarai（y を返す）ではなく tak（z を返す。 “ニセ”竹内関数）で tak(20, 10, 0) を手元の環境（Intel Core i7-4650U @1.7GHz/2.3GHz、Win8.1 64-bit）で計測してみました。インストールの手間もあって、必ずしも最新バージョンをそろえられなかったのはご容赦ください。


　言語　 　処理系　 　結果　
　Smalltalk　 　Squeak 4.5 CogVM　 　1.33 sec　
　　 　Squeak 4.5 SpurVM　 　1.19 sec　
　　 　Squeak 4.3 CogVM　 　0.741 sec　
　　 　VisualWorks 7.10.1nc　 　3.87 sec　
　　 　Dolphin Smalltalk X6 (6.0.3ce)　 　3.45 sec　
　　 　GNU Smalltalk 3.1　 　14.1 sec　
　Python　 　Python 3.2.5　 　11.4 sec　
　Ruby　 　Ruby 2.2.0dev　 　4.52 sec　
　Scheme　 　Gauche 0.9.5_pre1　 　3.27 sec　
　JavaScript　 　Node.js 0.10.31　 　0.486 sec　
　C　 　gcc 4.8.3　 　0.217 sec　


いつの間にか VisualWorks より爆速になった Squeak（CogVM）は安定の結果ですが、その中でも AO bench で威力を発揮した SpurVM が期待したほどではなかったのが残念だったのに対し、思わぬ伏兵として Squeak 4.3 の古い CogVM が意外な好成績をたたき出したのが興味深いところです。Dolphin Smalltalk も入れたのでついでに計ってみたのですが、古い処理系のわりに健闘しています。

他言語では、JavaScript の V8エンジンが相変わらずバカっぱやいですね。勝てる気がしません。


Smalltalk で使用したコード（共通）

| tak res |
tak := nil.
tak := [:x :y :z |
   x <= y ifTrue: [z] ifFalse: [
      tak
         value: (tak value: x-1 value: y value: z)
         value: (tak value: y-1 value: z value: x)
         value: (tak value: z-1 value: x value: y)
   ]
].

(Time millisecondsToRun: [res := tak value: 20 value: 10 value: 0]) -> res

その他の言語のコードと出力

$ python3 -V
Python 3.2.5

$ python3 tak.py
11.36166000366211 1

$ cat tak.py
from time import time

def tak(x, y, z):
    if x <= y: return z
    return tak( tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y) )

start = time()
res = tak(20, 10, 0)
print( time() - start, res )
$ ruby -v tak.rb
ruby 2.2.0dev (2014-08-26 trunk 47287) [x86_64-cygwin]
1
4.52072

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

start = Time.now
puts tak(20, 10, 0)
puts Time.now - start
$  gosh -V
Gauche scheme shell, version 0.9.5_pre1 [utf-8,pthreads], x86_64-unknown-cygwin

$ gosh tak.scm
;(time (display (tak 20 10 0)))
; real   3.274
; user   3.265
; sys    0.000
1

$ cat tak.scm
(define (tak x y z)
   (if (<= x y) z
     (tak (tak (- x 1) y z) (tak (- y 1) z x) (tak (- z 1) x y))))

(time (display (tak 20 10 0)))
$ node -v
v0.10.31

$ node tak.js
486 1

$ cat tak.js
function tak(x, y, z){
   if(x <= y){ return z; }
   return tak( tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y) );
}

var start = (new Date()).getTime();
var res = tak(20, 10, 0);
console.log((new Date()).getTime() - start, res)
$ gcc --version
gcc (GCC) 4.8.3
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


$ cat tak.c
#include <stdio.h>

int tak(int x, int y, int z){
   if (x <= y){
      return z;
   } else {
      return tak( tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y) );
   }
}

int main(void){
   printf("%d\n", tak(20, 10, 0));
   return 0;
}

$ gcc -O3 tak.c -o tak_O3

$ time ./tak_O3
1

real    0m0.217s
user    0m0.171s
sys     0m0.015s