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

2022-09-09改訂: gcc バージョンが古すぎたのと、C が内部計測でなかった点を改め計測しなおしました。結果、Rust は C より速くはなくなりました。紛らわしいことで、ごめんなさい。また、gcc のバージョンアップに伴い、Python および Ruby についてはビルドと計測をしなおしたので、これらも少し速い値に変わっています。この点もどうぞあしからず。
2022-09-10追記:ご要望のあった Python numba.njit 使用時と Go の結果を追加しました。PHPJIT 有効化が面倒だったので断念しました^^;
2022-09-10追記2:C の計測で clock() を使うのはフェアではないという指摘がありましたので、念のため clock_gettime() を使用したコードに差し替えました。結果に大きな差はありません。
2022-09-10追記3:PHPJIT有効化されない理由と回避方法 が分かったので、計測して追加しました。
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 の結果を追加しました。

竹内関数 (今回はyを返す正式版) tarai(14, 7, 0) にかかる時間を、手元の環境(Intel Core i9-9880H @ 2.30GHz、Win10 64-bit WSL環境)で計測してみました。

SmalltalkSqueak と 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倍   — 
 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 (最適化あり)の結果と使用した「#:g1: Common Lispでこれより速いtaraiの書き方があったら教えて欲しい」でご提示いただいたコード

$ 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

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

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

竹内関数 (正確には“ニセ”竹内関数) tak(20, 10, 0) にかかる時間を、手元の環境(Intel Core i9-9880H @ 2.30GHz、Win10 64-bit WSL環境)で計測してみました。前回からちょうど(?)7年ですね^^;

SmalltalkSqueak は Win版をそのまま、Pharo は次のページを参考に WSL にインストールして動かしてみました。

 言語   処理系   結果   対C比   参考:2014年時点 
 Smalltalk   Squeak 5.3   0.596 sec   4.45倍   6.12倍 (Squeak 4.5) 
    Pharo 8.0.0   0.644 sec   4.81倍   — 
    GNU Smalltalk 3.2.5   7.97 sec   59.5倍   65.0倍 (3.1) 
 Python   Python 3.10.0b3+   10.0 sec   74.6倍   52.53倍 (3.2.5) 
 Ruby   Ruby 3.1.0dev   2.97 sec   22.2倍   20.8倍 (2.2.0dev) 
 Scheme   Gauche 0.9.10   2.44 sec   18.2倍   15.1倍 (0.9.5_pre1) 
 JavaScript   Node.js 16.3.0   0.381 sec   2.84倍   2.23倍 (0.10.31) 
 C   gcc 7.5.0   0.134 sec   1.00倍   1.00倍 (4.8.3) 

対C比では7年前とあまり代わり映えしませんが、Rubyが速くなっていないのがちょっと意外ですね。

コードは以前と一緒です。

| 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

Squeak は起動後 Tools → Workspace で、Pharo は ./pharo-ui で起動後、Tools → Playground でプレイグラウンドを呼び出し、コードを貼り付けてから全選択、右クリックメニューや ctrl + p などで print it すると実行と結果を表示できます。

Pharo Smalltalkでの実行画面
Squeak Smalltalk での実行画面

GNU Smalltalk でも動きますが、最後の式を括弧でくくって printNl しないと結果を出力できません。

$ gst -v; gst tak.st
GNU Smalltalk version 3.2.5
...
7976->1

$ cat tak.st
| 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) printNl

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

$ python -V; python tak.py
Python 3.10.0b3+
10.04528284072876 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 3.1.0dev (2021-06-23T06:14:21Z master 69ce9e4187) [x86_64-linux]
1
2.9718293

$ 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; gosh tak.scm
Gauche scheme shell, version 0.9.10 [utf-8,pthreads], x86_64-pc-linux-gnu
...
;(time (display (tak 20 10 0)))
; real   2.441
; user   2.440
; 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; node tak.js
v16.3.0
381 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 (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
...

$ 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.134s
user    0m0.134s
sys     0m0.000s

Squeak Smalltalkを多コア対応させる10年程前の試み「RoarVM」で再び遊ぶ その4

副詞 valueLY: が並列処理にならない件を少し手を入れて解消する

前回 メッセージに織り込まれた副詞や自動詞の処理のされ方の謎が解けて、だいぶ目が慣れてきました。

実は当初、Ractorとの比較で たらい回しベンチを書いたとき、次のように副詞の valueLY: を使った実装を試してみたのですが…

"(FileStream fileNamed: 'Tarai.st') fileIn.
Transcript open"

Transcript clear.

(1 to: 16) collect: [:N |
    Transcript cr; show: N -> {
        "parallel version?"
        #'par?' -> ([(Array new: N withAll: Tarai) asEnsembleOfElements
            valueLY: [:tarai | tarai x: 12 y: 6 z: 0]] timeToRun / 1.0e3
        )
    }
]

