2022-09-09改訂: gcc バージョンが古すぎたのと、C が内部計測でなかった点を改め計測しなおしました。結果、Rust は C より速くはなくなりました。紛らわしいことで、ごめんなさい。また、gcc のバージョンアップに伴い、Python および Ruby についてはビルドと計測をしなおしたので、これらも少し速い値に変わっています。この点もどうぞあしからず。
2022-09-10追記:ご要望のあった Python numba.njit 使用時と Go の結果を追加しました。PHP は JIT 有効化が面倒だったので断念しました^^;
2022-09-10追記2:C の計測で clock() を使うのはフェアではないという指摘がありましたので、念のため clock_gettime() を使用したコードに差し替えました。結果に大きな差はありません。
2022-09-10追記3:PHP の JIT が 有効化されない理由と回避方法 が分かったので、計測して追加しました。
2022-09-11追記:PyPy の結果を追加しました。
2022-09-12追記:Common Lisp の結果を追加しました。
2022-09-13追記:Java(HotSpot、GraalVM)と C# 、GraalVM をインストールしたついでに TruffleSqueak、GraalPython、TruffleRuby の結果を追加しました。Java HotSpotVM が C より速くなってしまったのがナゾです。^^; ※その後、使用できるコア数を1に限ったり、引数をコマンドラインから与える、n=8 でも比較する等の検証をしましたが再現し、フェアさに欠ける点は特に見つけられませんでした。
2022-09-13追記2:PHP.ini の設定をしくじっていた(opcache.jit_buffer_size=128MBと最後に余計な"B"を付けてしまっていた^^;)ようで JIT が効いていませんでした。ごめんなさい。ご指摘いたみいります。ということで、PHP は「JITあり」の結果を改めて追加しました。
2022-09-13追記3:Ruby MJIT の結果を追加しました。
2022-09-16追記:お詳しい方からご指摘をいただき Common Lisp の最適化時の結果を更新しました。手元の環境では C より速く、Java を軽く制して今のところ最速です。Lisp 怖い (いろんな意味で^^;)。
2022-09-17追記:C# 最適化後と Swift の結果を追加しました。
2022-12-29追記:F# の結果を追加しました。
竹内関数 (今回はyを返す正式版) tarai(14, 7, 0) にかかる時間を、手元の環境(Intel Core i9-9880H @ 2.30GHz、Win10 64-bit WSL環境)で計測してみました。
- またまた久しぶりに竹内関数で JavaScript、Python、Ruby、Scheme と Smalltalk とを戦わせてみる
- 久しぶりに竹内関数で JavaScript、Python、Ruby、Scheme と Smalltalk とを戦わせてみる
Smalltalk は Squeak と Pharo の Win版を使いました。今回もいったんは従来通りブロック(無名関数)版の実装で計測したのですが、タイトルの通り、YJITありのRubyに思いのほか肉薄され、もはや余裕がなくなったので、少しでも差を付けられるようにメソッド版でも試しました。😅
Cの結果がたまたま1秒ちょうどだったので、今回は結果の数値がそのまま「Cの何倍か」になります。Ruby YJIT をビルドするついでに Rust をインストールしたので Rust でも計測してみました(コードは Rustでたらいまわし よりお借りして改変しました)。「Cより速い」つながり(?)で Julia でも試してみましたが、どうやら竹内関数ではそこまで速くはならないみたいです(でも十分速い!)。
言語 | 処理系 | 結果 | 対C比 | 前回(ニセ竹内関数)の対C比 |
C | gcc 9.4.0 | 0.735 sec | 1.00倍 | — |
Smalltalk (メソッド) | Squeak 6.0 | 2.55 sec | 3.47倍 | — |
TruffleSqueak 22.2.0 | 5.59 sec | 7.61倍 | — | |
Pharo 10.0.0 | 2.45 sec | 3.33倍 | — | |
Smalltalk (ブロック) | Squeak 6.0 | 3.87 sec | 5.27倍 | 4.45倍 (Squeak 5.3) |
TruffleSqueak 22.2.0 | 21.1 sec | 28.7倍 | — | |
Pharo 10.0.0 | 3.62 sec | 4.93倍 | 4.81倍 (Pharo 8.0.0) | |
Python | Python 3.11.0rc1 | 29.3 sec | 39.9倍 | — |
Python 3.10.7 | 53.0 sec | 72.1倍 | 74.6倍 (3.10.0b3+) | |
Python 3.10.7 (numba.njit使用時) | 3.58 sec | 4,87倍 | — | |
PyPy 3.9-7.3.9 | 9.19 sec | 12.5倍 | — | |
GraalPython 3.8.5 | 7.20 sec | 9.80倍 | — | |
Ruby | Ruby 3.2.0dev (YJIT) | 4.08 sec | 5.55倍 | — |
Ruby 3.2.0dev (MJIT) | 5.47 sec | 7.44倍 | — | |
Ruby 3.2.0dev (JITなし) | 17.7 sec | 24.1倍 | 22.2倍 (3.1.0dev) | |
truffleruby 22.2.0 | 5.14 sec | 6.99倍 | — | |
JavaScript | Node.js 17.9.1 | 2.14 sec | 2.91倍 | 2.84倍 (17.9.1) |
Julia | Julia 1.8.0 | 1.18 sec | 1.61倍 | — |
Rust | rustc 1.63.0 | 0.790 sec | 1.07倍 | — |
Go | go1.19 | 0.849 sec | 1.16倍 | — |
PHP | PHP 8.1.0 (JITあり) | 4.47 sec | 6.08倍 | — |
PHP 8.1.0 (JITなし) | 11.3 sec | 15.4倍 | — | |
Common Lisp | SBCL 1.4.5 | 2.61 sec | 3.55倍 | — |
SBCL 1.4.5 (最適化あり) | 0.590 sec | 0.803倍 | — | |
Java | OpenJDK 18.0.2.1 | 0.655 sec | 0.891倍 | — |
OpenJDK 17.0.4 GraalVM CE 22.2.0 | 0.884 sec | 1.20倍 | — | |
C# | .Net 6.0.400 | 1.81 sec | 2.46倍 | — |
.Net 6.0.400 (最適化あり) | 1.05 sec | 1.43倍 | — | |
F# | .Net 6.0.400 | 1.27 sec | 1.73倍 | — |
.Net 6.0.400 (最適化あり) | 0.983 sec | 1.34倍 | — | |
Swift | swiftc 5.7 | 5.58 sec | 7.59倍 | — |
swiftc 5.7 (最適化あり) | 0.780 sec | 1.06倍 | — |
x が y より大きくないときに z ではなく y を返すように変えたのと、竹内先生のコードに倣って if 内の順番を変えた以外は前回とほぼ一緒です。ニセ(…と連呼すると語弊がありますが「マッカーシー版」)と違って正式な竹内関数 tarai(2n, n, 0) では n=10 だと無理っぽそうだったので、n=7 で計算させました。
Pythonは伸びしろがいっぱいあるので「4年後に5倍の速度」は大丈夫そうですね!
Smalltalk (メソッド版)
「Tarai class >>」はクラスブラウザなどを使って定義した「Tarai」クラスのクラスメソッドに x:y:z: メソッドを定義することを意味します。
Tarai class >> x: x y: y z: z ^ x > y ifTrue: [ Tarai x: (Tarai x: x-1 y: y z: z) y: (Tarai x: y-1 y: z z: x) z: (Tarai x: z-1 y: x z: y)] ifFalse: [y]
| ans | (Time millisecondsToRun: [ans := Tarai x: 14 y: 7 z: 0]) -> ans
Smalltalk (ブロック版)
| tarai ans | tarai := nil. tarai := [:x :y :z | x > y ifTrue: [ tarai value: (tarai value: x-1 value: y value: z) value: (tarai value: y-1 value: z value: x) value: (tarai value: z-1 value: x value: y)] ifFalse: [y] ]. (Time millisecondsToRun: [ans := tarai value: 14 value: 7 value: 0]) -> ans
Cの結果と使用したコード
$ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~18.04) 9.4.0 ... $ gcc -O3 tarai.c -o tarai_O3 $ ./tarai_O3 0.734794 14 $ cat tarai.c #include <stdio.h> #include <time.h> int tarai(int x, int y, int z){ if (x > y){ return tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) ); } else { return y; } } int main(void){ struct timespec time1, time2; float delta; clock_gettime(CLOCK_REALTIME, &time1); int ans = tarai(14, 7, 0); clock_gettime(CLOCK_REALTIME, &time2); delta = time2.tv_sec - time1.tv_sec + (float)(time2.tv_nsec - time1.tv_nsec) / 1000000000; printf("%f %d\n", delta, ans); return 0; }
Pythonの結果と使用したコード
$ python -V; python tarai.py Python 3.10.7 53.01142239570618 14 $ python -V; python tarai.pyPython 3.11.0rc1 29.337019681930542 14 $ cat tarai.py from time import time def tarai(x, y, z): if x > y: return tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) ) else: return y start = time() ans = tarai(14, 7, 0) print( time() - start, ans )
Python numba.njit 使用時の結果とコード
$ pip list Package Version ---------- ------- llvmlite 0.39.1 numba 0.56.2 numpy 1.23.2 pip 22.2.2 setuptools 59.8.0 $ python -V; python tarai-njit.py Python 3.10.7 3.5813117027282715 14 $ cat tarai-njit.py from time import time from numba import njit, i2 @njit(i2(i2,i2,i2)) def tarai(x, y, z): if x > y: return tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) ) else: return y start = time() ans = tarai(14, 7, 0) print( time() - start, ans )
PyPyのバージョンと結果
$ pypy -V; pypy tarai.py Python 3.9.12 (05fbe3aa5b0845e6c37239768aa455451aa5faba, Mar 29 2022, 08:15:34) [PyPy 7.3.9 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] 9.192949771881104 14
GraalPython のバージョンと結果
$ graalpython -V; graalpython tarai.py GraalVM Python 3.8.5 (GraalVM CE Native 22.2.0) 7.203999996185303 14
Rubyの結果と使用したコード
$ ruby -v tarai.rb ruby 3.2.0dev (2022-09-08T15:46:21Z master 6d93644ba1) [x86_64-linux] 14 17.7318423 $ ruby --yjit -v tarai.rb ruby 3.2.0dev (2022-09-08T15:46:21Z master 6d93644ba1) +YJIT [x86_64-linux] 14 4.084934 $ ruby -v --mjit tarai7.rb ruby 3.2.0dev (2022-09-08T15:46:21Z master 6d93644ba1) +MJIT [x86_64-linux] 14 5.468897 $ cat tarai.rb def tak(x, y, z) if x > y then tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)) else y end end start = Time.now puts tak(14, 7, 0) puts Time.now - start
TruffleRuby のバージョンと結果
$ ruby -v tarai.rb truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE Native [x86_64-linux] 14 5.1394269999999995
JavaScript (Node.js) の結果と使用したコード
$ node -v; node tarai.js v17.9.1 2136 14 $ cat tarai.js function tarai(x, y, z) { if(x > y) { return tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) ); } else { return y; } } var start = (new Date()).getTime(); var ans = tarai(14, 7, 0); console.log((new Date()).getTime() - start, ans)
Juliaの結果と使用したコード
$ julia -v; julia tarai.jl julia version 1.8.0 1.184309 seconds 14 $ cat tarai.jl tak(x, y, z) = x > y ? tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y)) : y @time ans = tak(14, 7, 0) println(ans)
Rustの結果と使用したコード
$ rustc -V rustc 1.63.0 (4b91a6ea7 2022-08-08) $ rustc -C opt-level=3 -C debug_assertions=no tarai.rs $ ./tarai 14 0.7899205 $ cat tarai.rs use std::time::Instant; fn tarai(x: i32, y: i32, z: i32) -> i32 { if x > y { tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) } else { y } } fn main() { let start_tarai = Instant::now(); println!("{}", tarai(14, 7, 0)); let end_tarai = start_tarai.elapsed(); let tarai_sec = end_tarai.as_secs() as f64 + end_tarai.subsec_nanos() as f64 / 1000_000_000.0; println!("{}", tarai_sec); }
Goの結果と使用したコード
$ go version go version go1.19 linux/amd64 $ go run tarai.go 849 14 $ cat tarai.go package main import ( "fmt" "time" ) func tarai(x int, y int, z int) int { if x > y { return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) } else { return y } } func main() { start := time.Now() ans := tarai(14, 7, 0) fmt.Printf("%v %v\n", time.Since(start).Milliseconds(), ans) }
PHPの結果と使用したコード
$ php -i | grep opcache opcache.enable => On => On opcache.enable_cli => On => On opcache.jit => tracing => tracing opcache.jit_buffer_size => 128M => 128M opcache.revalidate_freq => 60 => 60 ... $ php -v; php tarai.php PHP 8.1.9 (cli) (built: Sep 10 2022 22:10:58) (NTS) Copyright (c) The PHP Group Zend Engine v4.1.9, Copyright (c) Zend Technologies with Zend OPcache v8.1.9, Copyright (c), by Zend Technologies 4.473552942276 14 $ php -i | grep opcache opcache.jit_buffer_size => 0 => 0 ... $ php tarai.php 11.325684070587 14 $ cat tarai.php <?php function tarai(int $x, int $y, int $z) : int { if ($x > $y) { return tarai(tarai($x - 1, $y, $z), tarai($y - 1, $z, $x), tarai($z - 1, $x, $y)); } else { return $y; } } $start = microtime(true); $ans = tarai(14, 7, 0); $time = microtime(true) - $start; echo "{$time} {$ans}\n";
Common Lisp (最適化なし)の結果と使用したコード
$ sbcl --version; sbcl --script tarai.lisp SBCL 1.4.5.debian Evaluation took: 2.608 seconds of real time 2.607781 seconds of total run time (2.606888 user, 0.000893 system) 100.00% CPU 6,008,334,038 processor cycles 0 bytes consed 14 $ cat tarai.lisp (defun tarai (x y z) (if (> x y) (tarai (tarai (1- x) y z) (tarai (1- y) z x) (tarai (1- z) x y)) y ) ) (defvar *ans*) (time (setq *ans* (tarai 14 7 0))) (princ *ans*) (terpri)
Common Lisp (最適化あり)の結果と使用した「https://g000001.cddddr.org/3872263095」でご提示いただいたコード
$ sbcl --script tarai7-g1.lisp Evaluation took: 0.590 seconds of real time 0.590533 seconds of total run time (0.590533 user, 0.000000 system) 100.17% CPU 1,360,580,830 processor cycles 0 bytes consed 14 $ cat tarai-g1.lisp (defun tarai (x y z) (declare (optimize (speed 3) (debug 0) (safety 0))) (labels ((tarai (x y z) (declare (fixnum x y z)) (the fixnum (if (> x y) (tarai (tarai (1- x) y z) (tarai (1- y) z x) (tarai (1- z) x y)) y)))) (declare (inline tarai)) (tarai x y z))) (compile 'tarai) (princ (time (tarai 14 7 0))) (terpri)
Java HotSpotVMの結果と使用したコード
$ java -version; javac -version openjdk version "18.0.2.1" 2022-08-18 OpenJDK Runtime Environment (build 18.0.2.1+1-1) OpenJDK 64-Bit Server VM (build 18.0.2.1+1-1, mixed mode, sharing) javac 18.0.2.1 $ javac tarai.java $ java Tarai 655 14 $ cat tarai.java class Tarai { static private int tarai(int x, int y, int z) { if (x > y) { return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)); } else { return y; } } static public void main(String args[]) { long start = System.currentTimeMillis(); int ans = tarai(14, 7, 0); System.out.println(System.currentTimeMillis() - start); System.out.println(ans); } }
Java GraalVMのバージョンと結果
$ java -version; javac -version openjdk version "17.0.4" 2022-07-19 OpenJDK Runtime Environment GraalVM CE 22.2.0 (build 17.0.4+8-jvmci-22.2-b06) OpenJDK 64-Bit Server VM GraalVM CE 22.2.0 (build 17.0.4+8-jvmci-22.2-b06, mixed mode, sharing) javac 17.0.4 $ javac tarai.java $ java Tarai 884 14
C#の結果と使用したコード
$ dotnet --version 6.0.400 $ dotnet new console -o Tarai_cs $ cat Program.cs using System.Diagnostics; class Program { static void Main() { var sw = new Stopwatch(); sw.Start(); var ans = Tarai(14, 7, 0); sw.Stop(); Console.WriteLine("" + sw.ElapsedMilliseconds + " " + ans); } static int Tarai(int x, int y, int z) { if (x > y) { return Tarai( Tarai(x - 1, y, z), Tarai(y - 1, z, x), Tarai(z - 1, x, y)); } else { return y; } } } $ dotnet run 1809 14 $ dotnet run --configuration Release 1048 14
F#の結果と使用したコード
$ dotnet --version 6.0.400 $ dotnet new console -lang F# -o Tarai_fs $ cat Program.fs let rec tarai x y z = if x > y then tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y) else y let stopWatch = System.Diagnostics.Stopwatch.StartNew() let ans = tarai 14 7 0 stopWatch.Stop() printfn "%f %d" stopWatch.Elapsed.TotalMilliseconds ans $ dotnet run 1272.238400 14 $ dotnet run --configuration Release 983.585300 14
Swiftの結果と使用したコード
$ swift -version Swift version 5.7 (swift-5.7-RELEASE) Target: x86_64-unknown-linux-gnu $ swiftc tarai.swift && ./tarai 14 5.5811779499053955 $ swiftc -Ounchecked tarai.swift && ./tarai 14 0.7802159786224365 $ cat tarai.swift import Foundation import CoreFoundation func tarai(_ x: Int, _ y: Int, _ z: Int) -> Int { if x > y { return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y)) } else { return y } } let start = CFAbsoluteTimeGetCurrent() let ans = tarai(14, 7, 0) print("\(ans) \(CFAbsoluteTimeGetCurrent() - start)")