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

#はじめに

[フィボナッチで各種言語をベンチマーク](http://d.hatena.ne.jp/satosystems/20121228/1356655565)を見て、そのページに無い**WebAssembly**でベンチマークを取ったらどうなるか試してみました。
あと、バイトコードや Lisp の話も少々。

#WebAssembly 版
早速、WebAssembly 版のコードを掲載します。
コードはテキスト形式(`.wat`)を[The WebAssembly Binary Toolkit](https://github.com/WebAssembly/wabt)を使ってバイナリ形式(`.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 版も実行してます。

```html: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 版
```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;
}
```

```shell
$ gcc -O2 fib.c
$ time ./a.out
39088169

real    0m0.114s
user    0m0.125s
sys     0m0.000s
```

#Java 版

```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));
    }
}
```

```shell
$ javac fib.java
$ time java fib
39088169

real    0m0.228s
user    0m0.203s
sys     0m0.047s
```

#Emacs Lisp 版

```emacs-lisp:fib.el
;;; -*- lexical-binding: t; -*-

(defun fib (n)
  (if (< n 2)
      n
    (+ (fib (- n 2))
       (fib (1- n)))))

(print (fib 38))
```

```shell
$ 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 版

```python:fib.py
def fib(n):
    return n if n < 2 else fib(n - 2) + fib(n - 1)

print(fib(38))
```

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

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