しかしこれがまったく並列にならなかったのです。

1->#(#'par?'->4.531)
2->#(#'par?'->9.064)
3->#(#'par?'->13.063)
4->#(#'par?'->17.362)"
...

遊びはじめの頃でよくわからずそのままこの実装はボツにしたのですが、今回改めてどうしてか気になったので調べてみることにしました。ずばり、valueLY: の実際の処理を担当する Sly3ModValuely>>#extendOperandTuples:operand:membersOrNil: の定義をよく見てみると…

Sly3ModValuely >> extendOperandTuples: operandTuplesSoFar operand: operand membersOrNil: operandMembers
    | r mems |
    mems _ operandMembers ifNil: [OrderedCollection with: operand] ifNotNil: [operandMembers].

    ^ operandTuplesSoFar
        ifEmpty: [mems collect: [:m| OrderedCollection with: (parameter value: m)]]
        ifNotEmpty: [ 
            operandTuplesSoFar size = mems size ifFalse: [self error: 'mismatch in number'].
            r _ OrderedCollection new.
            operandTuplesSoFar with: mems do: [:ot :m| r addLast: (ot copy addLast: (parameter value: m); yourself)].
            r]

なんということもなく、普通に #collect: や #with:do: を使っていて、並列に処理しようとする気概が感じられません。^^; これでは直列処理になるのは当然です。

せっかくなので並列処理になるように改変してみましょう。 前者は #parallelCollect: という並列化バージョンがすぐ見つかりましたのでこれと置き換えればよさそうですが、後者については #with:parallelDo: はもちろん #parallelDo: が探しても見つかりません。

いろいろ当たってみたところ #doInParallel: というのが見つかりました。ところがこれの定義を見てまたびっくり。

Collection >> doInParallel: aBlock
    self parallelCollect: aBlock

手抜きにも程があるだろうと少々呆れつつ、#parallelCollect: を参考に次のように書き直してみました。

Collection >> doInParallel: aBlock
    | task  barrier |
    self ifEmpty: [^ self].
    (Sly3 serializeForDebugging or: [self size = 1]) ifTrue: [^ self do: aBlock].
    barrier _ RVMBarrier new signalsNeededToPass: self size.
    self do:[:each|
        task _ [
            [aBlock copy fixTemps value: each] ifCurtailed: [barrier signal].
            barrier signal] asSlyMemberProcess.
            task resume].
    barrier wait

あらためて、Sly3ModValuely>>#extendOperandTuples:operand:membersOrNil: を次のように書き換えます。例によってなぜかクロージャではなく(つまり、古典的 Smalltalk-80 の BlockContext に先祖返り)させれたこのイメージのブロックは再入ができないので、#parallelCollect: および #doInParallel: の引数のブロックないで parameter をコール(#value:)しているところは忘れずに事前に copy fixTemps しておきます。

Sly3ModValuely >> extendOperandTuples: operandTuplesSoFar operand: operand membersOrNil: operandMembers
    | r mems |
    mems _ operandMembers ifNil: [OrderedCollection with: operand] ifNotNil: [operandMembers].

    ^ operandTuplesSoFar
        ifEmpty: [mems parallelCollect: [:m| OrderedCollection with: (parameter copy fixTemps value: m)]]
        ifNotEmpty: [ 
            operandTuplesSoFar size = mems size ifFalse: [self error: 'mismatch in number'].
            r _ OrderedCollection new.
            (1 to: mems size) doInParallel: [:idx | r addLast: ((operandTuplesSoFar at: idx) copy addLast: (parameter copy fixTemps value: (mems at: idx)); yourself)].
            r]

さて、これでどうでしょう。

1->#(#par->4.57)
2->#(#par->4.476)
3->#(#par->4.539)
4->#(#par->4.719)"
...

もくろみ通り、並列化成功です。

なぜ valueLY: が並列化されていなかったのかは謎ですが、#doInParallel: の実装を見るにつけいろいろと察せられ、なんだかちょっと残念な感じになってきました。

なお、serialLYvalueLY: と書いても副詞 valueLY: を同じ副詞の serialLY の修飾とは見なされないようで、直列化はされませんでした。

あと冒頭の valueLY: はレシーバーのアンサンブルの修飾になるわけですが、各引数のアンサンブルにも個別に valueLY: 修飾が可能なようです。

たとえばいささか無理矢理な例ですが…

