Pythonが速度改善に本気出すと聞いたので恒例のたらい回しベンチをとってみたら、RubyがYJITですごく速くなっていて驚いた話

See More

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)")