こんにちはフロントエンドエンジニアをしている ku6ryo です。
普段は VR のスタートアップにて JavaScript で SPA を開発しています。
WASM に興味をもち、 WASM x Go は本当に早いのかという疑問から速度検証をしてみたのですが、WASM に辿り着く前に Go が JavaScript (Node.js) よりも遅いケースがあるのを発見したので共有および、なぜこうなるのかわかる方がいらっしゃればご意見をいただきたく、本記事を投稿します。
結果
先に結果から。10^7 以下の最大の素数を求めたところ、JavaScript (Node.js) 約 1200 ms に対して Go は 約 2500 ms となった。Node.js は Go よりも約２倍も速い結果となった(10回施行のばらつきは 数% 以内なので Node.js は Go に対して優位な差があるとみなせると判断)。なお、実行環境は macOS Catalina / 2.3 GHz Dual-Core Intel Core i5 / 16 GB 2133 MHz LPDDR3 です。
コメントを頂いてからの改良
@c-yan さんから以下のコードにすると速くなるというコメントを頂き、変更すると約 950 ms で Go の実行できました。
if int32(i)%int32(p) == 0 {
int64 の mod (%) が遅いってことですね ... 今回は扱う数字が 10^7 < 2^31 - 1 でしたので int32 で十分でしたのでこれで問題なく改良できました。
ここから学んだ教訓としてはアルゴリズムが同じでも書き方によって Go > JavaScript とならないケースがあるということです。実務ではサーバーサイドに Go を用いようかと考えていたので DB 操作や、HTTP サーバーとしての実行時間も確認してみようと思います。
プログラムの内容
与えられた整数の引数 n に対してnを超えない最大の素数を導き出すプログラムを Go および JavaScript で書いた。両者に対して実行時間の計測を行った。両者ともに同じアルゴリズムで実装を行った。
解説
- 予め素数の表を持つことはせず、施行毎に素数を順次導き出していく方式をとった
- 計算量は i (3 <= i <= n) の平方根以下の素数の数の和
- 偶数は計算対象外とした
コード
JavaScript
/**
* @param {number} n >= 3
* @returns {number} Max prime number.
*/
const getMaxPrime = (n) => {
if (n < 3) {
throw new Error('n must be equal to or more than 3.')
}
let primes = [2]
for (let i = 3; i <= n; i += 2) {
const maxModCheck = Math.floor(Math.sqrt(i))
for (let j = 0; j < primes.length; j++) {
let p = primes[j]
if (i % p == 0) {
break;
}
if (p >= maxModCheck) {
primes.push(i)
break
}
}
}
return primes[primes.length - 1]
}
const startTime = (new Date()).getTime()
const maxPrime = getMaxPrime(10000000)
const endTime = (new Date()).getTime()
console.log(`Max Prime: ${maxPrime}`)
console.log(`Time: ${endTime - startTime}`)
Go
package main
import (
"fmt"
"errors"
"math"
"time"
)
/**
* @param n >= 3
* @returns Max prime number.
*/
func getMaxPrime(n int) (error, int) {
if (n < 3) {
return errors.New("n must be equal to or more than 3."), 0
}
primes := make([]int, n / 2)
primes[0] = 2
numPrimes := 1
for i := 3; i <= n; i += 2 {
maxModCheck := int(math.Sqrt(float64(i)))
for j := 0; j < numPrimes; j++ {
p := primes[j]
if i % p == 0 {
break;
}
if p >= maxModCheck {
primes[numPrimes] = i
numPrimes += 1
break
}
}
}
return nil, primes[numPrimes - 1]
}
func main() {
startTime := time.Now().UnixNano() / 1000000
err, maxPrime := getMaxPrime(10000000)
if err == nil {
fmt.Println("Max Prime: ", maxPrime)
endTime := time.Now().UnixNano() / 1000000
fmt.Println("Time: ", endTime - startTime)
} else {
fmt.Println(err)
return
}
}
WebAssembly
また、WebAssembly での Go (WASM) 実行とブラウザでの JavaScript の実行の比較をしたところ、さらに差は広がる結果となりました。Go (WASM) は約 6300 ms に対して JavaScript (Chrome) は約 1100 ms になりました。約 6 倍 JavaScript が速いという結果です。これは WASM なら速くなると盲目的に思っていた自分にとって衝撃でした。
最後に
流石になにかがおかしいと思ったので、Go と JavaScript で 1000000000 回 for ループを回すだけのコード書いたところ、Go のほうが２，３倍実行速度が速かったです。素数の導出のコードの問題なのかなんなのか謎であります。
後日追記
上記のコードで、Go の扱う整数値の型によって、速度が変わることを指摘いただいた。書き方によって必ずしも Go が速くなるわけではないことを学びました。
参考