[%{Tarai. Tarai} valueLY: [:tarai | tarai x: 12 y: 6 z: 0. tarai]
    x: %{12. 12} valueLY: [:x | Tarai x: x y: 6 z: 0. x]
    y: %{6. 6} valueLY: [:y | Tarai x: 12 y: y z: 0. y]
    z: %{0. 0} valueLY: [:z | Tarai x: 12 y: 6 z: z. z]] timeToRun

というように書けば、レシーバーの %{Tarai. Tarai} というアンサンブルに対し、最初の valueLY: が適用され、その返値(のアンサンブルの各要素である Tarai )に対し送られる x: ~ y: ~ z: ~ というメッセージの各引数についても、それぞれの直後に書いた valueLY: で修飾することができる(その結果、セレクタとしては valueLY:x:valueLY:y:valueLY:z:valueLY: になる!)ので、つごう4+1=5回の 2つの並列のたらい回しを回す式の記述が可能になります。

計測してみると、前述の Sly3ModValuely>>#extendOperandTuples:operand:membersOrNil: 等への細工を済ませておけば、レシーバーに加え、各引数に対する valueLY: 修飾もそれぞれ2つの並列で行われるようです。ただレシバーと各引数に対する4つの修飾に伴う処理は Sly3 の並列化の管轄外なのか直列で処理されます。

"すべての valueLY: 処理をコメントアウト #ori=> 4624 #mod=> 4609 "
"レシーバーを修飾する valueLY: のみ実行 #ori=> 13178 #mod=> 9347 "
"レシーバーと第一引数を修飾する valueLY: のみ実行 #ori=> 22171 #mod=> 13984 "
"レシーバーと第一、第二引数を修飾する valueLY: を実行 #ori=> 31017 #mod=> 18245 "
"すべての valueLY: 処理を実行 #ori=> 39734 #mod=> 22848 "
"参考:たらい回しベンチ1回のみ実行時の計測"
[Tarai x: 12 y: 6 z: 0] timeToRun "=> 4680 "

今回はここまで。valueLY: による引数の修飾の記述は、Smalltalk と違い、キーワードメッセージでも(二つ目以降のキーワードの頭文字を大文字にするルールを設けることで、括弧を使わずに―)複数同時に使用可能な SELF を彷彿とさせますね。David Ungar 率いるプロジェクトだけに。

Squeak Smalltalkを多コア対応させる10年程前の試み「RoarVM」で再び遊ぶ その3

前回、RoarVM 専用並列処理特化 DSL である Sly3 について、「アンサンブルが同名メソッドを持っていなければ、副詞 IndividualLY が無くてもメッセージはアンサンブル内の各要素に委譲される」と書きましたが、あれは嘘でした。すみません。

blocks copy fixTemps

と複数のブロックを収めたアンサンブルである blocks に対して、アンサンブルにない BlockContext 固有の fixTemps はともかく、誰でも反応できるはずの copy を送っても IndividualLY になるのはおかしいな…と気になって調べてみたところ、完全な思い違いが判明しました。お恥ずかしい。

そもそもこの勘違いのきっかけは、Sly3Ensemble に #doesNotUnderstand: が(再)定義されているのを見つけて、てっきり自分が理解できないメッセージについてのみその要素にメッセージを転送する、よくある仕組みだろうと早合点したことでした。

実際は、アンサンブルを構成する Sly3Ensemble>>#members: 内で Object>>#primitiveSetExtraWordSelector: および Object>>#primitiveSetExtraPreheaderWord: をコールすることでプリミティブレベルで自身の情報を書き換えることで、自身に送られたメッセージは(先述の、よくある doesNotUnderstand: の再定義による仕組みを介することなしに) members に収められたコレクションに sentToEnsemble: aMessage をコールするかたちで無条件に委譲される仕組みになっていました。(これだけだとアンサンブルを構成するコレクションに委譲されるだけですが、さらに先の処理で一定の条件を満たした場合に各要素に委譲されるようです。)

Sly3Ensemble >> members: aCollection
    "crude check:"
    self primitiveSetExtraWordSelector: #sentToEnsemble:.
    aCollection primitiveSetExtraPreheaderWord: self.
    members _ aCollection.
    ^ self

ではなぜ通常は使う必要がない #doesNotUnderstand: が再定義されているかというと、これも当該メソッドのソースにちゃんと説明が書いてありました。^^;

Sly3Ensemble >> doesNotUnderstand: aMessage
    "Try to process this message as an ensemble dispatch message to help in the case of inlined primitive calls  like perform:with:with:"
    ^ Sly3EnsembleMessageDispatcher dispatch: (Sly3UnprocessedEnsembleMessage fromMessage: aMessage theEnsemble: self)

