はじめに
フィボナッチで各種言語をベンチマークを見て、そのページに無いWebAssemblyでベンチマークを取ったらどうなるか試してみました。
あと、バイトコードや Lisp の話も少々。
WebAssembly 版
早速、WebAssembly 版のコードを掲載します。
コードはテキスト形式(.wat)をThe WebAssembly Binary Toolkitを使ってバイナリ形式(.wasm)にコンパイルします。(詳細は検索すると色々出てくるので、そちらを参照してください)
これが最善の書き方か全然分かりません…。少なくともちゃんと動いています。
ちなみに、.watは S 式と呼ばれる、Lisp 好きにはたまらない見栄えをしています。
Lisper であれば「読める、読めるぞ！」と言いたくなる事でしょう(笑)。
(module
(func $fib (param $n i32) (result i32)
(if (i32.lt_s (get_local $n) (i32.const 2))
(then (return (get_local $n)))
(else (return (i32.add (call $fib (i32.sub (get_local $n) (i32.const 1)))
(call $fib (i32.sub (get_local $n) (i32.const 2)))))))
unreachable)
(export "fib" (func $fib)))
コンパイル後のfib.wasmを再度fib.watに戻して(逆アセンブルして)みます。
(module
(type (;0;) (func (param i32) (result i32)))
(func (;0;) (type 0) (param i32) (result i32)
get_local 0
i32.const 2
i32.lt_s
if ;; label = @1
get_local 0
return
else
get_local 0
i32.const 1
i32.sub
call 0
get_local 0
i32.const 2
i32.sub
call 0
i32.add
return
end
unreachable)
(export "fib" (func 0)))
.watは S 式を書く事が出来ますが、普通(?)のスタックマシーンのバイトコードっぽい形式でも書く事が出来ます。(正式に何と言うのでしょうか…)
.wasmを逆アセンブルするとこの形式で出力されます。
これを以下の HTML ファイルを使用して実行します。
ついでに JavaScript 版も実行してます。
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>WebAssembly Sample</title>
<script>
// WebAssembly 版
function fetchAndInstantiate(url, importObject) {
return fetch(url)
.then(response => response.arrayBuffer())
.then(bytes => WebAssembly.instantiate(bytes, importObject))
.then(results => results.instance);
}
fetchAndInstantiate("fib.wasm")
.then(instance => {
const start = performance.now();
console.log(instance.exports.fib(38));
console.log("WebAssembly", (performance.now() - start) / 1000);
});
// JavaScript 版
function fib(n) {
return n < 2 ? n : fib(n - 2) + fib(n - 1);
}
const start = performance.now();
console.log(fib(38));
console.log("JavaScript", (performance.now() - start) / 1000);
</script>
</head>
<body>
</body>
</html>
これを Windows10 の Firefox Developer Edition (63)を使用して実行すると以下の出力が得られました。
39088169
JavaScript 0.343
39088169
WebAssembly 0.679
実行時間が0.679秒となりました。
比較の為に、C Java Emacs Lisp Python での実行結果を載せておきます。
実行環境は全て Windows Subsystem for Linux 版 Ubuntu 18.04 です。
C 版
#include <stdio.h>
int fib(int n)
{
return n < 2 ? n : fib(n - 2) + fib(n - 1);
}
int main()
{
printf("%d\n", fib(38));
return 0;
}
$ gcc -O2 fib.c
$ time ./a.out
39088169
real 0m0.114s
user 0m0.125s
sys 0m0.000s
Java 版
public class fib {
static int fib(int n) {
return n < 2 ? n : fib(n - 2) + fib(n - 1);
}
public static void main(String[] args) {
System.out.println(fib(38));
}
}
$ javac fib.java
$ time java fib
39088169
real 0m0.228s
user 0m0.203s
sys 0m0.047s
Emacs Lisp 版
;;; -*- lexical-binding: t; -*-
(defun fib (n)
(if (< n 2)
n
(+ (fib (- n 2))
(fib (1- n)))))
(print (fib 38))
$ emacs -Q --batch -f batch-byte-compile fib.el
$ time emacs -Q --batch -l fib.elc
39088169
real 0m6.972s
user 0m6.922s
sys 0m0.047s
Python 版
def fib(n):
return n if n < 2 else fib(n - 2) + fib(n - 1)
print(fib(38))
$ time python3 fib.py
39088169
real 0m10.133s
user 0m10.109s
sys 0m0.031s
表にまとめたものが以下です。
| 言語 | 実行時間(秒) |
|---|---|
| C | 0.114 |
| Java | 0.228 |
| JavaScript | 0.343 |
| WebAssembly | 0.679 |
| Emacs Lisp | 6.972 |
| Python | 10.133 |
実行速度考察
WebAssembly 版の実行速度を期待してましたが、まだまだという所でしょうか？
JavaScript は動的型なのにこの速度は凄すぎる…。
Emacs Lisp と Python を載せたのは、単に自分が Emacs が好きだからです(笑)。
Emacs Lisp は意外と速くて、色々なベンチマークを実行しても同じように Python より少し速いという傾向になります。
Python がそもそもあまり速くないというのもありますが…。
バイトコード考察
実はこれが一番言いたかった事ですが、ひとまず Java 版のバイトコードを逆アセンブルしてみます。
Compiled from "fib.java"
public class fib {
public fib();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
static int fib(int);
Code:
0: iload_0
1: iconst_2
2: if_icmpge 7
5: iload_0
6: ireturn
7: iload_0
8: iconst_2
9: isub
10: invokestatic #2 // Method fib:(I)I
13: iload_0
14: iconst_1
15: isub
16: invokestatic #2 // Method fib:(I)I
19: iadd
20: ireturn
public static void main(java.lang.String[]);
Code:
0: getstatic #3 // Field java/lang/System.out:Ljava/io/PrintStream;
3: bipush 38
5: invokestatic #2 // Method fib:(I)I
8: invokevirtual #4 // Method java/io/PrintStream.println:(I)V
11: return
}
これと、前の方で掲載したfib.wasm.watのものと比べてみてください。
fibのバイトコードが、実はほとんど一致しています！
単純なコードとは言え、S 式から Java とほぼ同じバイトコードが出力されたのは感慨深いです。
これは静的型の Lisp を手に入れたと言っても過言ではありません！
…というのは言い過ぎですが、直接書くのはしんどい.watを書き易くする薄いラッパーの Lisp を作りたくなる動機付けには十分でしょう。
ちなみに、Emacs Lisp のバイトコードは以下のようになります。
byte code for fib:
doc: ...
args: (arg1)
0 dup
1 constant 2
2 lss
3 goto-if-nil 1
6 return
7:1 constant fib
8 stack-ref 1
9 constant 2
10 diff
11 call 1
12 constant fib
13 stack-ref 2
14 sub1
15 call 1
16 plus
17 return
1-に対応するsub1というオプコードがあったり(普通の引き算はdiff)、fibが名前(シンボル)のまま残ってたりしてますね。しかし、全体的に悪いコードではないように見えます。
Emacs は将来的には JIT コンパイラが搭載されるようですが、これがどの程度速くなるのかが楽しみです。
しかし、fibがシンボルのまま残っているので、毎回シンボルから関数を辿る必要があり、これがかなり遅いので、JIT の効果も限定的でしょう。(それでも 3 倍ぐらい速くなるようですが)
ちなみに、Emacs バイトコード完全解説の記事を近々アップ予定です。
中々マニアックな視点の記事になったと思います(笑)。
以上です。