WebAssemblyでマンデルブロ集合を計算してみた

# はじめに
この記事では個人的に興味があるWebAssemblyを試してみた感想を書こうと思う。
なぜWebAssemblyに興味があるかというと、もしWebAssemblyが広く使われるようになればwasmファイルを生成するソースを記述する言語として第一級の地位を占めるRustも自然と広く使われるようになるはずだからである。
Rustの本を読むと「RustはStack Overflowの調査で○年連続で開発者から最も愛されている言語に選ばれています！(ドヤ顔)」という記述をよく見るが、日本ではRustの求人を見ることは少ない。なので、Rustを業務で使ってみたい自分としてはWebAssemblyに頑張ってもらいたいという浅はかな願望を持っている。

今回はRustでマンデルブロ集合を計算するプログラムをつくり、それをWebAssemblyに変換してブラウザ上で走らせ、パフォーマンスを計測してみた。


# WebAssemblyとは
WebAssemblyとは仮想スタックマシンに対するアセンブリ言語のことである。普通、プログラム言語というのは特定のハードウェア向けの実行ファイルに変換されるが、WebAssemblyの場合はRustやC/C++で書いたソースをWebAssemblyに変換して、実行時に特定のチップの命令に変換される。この「ソース→中間表現→ネイティブコード」という図式はJavaと似ている。
WebAssemblyは仮想スタックマシンに対するアセンブリ言語なので持っている命令はスタックに値をpopしたりpushしたり、スタックに載っている上２つの値を取り出して和を取って結果をpushしたり(add)といったものである。

## なぜWebAssemblyを使うのか
ブラウザ上で走る言語としてJavaScriptが覇権を握っているのは皆様ご承知おきの通りだろう。多大なる最適化への努力によりJavaScriptは動的型付け言語とは思えないパフォーマンスを達成しているが、それでも言語の特性からC/C++、Rustといった言語と同等の性能を出すまでは至っていない。大体のことはJavaScriptで事足りるが、低レベルのネットワークたコーデックなどJavaScriptの性能では厳しいユースケースも一部存在する。そのようなユースケースに対応するためNaClやasm.jsなどが生まれたが、どれも欠点があったらしい。これらの技術のいいとこ取りをしたのがWebAssemblyだ(ノーエビデンス)。WebAssemblyは高パフォーマンスでサンドボックス化されていて、ポータブルなコードであることを目指している。

# マンデルブロ集合とは
[Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%87%E3%83%AB%E3%83%96%E3%83%AD%E9%9B%86%E5%90%88)によると
次の漸化式

```math
z_{n+1} = x_n^2 + c
```
```math
z_0 = 0
```
で定義される複素数列$\lbrace z_n \rbrace_{n \in N \cup \lbrace 0\rbrace }$が$n \rightarrow \infty$ の極限で無限大に発散しないという条件を満たす複素数$c$全体が作る集合がマンデルブロ集合らしい。

私は数学の素養が**ZERO**なので、どこからこの漸化式が出てきたが皆目検討がつかないのだが、生成される図形が神秘的で気に入っている。

