この記事はなに？
「Turing Complete FM」面白いですよね。
この回を聞いていて、絶対値を求めるアルゴリズムの速度について気になったのでベンチマークテストをしてみました。
先に結果から
- 絶対値を取るアルゴリズムについて、少なくともGo1.11.2以降であればif文を使っても速度面でのデメリットはないよ
- 速度面でのデメリットがないので、可読性を考慮して普通にif文を使って書く方がおすすめだよ
- ただし、Atcoderで使用されているGo1.6については速度差が出るので、Atcoderで少しでも実行速度を上げたいならif文を使わずに実装した方がいいよ
- ベンチマークの実行結果はこちら
絶対値を求めるアルゴリズム
bit演算を使用してif文を使わないアルゴリズム(Turing Complete FMで紹介されていたもの)
const intSize = 32 << (^uint(0) >> 63)
func abs(x int) int {
m := x >> (intSize - 1)
return (x ^ m) - m
}
簡単に解説しておくと、1行目ではintSizeが32bitか64bitかを判定しています。（参考：TCFMのるいさんによるQiita記事）
m := x >> (intSize - 1)では、xの最上位ビットを最下位ビットまで右シフトしているので、xが負のときは1が連続するためにm := -1となり、xが非負のときはm := 0となります。
続く(x ^ m) - mの部分で、xが負のときは2の補数と同様の計算式となり、(x ^ -1) + 1となるので、xのbitを全部反転して1を足していることになります。xが非負のときは(x ^ 0) - 0 = xとなってxがそのままreturnされます。
詳しくはこちらを聞いてください。
if文とかけ算を使用するアルゴリズム
func ifAbs(x int) int {
if x < 0 {
return -1 * x
} else {
return x
}
}
if文のみ使用してかけ算を使わないアルゴリズム
func ifAbsAnd(x int) int {
if x < 0 {
return -1 ^ x + 1
} else {
return x
}
}
なぜわざわざかけ算をしないバージョンを用意しているのかというと、TCFM内でかけ算も遅くなりがちであるという話が出たためです。
こちらについても一緒にベンチマークを行ってみます。
ベンチマーク
ソースコード
ベンチマークソースコード（長いのでたたんでいます）
package test
import (
"testing"
)
const intSize = 32 << (^uint(0) >> 63)
const loop = 1000000
func abs(x int) int {
m := x >> (intSize - 1)
return (x ^ m) - m
}
func ifAbs(x int) int {
if x < 0 {
return -1 * x
} else {
return x
}
}
func ifAbsAnd(x int) int {
if x < 0 {
return -1 ^ x + 1
} else {
return x
}
}
func BenchmarkAbs(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < loop; j++ {
_ = abs(i)
}
}
}
func BenchmarkIfAbs(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < loop; j++ {
_ = ifAbs(i)
}
}
}
func BenchmarkIfAbsAnd(b *testing.B) {
b.ResetTimer()
for i := 0; i < b.N; i++ {
for j := 0; j < loop; j++ {
_ = ifAbsAnd(i)
}
}
}
ベンチマーク実行結果
それぞれ「MacOS Mojave10.14.5」でDocker Official Imagesを使用して実行しました。
結果は冒頭に記載した通り、Go1.11.2では実行速度差がほとんど出ず、Go1.6ではif文を使用しないアルゴリズムが倍程度早く実行されました。
Go1.11.2
root@21b57f8e170a:/go/benchmark/test# go test -bench .
goos: linux
goarch: amd64
BenchmarkAbs-4 5000 305530 ns/op
BenchmarkIfAbs-4 5000 301753 ns/op
BenchmarkIfAbsAnd-4 5000 306744 ns/op
Go1.6
root@5e04c8c946b5:/go/benchmark/test# go test -bench .
testing: warning: no tests to run
PASS
BenchmarkAbs-4 2000 605807 ns/op
BenchmarkIfAbs-4 1000 1188589 ns/op
BenchmarkIfAbsAnd-4 1000 1171685 ns/op
所感
- 同じソースコードで同じマシンで実行した結果にも関わらず、Go1.6とGo1.11.2では2倍から4倍ほど早くなっていたことが驚きだった
- レガシーなソースコードの速度改善をする場合、アルゴリズムとは別にGo自体のバージョンアップを行うことで速度が改善することもあるかも
- Atcoder、Goのバージョン上げてくれ頼む・・・！！