通常のメッセージ式ではなく、#perform: などを使ってアンサンブルにメッセージが送られた場合であっても、同様の仕組みが(もとより、Sly3Ensemble に定義されていないメソッドのコールに限られるため、不完全ではありますが―)機能するように備えたもの…ということらしいです。

ただ残念ながら、デバッガーで使われるインタープリターシミュレーターにはこうした配慮が行き届いていない(あるいは当該機構によりインタープリターシミュレーターがバグる?)ようで、結果的にデバッガーでステップ実行したときと通常実行したときで動きが異なる事態が発生してしまうみたいなので要注意です。

関連してデバッガーについては、これを動作させようとすると並列処理に起因すると思われるノーティファイアーの嵐が出まくって操作不能に陥ることが多々あり、やはりプロセス(スレッド)を多コア対応にできても Squeak Smalltalk 環境を既存のコードのまま運用するのは難しく、全体の書き直しが必要でそれはきっと大変な作業になるのだろうな…と実感させられます。RoarVM/Sly3 評価用の renaissance.image が かなり手間をかけてMVC ベースや、ブロックがクロージャーでなくすなど過去の Smalltalk の状態に戻してしてあったりするのも、並列処理に起因するトラブルにできるだけシンプルな対応で済ませたいがためだったのかもしれませんね。

次回へ続く。

Squeak Smalltalkを多コア対応させる10年程前の試み「RoarVM」で再び遊ぶ その2

前回 の続き。

多コア用 RoarVM 向けには Sly3 という並列処理を記述するための DSL も同時に開発されていました。もともと Ly という Smalltalk上に実装された JavaScript ライクな文法の並列処理言語とその処理系が作られ、それを Smalltalk 内で DSL化したのが Sly で、Sly3 はその3サイクル目ということらしいです。

この Ly/Sly や RoarVM はプロトタイプベース・オブジェクト指向の祖として知られる SELF言語を開発者した David Ungar とテクトロニクス社出身の Sam S. Adams らが参加したIBM基礎研究所・ポートランド州立大学、ブリュッセル自由大学の共同研究「ルネッサンス」プロジェクトの成果物です。

www.stefan-marr.de

Ly/Sly は「アンサンブル」と呼ばれる特殊なコレクションにオブジェクトを収めておき、それにメッセージを送ることで要素であるオブジェクトに並列処理をさせる仕組みになっています。このとき送るメッセージにすこし細工があって、最終的にコールされるメソッドをどのように実行するのかをメソッド名を修飾する副詞や動名詞としてメッセージに織り込むことで並列処理を制御します。

たとえば、%{1. 2. 3} というアンサンブルに含まれる要素に対して %{10. 20. 30} というアンサンブルの要素を加える(plus:)場合、「総当たりで」(roundly)という副詞で修飾したセレクタ(通常の Smalltalk ではメソッド名と同義ですが、Sly3 ではそういうメソッドがあるわけではないのであくまでメッセージの一部)を合成して用いた次のような式として表現できます。

%{1. 2. 3} plusRoundLY: %{10. 20. 30}

"=> %{11. 12. 13. 21. 22. 23. 31. 32. 33. } "

このときセレクタを修飾する副詞は語尾の ly を大文字で LY と記述するルールになっていて、また、この副詞の語尾の ly がこの言語の名前の由来なのだと思います。

なお、ここで修飾される側の「plus:」は、通常であれば「+」を用いたいところですが、残念ながら Smalltalk の文法上の制約からセレクタを記号とをアルファベットの混成にする(roundLY+、+roundLY: など)ことができないので Object >> #plus: といったキーワードセレクタのメソッドとして別に定義しておく必要があります。念のため。

