Golangでベクトル演算を高速化しようとしてみた話

はじめに

Goでスライスのベクトル演算などを書いてたときに、今までは

for i := 0; i<len(slice); i++ {...}

のように素直にfor文で全要素にアクセスしてました。

もっと速い演算方法は無いかと考えていたところ、

for i := 0; i<cpus; i++ {
    go func{...}
}

のようにcpuコア数に合わせてsliceを分割し、goroutineで並行処理する方法を思いつきました。

ということで、実際に速度の検証をしてみました。

結論から言うと...

むしろ遅くなりました。

2019/11/01追記

要素数10万以上では、goroutineを使用したほうが速くなりました。（環境によります。）

検証コードはスライスに数字を代入しているだけなので、演算時間が逆転する要素数が多くなっています。 しかし、べき乗や平方根を求めるなどの重い処理をする場合、goroutineの旨みが増すことが予想できます。

以下は検証のコードなので、興味のある方は見て頂けると幸いです。

環境

• MacBook Pro 2019
• macOS Catalina
• 2.4 GHz Quad-Core Intel Core i5
• Go 1.13.1

検証

素直にfor文

func main() {
	n := 100000000
	is := make([]int, n)
	fmt.Println("==START==")

	start := time.Now()
	for i := 0; i < n; i++ {
		func(i int) { is[i] = i }(i)
	}
	end := time.Now()

	fmt.Println("==END==")
	fmt.Println(end.Sub(start))
}

$ go run main.go
==START==
==END==
309.95595ms

1億回で310msでした。

cpu数に合わせて並行処理

func main() {
	fmt.Printf("Number of cpus: %v\n", runtime.NumCPU())
	wg := &sync.WaitGroup{}
	cpus := runtime.NumCPU()
	n := 100000000
	is := make([]int, n)
	fmt.Println("==START==")

	start := time.Now()
	jMax := n / cpus
	for i := 0; i < cpus; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			/* 遅いコード
			   for j := 0; j < n/cpus; j++ {
			       is[i*n/cpus+j] = i*n/cpus + j
			   }
			*/
			offset := i * jMax
			for j := 0; j < jMax; j++ {
				is[offset+j] = offset + j
			}
		}(i)
	}
	wg.Wait()
	end := time.Now()

	fmt.Println("==END==")
	fmt.Println(end.Sub(start))
}

$ go run main.go
Number of cpus: 8
==START==
==END==
88.946429ms

1億回を8個のgoroutineで処理して、89msでした。
要素数が多い場合、goroutineを使用したほうがかなり速いです。

cgoで実行

/*
void vec(long *is, long n){
    for (int i=0; i<n; i++) {
        is[i] = i;
    }
}
*/
import "C"

func main() {
	fmt.Println("==START==")

	n := 100000000
	is := make([]int, n)

	start := time.Now()
	C.vec((*C.long)(unsafe.Pointer(&is[0])), (C.long)(n))
	end := time.Now()
	time.Sleep(time.Second)

	fmt.Println("==END==")
	fmt.Println(end.Sub(start))
}

$ go run main.go
==START==
==END==
271.969568ms

cgoはそこそこの結果に終わりました。

• メモリセーフでない
• コードが読みづらくなる

ことを考慮すると、よっぽどの理由がない限りgoroutineを使うのがよいと思います。

ちなみにpyhtonでも実行してみました。

import time
import numpy as np

print("==START==")
start = time.time()
iarr = np.arange(100000000)
duration = time.time() - start
print("==END==")

print(str(duration*1000) + "ms")

python main.py
==START==
==END==
304.9652576446533ms

書きやすさと速度を考えると、numpyは偉大ですね。

要素数を増減して検証

演算回数を1万回、10万回、100億回に変えて実行してみます。

演算回数	生go	goroutine	cgo
1万	0.035ms	0.087ms	0.038ms
10万	0.43ms	0.34ms	0.39ms
1億	309ms	89ms	272ms
100億	47s	38s	43s

演算回数10万回以上ではgoroutineが速くなりました。

cgoは演算回数が増えると生goよりも速くなりました。シングルコアの環境であれば、cgoを使うのも有効かもしれません。

おわりに

冒頭にも書きましたが、演算数が増えたり、内容が重くなったりするとgoroutineの効果が大きく出ると思います。

信号処理をgoで書いてるので、機会があればQiitaにも投稿しようと思います。