この記事はなに？

「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のバージョン上げてくれ頼む・・・！！