ちなみに { } は、各要素を生成する式(もちろんリテラル式も可)をピリオドで区切って連ね、それらを { } でくくることで動的に配列を定義できるよう Squeak Smalltalk に新たに(と言っても 1990年代なのでずいぶん前ですが─)追加された記法です。それまでの Smalltalk-80 では、リテラルを要素とする配列定義( #('this' is $a 10) など)はありましたが、動的に要素を定義したければ配列等のクラスメソッドとして用意された with: 、with:with: 、with:with:with: … を使う必要がありました。{ } による動的配列定義記法はその後、他の Smalltalk 処理系にも広まりました。

#('this' is $a 10) collect: [:each | each hash]

"=> #(219033213 218806809 97 10) "
(Array with: 'siht' reversed with: 'is' asSymbol with: 'abc' first with: 3 + 7)
    collect: [:each | each hash]

"=> #(219033213 218806809 97 10) "
{'siht' reversed. 'is' asSymbol. 'abc' first. 3 + 7} 
    collect: [:each | each hash] 

"=> #(219033213 218806809 97 10) "

Sly3 ではこれの頭に % を付すことでアンサンブルを生成する式として利用できます。他にも、Sly3Ensemble class >> #withMembersFrom: や Collection >> #asEnsembleOfElements が使えます。

%{'this'. #is. $a. 10} hashIndividualLY

"=> %{219033213. 218806809. 97. 10. } "
(Sly3Ensemble withMembersFrom: #('this' is $a 10)) hashIndividualLY

"=> %{219033213. 218806809. 97. 10. } "
#('this' is $a 10) asEnsembleOfElements hashIndividualLY

"=> %{219033213. 218806809. 97. 10. } "

アンサンブル自身ではなく、それに含まれる要素それぞれに hash を送るために副詞 individually で修飾するため、hashIndividualLY と記述しています。

このように副詞が LY なのに対し、動名詞は ING で、アンサンブルの要素の畳み込み処理を指示するときに使います。

%{1. 2. 3. 4} totallING "=> 10 "

使用できる副詞と動名詞は Sly3Mod~ で始まるクラス名から調べられます。

Smalltalk allClasses select: [:class | class name beginsWith: 'Sly3Mod']

"=> an OrderedCollection(
    Sly3ModAnding
    Sly3ModAveraging
    Sly3ModCollectionly
    Sly3ModConcatenating
    Sly3ModDuplicatively
    Sly3ModEnsembling
    Sly3ModGathering
    Sly3ModIndividually
    Sly3ModMaxing
    Sly3ModMining
    Sly3ModOring
    Sly3ModPlainly
    Sly3ModRandomly
    Sly3ModRoundly
    Sly3ModSelecting
    Sly3ModSelectively
    Sly3ModSerially
    Sly3ModStandardDeviationing
    Sly3ModTotalling
    Sly3ModValuely
    Sly3ModWholly) "

Sly3ModStandardDeviationing のように実質使えないものもあるので要注意ですが…^^;

さて、ざっと Sly3 の様子がわかったところで、前回の たらい回しベンチを Sly3 で書き直してみたのがこちらです。

| blocks |

"(FileStream fileNamed: 'Tarai.st') fileIn.
Transcript open"

Transcript clear.

(1 to: 16) collect: [:N |

    blocks _ Sly3Ensemble withMembersFrom: (Array new: N withAll: [Tarai x: 12 y: 6 z: 0]).
    blocks _ blocks copy fixTemps.

    Transcript cr; show: N -> {
        "sequential version"
        #seq -> ([blocks serialLYvalue] timeToRun / 1.0e3).
        "parallel version"
        #par -> ([blocks value] timeToRun / 1.0e3)
    }
]

なぜかクロージャーでなくなってしまったブロックを繰り返し評価するために copy して fixTemps する必要があるなど余計な処理が入っていますが、実にすっきりとかけていて素晴らしいですね。(ちなみに、アンサンブルが同名メソッドを持っていなければ、副詞 IndividualLY が無くてもメッセージはアンサンブル内の各要素に委譲されるようです。ん?…でも copy は?→あとで調べておきます^^; → 勘違いしていました

結果はこちら。Tarai x: 14 y: 7 z: 0 だとキツいので^^; 上のコードのとおり Tarai x: 12 y: 6 z: 0 を使った結果になります。あしからず。

1->#(#seq->3.574 #par->3.371)
2->#(#seq->6.518 #par->3.299)
3->#(#seq->10.264 #par->3.792)
4->#(#seq->13.359 #par->3.429)
5->#(#seq->16.954 #par->3.662)
6->#(#seq->19.603 #par->3.519)
7->#(#seq->23.365 #par->3.467)
8->#(#seq->26.263 #par->3.753)
9->#(#seq->30.277 #par->3.847)
10->#(#seq->33.913 #par->3.645)
11->#(#seq->37.356 #par->3.751)
12->#(#seq->40.46 #par->3.933)
13->#(#seq->43.841 #par->3.717)
14->#(#seq->46.286 #par->3.729)
15->#(#seq->50.822 #par->3.932)
16->#(#seq->54.656 #par->3.793)

[追記] よく考えてみたところ、アンサンブルに送る(ことで、その要素に送られる)メッセージは単項メッセージでなければいけないということはなかったので、アンサンブルに Tarai を必要な数だけ入れておいて x: 12 y: 6 z: 0 を送るのでもよいのではないか…と気づいたので書き直してみました。逐次実行は同じように副詞 serialLY で修飾しています。

| tarais |

"(FileStream fileNamed: 'Tarai.st') fileIn.
Transcript open"

Transcript clear.

(1 to: 16) collect: [:N |

    tarais _ (Array new: N withAll: Tarai) asEnsembleOfElements.

    Transcript cr; show: N -> {
        "sequential version"
        #seq -> ([tarais serialLYx: 12 y: 6 z: 0] timeToRun / 1.0e3).
        "parallel version"
        #par -> ([tarais x: 12 y: 6 z: 0] timeToRun / 1.0e3)
    }
]

こちらの方がずっと Sly3 らしくていいですね!

結果もほぼ同じです。

1->#(#seq->3.055 #par->3.332)
2->#(#seq->6.437 #par->3.164)
3->#(#seq->9.861 #par->3.605)
4->#(#seq->13.64 #par->3.496)
5->#(#seq->15.791 #par->3.378)
6->#(#seq->19.625 #par->3.938)
7->#(#seq->22.378 #par->3.691)
8->#(#seq->25.633 #par->3.525)
9->#(#seq->29.435 #par->3.655)
10->#(#seq->32.004 #par->3.664)
11->#(#seq->34.929 #par->3.874)
12->#(#seq->37.529 #par->3.629)
13->#(#seq->41.2 #par->3.761)
14->#(#seq->47.115 #par->4.201)
15->#(#seq->49.703 #par->3.783)
16->#(#seq->53.233 #par->3.824)

次回へ続く

Squeak Smalltalkを多コア対応させる10年程前の試み「RoarVM」で再び遊ぶ

昨年末の登場以来、Apple の M1マシンの爆速ぶりが大々的にフィーチャーされ続けているおかげもあってか、インテル版のそこそこ盛った仕様の MacBook Pro(16インチ, Late 2019)の中古価格にかなりお手頃感が出てきました。そこで、いろいろ不具合が蓄積してきていた第4世代 Core i7 搭載の MacBook Air(Early 2014)の代替として入手してみました。M1 ほどではないにしても 8コア16スレッドの第9世代 Core i9 のパワーを手にしてふと思い立ち、10年ほど前に話題になったときに少し動かしてみたきりになっていた Squeak Smalltalkの多コア対応VMである「RoarVM」でまた少し遊んでみることに。

前に遊んだときは前述プロジェクトサイトで提供されている macOS 向けのバイナリーを使ったのですが、その後 10.15 Catalina から古い 32-bit アプリは動かせなくなってしまったので、今回は Linux 版を Windows 10(Boot Camp)の WSL2 上でビルドしました。当然のことながら 32-bit 版のライブラリパッケージを事前にインストールしておかなければならないことに加え、RoarVM/vm/src/makefiles/Makefile.common をちょっといじってやる必要がありましたが(具体的には g++ のコマンドオプションの LDFLAGS の位置を後ろにずらす)、あとはほぼ INSTALL.rst の記述通りで、3年前リリースの Ubuntu 18.04 でも思ったよりあっさりビルドして動かすことが可能なようです。

github.com

f:id:sumim:20210111020427p:plain
RoarVMで動作するMVC版Squeak3.7でたらい回しベンチ(この図ではTarai x: 12 y: 6 z: 0)を実行している様子

たらい回し関数による並列化効率の評価は ささださんのこちらの Ractor 紹介記事中のコードを参考にさせていただきました。

techlife.cookpad.com

Smalltalk 版のたらい回し関数は、最初は次のコードのようにクロージャーでさくっと書いて済ませるつもりだったのですが…

| tarai |

tarai := nil.
tarai := [:x :y :z |
    x <= y ifTrue: [y] ifFalse: [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)]].

[tarai value: 14 value: 7 value: 0] timeToRun / 1.0e3

なんと RoarVM 評価用の Squeak3.7 の仮想イメージ(renaissance.image)は GUI フレームワークに古い MVC だけしか用意されていない(Morphic が取り除かれて使えない)という細工がされているだけでなく、ブロックにクロージャーの振る舞いをさせるのに必要な BlockClosureクラスも取り除かれていて古典的な Smalltalk-80 や古い Squeak 同様にブロックの再帰呼び出しができない(!?)という謎仕様で運用されていることが判明したので、やむなく次のように Tarai クラスのクラスメソッド(x:y:z:)として書き直しました。

Smalltalk は ~GNU Smalltalk などの特殊な処理系を除き~ 一般にメソッド定義の構文が用意されていないので、スクリプト言語っぽい簡易コードにメソッド定義が混ざるといろいろ面倒なのです…^^;)

Object subclass: #Tarai
    instanceVariableNames: ''
    classVariableNames: ''
    poolDictionaries: ''
    category: 'Multicore-Benchmark'!

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

Tarai class
    instanceVariableNames: ''!

!Tarai class methodsFor: 'as yet unclassified' stamp: 'sumim 1/7/2021 01:45'!
x: x y: y z: z
    ^ x <= y ifTrue: [y] ifFalse: [self
        x: (self x: x-1 y: y z: z)
        y: (self x: y-1 y: z z: x)
        z: (self x: z-1 y: x z: y)]! !

これをシステムブラウザで定義するか、あるいは Tarai.st として保存しておき、次のベンチマークコードの最初のコメントアウトされた式でシステム内に読み込んで(file in して)から改めて次のベンチマークコード全体を選択して実行(do it)すると結果が得られます。

| queue |

"(FileStream fileNamed: 'Tarai.st') fileIn.
Transcript open"

Transcript clear.

(1 to: 16) collect: [:N |
    Transcript cr; show: N -> {
        "sequential version"
        #seq -> ([N timesRepeat: [Tarai x: 14 y: 7 z: 0]] timeToRun / 1.0e3
).

        "parallel/thread version"
        #par -> ([
            queue := SharedQueue new.
            N timesRepeat: [
                [queue nextPut: (Tarai x: 14 y: 7 z: 0)] fork
            ].
            N timesRepeat: [queue next]
        ] timeToRun / 1.0e3)
    }
]

