Edited at

WebAssembly のベンチマークとバイトコードと Lisp


はじめに

フィボナッチで各種言語をベンチマークを見て、そのページに無いWebAssemblyでベンチマークを取ったらどうなるか試してみました。

あと、バイトコードや Lisp の話も少々。


WebAssembly 版

早速、WebAssembly 版のコードを掲載します。

コードはテキスト形式(.wat)をThe WebAssembly Binary Toolkitを使ってバイナリ形式(.wasm)にコンパイルします。(詳細は検索すると色々出てくるので、そちらを参照してください)

これが最善の書き方か全然分かりません…。少なくともちゃんと動いています。

ちなみに、.watは S 式と呼ばれる、Lisp 好きにはたまらない見栄えをしています。

Lisper であれば「読める、読めるぞ!」と言いたくなる事でしょう(笑)。


fib.wat

(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に戻して(逆アセンブルして)みます。


fib.wasm.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 版も実行してます。


fib.html

<!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 版


fib.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 版


fib.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 版


fib.el

;;; -*- 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 版


fib.py

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 バイトコード完全解説の記事を近々アップ予定です。

中々マニアックな視点の記事になったと思います(笑)。

以上です。