f:id:shogonir:20170514025514p:plain

1. この記事の目的

この記事ではソートの速度を、JSのみの場合とwasmを使った場合の比較を行います。
今回はあえてかなり遅めのアルゴリズムである挿入ソートを採用しました。
結果から言うとJSのみの方が早いという結果になってしまいました、あれ？

2. C++でソートを実装

C++でソートを実装します。配列の先頭ポインタと配列長を受け取ります。

extern "C"
{

void InsertSort(int * array, int length)
{
    int j, swap;
    for (int i=1; i<length; i++) {
        j = i - 1;
        while (j >= 0 && array[j] > array[j+1]) {
            swap = array[j];
            array[j] = array[j+1];
            array[j+1] = swap;
            --j;
        }
    }
}

}

3. JSでソートを実装

JSでも同様のソートを実装します。こちらはInt32Arrayのみ受け取ります。

function insertSortJS(int32Array) {
  var j, swap;
  for (var i=0; i<int32Array.length; i++) {
    j = i - 1;
    while(j >= 0 && int32Array[j] > int32Array[j+1]) {
      swap = int32Array[j];
      int32Array[j] = int32Array[j+1];
      int32Array[j+1] = swap;
      j--;
    }
  }
  console.log(int32Array);
}

4. 実行用のHTMLを準備する

実行用のHTMLを準備します。
まずはJSのInt32Arrayをwasmのソートに渡して実行する部分を準備します。

function insertSortWasm(int32Array) {
  var pointer = module._malloc(int32Array.length * 4); // 32bit=4bytes
  var offset = pointer / 4;
  module.HEAP32.set(int32Array, offset);
  functions.InsertSort(pointer, int32Array.length);
  console.log(module.HEAP32.subarray(offset, offset + int32Array.length));
  module._free(pointer);
}

JSのtyped arrayをwasmに渡す方法はこちらを参照して下さい。

次にソートするランダムな配列を準備する関数を準備します。

function randomArray(size) {
  var int32Array = new Int32Array(size);
  var i;
  for (i=0; i<size; i++) {
    int32Array[i] = i;
  }
  for (i=0; i<size; i++) {
    var rand1 = Math.floor(Math.random() * (size+1));
    var rand2 = Math.floor(Math.random() * (size+1));
    var swap = int32Array[rand1];
    int32Array[rand1] = int32Array[rand2];
    int32Array[rand2] = swap;
  }
  return int32Array;
}

[0, 1, 2, …, size] という配列を準備して、ランダムに要素を交換して混ぜて返します。

5. 実際に速度を比較する

速度を測定するのにconsole.time(string), console.timeEnd(string)を使います。
完全に同じランダムな配列を2つ準備し、それぞれのアルゴリズムでかかった時間を測定します。

function benchmark(size) {
  var randArray1 = randomArray(size);
  var randArray2 = new Int32Array(randArray1);

  console.time('js');
  insertSortJS(randArray1);
  console.timeEnd('js');

  console.time('wasm');
  insertSortWasm(randArray2);
  console.timeEnd('wasm');
}

最終的にHTML全体は下記のようになります。

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8"/>
    <title>sort benchmark</title>
  </head>
  <body>
    <script src="sort.js"></script>
    <script>

var module;
var functions = {};

function readFunctions() {
  functions.InsertSort = module.cwrap('InsertSort', null, ['number', 'number']);
}

function insertSortJS(int32Array) {
  var j, swap;
  for (var i=0; i<int32Array.length; i++) {
    j = i - 1;
    while(j >= 0 && int32Array[j] > int32Array[j+1]) {
      swap = int32Array[j];
      int32Array[j] = int32Array[j+1];
      int32Array[j+1] = swap;
      j--;
    }
  }
  console.log(int32Array);
}

function insertSortWasm(int32Array) {
  var pointer = module._malloc(int32Array.length * 4); // 32bit=4bytes
  var offset = pointer / 4;
  module.HEAP32.set(int32Array, offset);
  functions.InsertSort(pointer, int32Array.length);
  console.log(module.HEAP32.subarray(offset, offset + int32Array.length));
  module._free(pointer);
}

function randomArray(size) {
  var int32Array = new Int32Array(size);
  var i;
  for (i=0; i<size; i++) {
    int32Array[i] = i;
  }
  for (i=0; i<size; i++) {
    var rand1 = Math.floor(Math.random() * (size+1));
    var rand2 = Math.floor(Math.random() * (size+1));
    var swap = int32Array[rand1];
    int32Array[rand1] = int32Array[rand2];
    int32Array[rand2] = swap;
  }
  return int32Array;
}

function benchmark(size) {
  var randArray1 = randomArray(size);
  var randArray2 = new Int32Array(randArray1);

  console.time('js');
  insertSortJS(randArray1);
  console.timeEnd('js');

  console.time('wasm');
  insertSortWasm(randArray2);
  console.timeEnd('wasm');
}

fetch('sort.wasm')
  .then(response => response.arrayBuffer())
  .then(buffer => new Uint8Array(buffer))
  .then(binary => {
    var moduleArgs = {
      wasmBinary: binary,
      onRuntimeInitialized: function () {
        readFunctions();
        benchmark(10 * 1000);
      }
    };
    module = Module(moduleArgs);
  });

    </script>
  </body>
</html>

http-serverを実行して実際にコンソールを見ると下記のようになります。

f:id:shogonir:20170525005729p:plain

6. まとめ

今回はソートの速度をJSとwasmで比較しました。
出力を見るとJSの方が早いという結果になってしまいました。（あれ？）
おかしいなと思い、typed arrayをwasmに渡す部分を時間測定からはずしてみましたがJSの方が早かったです。
どうもwasmの実行を呼ぶためのオーバーヘッドで時間がかかっているのではと考えています。

shogonir blog

【WebAssembly】JSとwasmでソートの速度を比較する

目次