https://sumim.hatenablog.com/entry/20140910/p1

AO bench で味を占めたので。

徒然日記 | tak(20, 10, 0)関数ベンチマーク

今回は上のリンク先の結果と対比できるように 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