Emacs
emacs-lisp
WebAssembly

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

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