プログラムはこの[本](https://www.oreilly.com/library/view/programming-rust-2nd/9781492052586/)に載っていた実装をベースにした。
プログラムでこの漸化式を無限に計算するわけには行かないのである回数で打ち切っている。また無限の解像度をもった画像を計算するわけにも行かないので、解像度と画像左上の複素数と画像右下の複素数を指定し、各ピクセルを複素数に変換して計算するようにしている。

# 実験結果
私は以下の三種類の形式でコードを走らせ、実行時間を計測してみた。ちなみにRustによるWebAssemblyの生成はこの[記事](https://rustwasm.github.io/docs/book/)を参考にした。[wasm-pack](https://github.com/rustwasm/wasm-pack)というツールを使うとRustから生成したwasmファイルをJavaScript上から簡単に呼び出すことができ、非常に便利だった。

1. Rustで普通に走らせる
1. wasmに変換してブラウザで実行
1. wasmに変換して走らせてcanvasを使ってブラウザに結果を描画する。

ちなみに実行環境としてはcore i5-10210U メモリ16GB Google Chromeバージョン: 96.0.4664.45（Official Build） （64 ビット）である。
生成したマンデルブロ集合の解像度は4000*3000、canvasの大きさは約8000*6000である。

| 種別 | 実行時間 |
|:-:|:-:|
| Rustで普通に走らせる  |  約0.3秒 |
|  wasmに変換してブラウザで実行 |  約6秒 |
|  canvasでブラウザに描画 |  約30秒 |

まずRustで普通に走らせるとPNG画像へのエンコードまで含めて約0.3秒だった。canvasで描画すると30秒くらいかかり、これはJavaScriptで8000*6000回のループを回して`fillRect()`を呼んでいるので仕方がないにしても、描画しなくても約6秒かかるというのは予想外だった。

これは

- 自分の書いたコードに致命的な欠陥がある
- 4000*3000バイトのメモリを共有するのはパフォーマンス上よろしくない
- wasmのネイティブコードへの変換はまだあんまり最適化されていない
- 実行以外の箇所で時間がかかっている

など理由はいろいろ考えられるが、真相は分からない。確かなのは現状素人が適当に書いても爆速で実行できるというわけには行かなそうということである。


# 終わりに
RustでWebAssemblyを使ってマンデルブロ集合をブラウザ上で計算してみたが、作成は簡単だった。一方で性能が全然出ず、WebAssemblyを自分のツールボックスに入れるには修行が必要だと感じた。
自分の好きな言語で簡単に安全で高パフォーマンスでポータブルなコードを生成できるという世界は魅力的なので、WebAssemblyのこれからに期待したい。

# 参考
参考としてコード片を載せておく

```rust:マンデルブロ集合計算
#[wasm_bindgen]
pub struct Mandelbrot {
    bounds: (usize, usize),
    pixels: Vec<u8>,
}

#[wasm_bindgen]
impl Mandelbrot {
    pub fn new() -> Self {
        Mandelbrot { 
            bounds: (4000, 3000),
            pixels: vec![0; 4000*3000],
        }
    }

    pub fn width(&self) -> usize {
        self.bounds.0
    }

    pub fn height(&self) -> usize {
        self.bounds.1
    }

    pub fn pixels(&self) -> *const u8 {
        self.pixels.as_ptr()
    }

    pub fn render(&mut self, upper_left_re: f64, upper_left_im: f64, lower_right_re: f64, lower_right_im: f64) {
        let _timer = Timer::new("Mandelbrot::render");
        let upper_left = Complex { re: upper_left_re, im: upper_left_im };
        let lower_right = Complex {re: lower_right_re, im: lower_right_im };
        self.render_inner(upper_left, lower_right);
    }
}

impl Mandelbrot {
    fn render_inner(
        &mut self,
        upper_left: Complex<f64>,
        lower_right: Complex<f64>,
    ) {
        assert!(self.pixels.len() == self.bounds.0 * self.bounds.1);

        for row in 0..self.bounds.1 {
            for column in 0..self.bounds.0 {
                let point = pixel_to_point(self.bounds, (column, row), upper_left, lower_right);
                self.pixels[row * self.bounds.0 + column] = match escape_time(point, 255) {
                    None => 0,
                    Some(count) => 255 - count as u8,
                };
            }
        }
    }
}

fn escape_time(c: Complex<f64>, limit: usize) -> Option<usize> {
    let mut z = Complex { re: 0.0, im: 0.0 };
    for i in 0..limit {
        if z.norm_sqr() > 4.0 {
            return Some(i);
        }
        z = z * z + c;
    }
    None
}

fn pixel_to_point(
    bounds: (usize, usize),
    pixel: (usize, usize),
    upper_left: Complex<f64>,
    lower_right: Complex<f64>,
) -> Complex<f64> {
    let (width, height) = (
        lower_right.re - upper_left.re,
        upper_left.im - lower_right.im,
    );

    Complex {
        re: upper_left.re + pixel.0 as f64 * width / bounds.0 as f64,
        im: upper_left.im - pixel.1 as f64 * height / bounds.1 as f64,
    }
}



pub struct Timer<'a> {
    name: &'a str,
}

impl<'a> Timer<'a> {
    pub fn new(name: &'a str) -> Timer<'a> {
        console::time_with_label(name);
        Timer { name }
    }
}

impl<'a> Drop for Timer<'a> {
    fn drop(&mut self) {
        console::time_end_with_label(self.name);
    }
}

```

```javascript:index.js
import { Mandelbrot } from "mandelbrot";
import { memory } from "mandelbrot/mandelbrot_bg";



const mandelbrot = Mandelbrot.new();
const width = mandelbrot.width();
const height = mandelbrot.height();

const CELL_SIZE = 1;
const DEAD_COLOR = "#FFFFFF";
const ALIVE_COLOR = "#000000";
const canvas = document.getElementById("mandelbrot");
canvas.height = (CELL_SIZE + 1) * height + 1;
canvas.width = (CELL_SIZE + 1) * width + 1;

const ctx = canvas.getContext('2d');

const getIndex = (row, column) => {
  return row * width + column;
};

const drawPixels = () => {
    const pixelsPtr = mandelbrot.pixels();
    const pixels = new Uint8Array(memory.buffer, pixelsPtr, width*height);

    ctx.beginPath();

    for (let row = 0; row < height; row++) {
        for (let col = 0; col < width; col++) {
            const idx = getIndex(row, col);

            ctx.fillStyle = pixels[idx] === 0 
        ? DEAD_COLOR
        : ALIVE_COLOR;

      ctx.fillRect(
        col * (CELL_SIZE + 1) + 1,
        row * (CELL_SIZE + 1) + 1,
        CELL_SIZE,
        CELL_SIZE
      );
    }
  }

  ctx.stroke();

}

const renderLoop = () => {
    mandelbrot.render(-1.20, 0.35, -1.0, 0.2);
    drawPixels();
    requestAnimationFrame(renderLoop)
}

drawPixels();
requestAnimationFrame(renderLoop);

```
# 参考文献
- https://rustwasm.github.io/docs/book/
- https://www.oreilly.com/library/view/webassembly-the-definitive/9781492089834/
- https://www.oreilly.com/library/view/programming-rust-2nd/9781492052586/