1回実行時(あるいは HWスレッド数 N = 1)の Tarai x: 14 y: 7 z: 0 の実行時間が 155秒とかなり遅いですが、頑張って N = 16 まで回した結果が次になります。

1 -> #(#seq->152.17 #par->154.68)
2 -> #(#seq->307.371 #par->154.517)
3 -> #(#seq->458.852 #par->163.255)
4 -> #(#seq->610.838 #par->159.789)
5 -> #(#seq->765.181 #par->164.316)
6 -> #(#seq->930.125 #par->165.27)
7 -> #(#seq->1068.89 #par->169.063)
8 -> #(#seq->1227.686 #par->167.873)
9 -> #(#seq->1394.253 #par->172.45)
10 -> #(#seq->1534.125 #par->170.147)
11 -> #(#seq->1692.829 #par->170.365)
12 -> #(#seq->1883.802 #par->171.348)
13 -> #(#seq->2148.376 #par->199.649)
14 -> #(#seq->2359.443 #par->201.405)
15 -> #(#seq->2526.411 #par->204.275)
16 -> #(#seq->2684.875 #par->201.445)

しっかり並列化されていて素晴らしいですね!(小並感)

参考まで、最新の Squeak5.3 や Pharo8 では、並列化こそされませんが JIT などにより高速化された結果、N = 1 で 2.5秒程度(!!)、N = 16 の直列処理時でも 40秒程度とまずまずの性能をたたき出します。

