モンテカルロ法（Javascriptでの処理高速化）

■今回はJavascript。
Pythonと同様にJavascriptでの高速化について検討してみたい。Pythonのときは、Numpyによるベクトル化（乱数の一括生成）、NumbaによるJIT化、Sobolによる準乱数（より軽い方法での乱数生成）を試した。

ChatGPTで、Javascriptでこれらに相当するものがないか聞いたところ、Numpyに対応するようなライブラリなどは無く、NumbaについてはJavascriptでは既にJIT相当になっているそう。乱数生成については、xorshift32という方法？で作るものが紹介された。あまり改善できる提案もなく既にそれなりに速いのではないかと思う。これなら一番初めに試した結果でJavascriptの方が速かったのも納得できる。
あとはPythonで試さなかったけど、並列処理も使ってみる。

まず、xorshift32の話。
今まで使ってきたMath.randomのコードが下。performance.nowで時間計測している。

const t0 = performance.now();

    for (let i = 0; i < STEP && totalCount < N_MAX; i++)
    {
      const x = Math.random() * 2 - 1;
      const y = Math.random() * 2 - 1;
      totalCount++;
      if (x * x + y * y <= 1) insideCount++;
    }

const t1 = performance.now();

今回のxorshift32のコード。xorshift32という関数へ参照させる。

function xorshift32(seed) {
  let x = seed | 0;
  return function () {
    x ^= x << 13;
    x ^= x >>> 17;
    x ^= x << 5;
    return (x >>> 0) / 4294967296;
  };
}

const t0 = performance.now();

    let seed = (Math.random() * 0xffffffff) | 0
    const rand = xorshift32(seed);

    for (let i = 0; i < STEP && totalCount < N_MAX; i++) {
      const x = rand() * 2 - 1;
      const y = rand() * 2 - 1;
      totalCount++;
      if (x * x + y * y <= 1) insideCount++;
    }

const t1 = performance.now();

次に、並列処理の話。下のようなWorkerのjsファイルを作成して、そちらで処理をさせる。時間計測は同じコードの部分をはさむ。

self.onmessage = (e) => {
  const { STEP, N_MAX } = e.data;

  let inside = 0;
  let total = 0;

  const t0 = performance.now();

  for (let i = 0; i < STEP && total < N_MAX; i++) {
    const x = Math.random() * 2 - 1;
    const y = Math.random() * 2 - 1;
    total++;
    inside += (x * x + y * y <= 1) | 0;
  }

  const t1 = performance.now();

  self.postMessage({
    insideDelta: inside,
    totalDelta: total,
    mcTime: (t1 - t0) / 1000
  });
};

実行結果が次。STEPが40000、N_MAXが1.2憶で処理時間を計測した。
WorkerとNon（Workerを使わないもの）。MathがMath.random, Xorがxorshift32。単位は秒(s)。

試行	Math, Non	Math, Worker	Xor, Non	Xor, Worker
1	6.88s	7.60s	19.93s	21.01s
2	7.33s	7.16s	17.77s	21.15s
3	8.08s	7.29s	20.22s	20.82s
4	7.26s	7.19s	18.61s	20.70s
5	7.96s	6.46s	20.58s	20.28s

プログラムの始めから終わりでも時間を計測したが、いずれも50秒ほどだった。xorshift32の方が演算に時間がかかっているはずなので、その分遅くなりそうだが。xorshift32の方法は、WebAssemblyを使ってC言語などで実行すれば早くなるそう。今回のようにjavascript内で実行するとむしろ遅くなった。
Workerを使う使わないは処理速度に影響はないとのことで、今回の結果とも整合する（Math, Xorでそれぞれ同じくらい）。

Workerを複数用意して並列処理を行うと上記の演算部分の累積時間は23.62秒、プログラムの始めから終わりまでは6.56秒となった。それぞれのWorker内での演算時間を加算するので8つのWorkerで並列処理したら、1つのWorker処理時間×8とかになる。グラフが更新されるさまを見る限り明らかに速く処理されている。

描画時間の高速化についても少し見てみたが、差分のみの描写にするなど改善していけばReactでの処理時間と同じくらい速くすることもできそう。今回でモンテカルロ法についてはきりにする。