f:id:sumim:20210111033350p:plain

f:id:sumim:20210111034429p:plain

せっかく(?)なので、Ruby3 の Ractor と、当該記事に登場する JRuby のスレッド版でも次の Ruby に焼き直したコードを使って同様の評価をしてみました。Ruby は Ractor も JRuby の Thread も N = 4 あたりから理論値を外れだして、N = 10 あたりで頭打ちになってしまうようなので今後に期待ですね。

def tarai(x, y, z)
  return y if x <= y
  tarai(
    tarai(x-1, y, z),
    tarai(y-1, z, x),
    tarai(z-1, x, y)
  )
end

require 'benchmark'
Benchmark.bm do |x|
  (1..16).each do |n|
    # sequential version
    x.report("seq-#{n}"){ n.times{ tarai(14, 7, 0) } }

    # thread version
    x.report("thr-#{n}"){
      n.times.map do
        Thread.new { tarai(14, 7, 0) }
      end.each(&:join)
    }

    if defined?(Ractor) then
      # parallel version
      x.report("par-#{n}"){
        n.times.map do
          Ractor.new { tarai(14, 7, 0) }
        end.each(&:take)
      }
    end
  end
end

f:id:sumim:20210111030219p:plain

f:id:sumim:20210111030246p:plain

ともあれ、Squeak/Pharo Smalltalk のマルチコア対応が待たれます。

(その2につづく)

Smalltalk-72で学ぶOOPの原点:まとめ

サンプルコード「じゃんけんゲーム」(@nrslibさんのSIMULA版を移植)の続き)

アドカレのかたちを借りて、アラン・ケイの“オブジェクト指向”というアイデアをもとに(非同期処理などいろいろ足りていないながらも──)比較的忠実に実装された1970年代の非常に古いSmalltalk-72でいろいろ遊んでみたわけですが、お楽しみ頂けましたでしょうか。

絵文字などが多用されているコードの見た目の時点でもうすでにかなりユニークなSmalltalk-72ですが、純粋に言語として見ても、今でも十分異端とされる我々の知るSmalltalk-80以降の現在に至る実装(例えばPharo)のそのまたさらに遥か斜め上を行く“メッセージング”の徹底具合とその実現方法に度肝を抜かれたかと思います。

今のSmalltalkを含めて、Smalltalk-76以降のSmalltalkがパフォーマンスを優先してそれを選択したが故に、現在主流のメッセージングのOOPLの実装は「メンバー関数を“メソッド”と呼び、その動的コール&風変わりな例外処理(メソッドがないときに発動)の組み合わせを“メッセージ”と称する」のが唯一の正解とされてしまいがちですが、実装のバリエーションはいろいろあってもっと試されるべきなんだよ!(「だったんだよ!」ではなく現在進行形なのも重要!)ということを少しでもお伝えできたならさいわいです。


以下、このシリーズを通じてSmalltalk-72で遊んで気がついたことをつらつらと。(順不同。逐次追加)

  • トークン列のパースをメッセージングに見立てたアイデアは斬新だが、今のSmalltalkのようにコンパイル言語にはしにくい(実行速度は稼ぎにくい)かも。
  • 文法を定義できるのは強力だが、コンテキストによってコードの意味が変わるのは読むときつらい(つーか、字面を追うだけでは無理)。
  • 動的にコードを読む(実行時の動きを追う)にしても、今のSmalltalkのような強力なデバッガーが無いのがつらい(モードレスエディタ同様に発明前なので当然だが──)。そもそも、現在のOOPLに至ってもなおこれ無しに動的言語のコーディングや既存コードの解析をしている人を尊敬する!
  • このSmalltalk-72に影響を受けたカール・ヒューイットのアクターの実装(PLASMA)がどうなっていたか調べてみたい。Erlang/Elixirのメッセージングの実装がそれにどの程度影響を受けたものか確かめたい。
  • いろいろ工夫はできるが継承がないのはやっぱりつらい。継承にするかはともかく、コード(あるいはコード片)をオブジェクト間で共有する何らかの機構は(ユーザーサイドのノウハウの蓄積に頼るのではなく──)処理系サイドで用意していただきたい!
  • このあと発明されたコピペを含むモードレスエディタは偉大!(LivelyWebをもうちょっと勉強すればペースト機能くらいは追加できるかも…)
  • 知らないメッセージが来ると、冒頭のトークンをアクティベートして新しいコンテキストで処理が始まるのは斬新。
  • ただ、今のSmalltalkのようにオブジェクトにメッセージを送る(正味は動的な関数コールなのはさておき──)とそれがトリガーになる感じのほうが好き。
  • なんかこう(今のSmalltalkにおいてオブジェクトがいつもそこにあって自律してるイメージではなく──)いちいち処理系がしゃしゃり出てくる感じ(?)がSmalltalk-72方式にはある。
  • あと、知らないメッセージを無視してしまうことになるので、フォールスルー処理でできることが限定される。これはよくない。→あ、これ、ピーク(鍵穴マーク)を使えばできるのか!
  • でも、ネットワークや細胞間での通信とのアナロジーからはスルーする方がよく合致する。ここらへんアラン・・ケイ的にどう考えているのか知りたい。
  • 記号は1文字でトークンになるところがミソであるが(Smalltalk-76も同じ。なお、-80以降の今のSmalltalkでは記号が続くとまとめてトークンになるので、<=>とか新しいメソッドを追加できる──)、「=<」「<=」の代わりに「≦」を用いる等で必然的に多くの記号が必要になり、ともするとコードの読み下しのしにくさ、またLivelyWeb版に関してはWebブラウザにキーアサインを奪われることでエミュレーターの制約につながってしまっている。
  • 代入(☞<変数名>←<値>)や(Smalltalk-80以降は別の方法で戻ったが──)条件分岐(<条件式>⇒(<非偽時処理>)<偽時処理>)も一貫して意味的にはちゃんとメッセージ式になっているのはさすが。
  • アクションやクラスが実質クロージャーなのがびっくり。
  • メソッドが独立した関数ではなく、巨大なIF式の中にネストされたひとつのパターンマッチのコード片に過ぎないのもびっくり。
  • アクションやクラスがアクティベートされる(トークン列からオブジェクトだと判断される)とすぐにコードが実行されてしまうのはわかりにくいし、第遺丘オブジェクトとして扱いにくい。
  • 処理系の細かな挙動を理解するにあたっては、Smalltalk-72のオリジナルの実装者であるダン・インガルス自身によるSqueak版Smalltalk-72の実装が(若干齟齬はあるものの──)非常に参考になる。ここでもやはり今のSmalltalkのデバッガーは必須のツールであった。