golang でクイックソートを並列化してみる

僕の中で今アツイ golang。
Googleが開発したプログラミング言語で、C言語を置き換える言語を目指しているらしいです。数多くの強力なライブラリを標準で備え、Cにあった様々な問題の解決を目指しているとか。
中でも僕が一番魅力に感じているのが、並列化機構を言語がネイティブで持っていること。外部のライブラリなどに頼らず、非常に簡単に並列処理を実現することが出来ます。
そういった機能がどれだけ強力なことなのか、検証やらの意味も込めて実験してみました。

今回 golang で書いたコードは以下になります。

＜コード＞

package main

import "fmt"
import "math/rand"
import "time"

func qsort(list []int) []int {
	if len(list) == 0 {
		return []int{}
	}
	x := list[0]
	xs := list[1:]
	smaller := make([]int, 0, len(list)-1)
	bigger := make([]int, 0, len(list)-1)
	for _, val := range xs {
		if val >= x {
			bigger = append(bigger, val)
		} else {
			smaller = append(smaller, val)
		}
	}
	smallch := make(chan []int)
	bigchan := make(chan []int)
	go sortchan(smaller, smallch)
	go sortchan(bigger, bigchan)
	smalllist := <-smallch
	biglist := <-bigchan
	return append(append(smalllist, x), biglist...)
}

func sortchan(list []int, ch chan []int) {
	sorted := qsort(list)
	ch <- sorted
}

func qsortNone(list []int) []int {
	if len(list) == 0 {
		return []int{}
	}
	x := list[0]
	xs := list[1:]
	smaller := make([]int, 0, len(list)-1)
	bigger := make([]int, 0, len(list)-1)
	for _, val := range xs {
		if val >= x {
			bigger = append(bigger, val)
		} else {
			smaller = append(smaller, val)
		}
	}
	smalllist := qsortNone(smaller)
	biglist := qsortNone(bigger)
	return append(append(smalllist, x), biglist...)
}

func main() {
	slist := make([]int, 200000)
	for i := range slist {
		slist[i] = rand.Intn(100000)
	}
	start := time.Now()
	_ = qsortNone(slist)
	end := time.Now().Sub(start).Nanoseconds()
	fmt.Println("並列化前: ", end, " ns")

	start = time.Now()
	_ = qsort(slist)
	end = time.Now().Sub(start).Nanoseconds()
	fmt.Println("並列化後: ", end, " ns")
}

＜説明＞

クイックソートのアルゴリズム解説はWikipediaでも読んでください。
go func() でfunc()をゴルーチンとして実行し、終了を待たずに次の行へ進むことが出来ます。これが並列化です。今回は配列の先頭の数字をピボットとし、再帰的にソートする処理を並列化することによって高速化を試みました。qsort(int)が並列化バージョン、qsortNone(int)が並列化なしバージョンの関数です。
0から99,999までの範囲の乱数が200,000個ランダムに入ったスライス slist に対してソートを実行し、それぞれの時間を計測しています。

＜実行結果＞

10回実行し、平均を取ります。

1.　並列化前: 117006700 ns
　　並列化後: 839048000 ns
2.　並列化前: 116006600 ns
　　並列化後: 776044400 ns
3.　並列化前: 115006500 ns
　　並列化後: 840048100 ns
4.　並列化前: 117006700 ns
　　並列化後: 768044000 ns
5.　並列化前: 114006500 ns
　　並列化後: 778044500 ns
6.　並列化前: 112006400 ns
　　並列化後: 764043700 ns
7.　並列化前: 111006400 ns
　　並列化後: 757043300 ns
8.　並列化前: 111006400 ns
　　並列化後: 752043000 ns
9.　並列化前: 111006400 ns
　　並列化後: 767043800 ns
10. 並列化前: 111006300 ns
　　並列化後: 764043700 ns

＜平均＞
　　並列化前: 113506490 ns
　　並列化後: 780544650 ns

以上のような結果となりました。並列化前が0.114秒、並列化後が0.781秒くらいですね。…………？？？

あれ……並列化した後のほうが遅い……。並列化の強力さって……？

＜考察＞

きっとスレッディングだから。
実際に並列に処理しているわけではなく、一定時間ごとに「次はこっちのスレッド、その次はこっちのスレッド……」みたいな感じで、他のスレッドを停止しながら１つずつ処理していっているからだと考えられます。ゴルーチンはCPUが同時に複数計算するのではなく、同時に見えるように計算しているだけなので、チャネルのロック待機時間やら関数呼び出しのオーバーヘッドやらなんやらで並列化バージョンのほうが余計に時間がかかってしまっているものと思われます。
コーディングが悪いわけではない……と信じたい。実装方法的に、スライスの要素数が1つになるまでスレッドが分かれてしまうので、そのせいで時間がかかっているのかもしれません。

＜まとめ＞

golang楽しい(錯乱)。
スレッディングはゲームプログラミングでめっちゃ使うので、ぶっちゃけ処理時間が向上しなくても普通に使い道はあるのです。
使いやすいゲーム用GUIライブラリがなさそうなので、しばらくはこういうことずっとやってる感じになるかもしれません。
go-sdlとかは出てます。(SDL触ったことないので敬遠してます。食わず嫌いとはまた違いますが、ﾁｮｯﾄｺﾜｲ)

前に言ってたこととやってることがぜんぜん違う……。すごいH本買ってからしばらく経ったはずなのに、まだ読み終わってないしhaskellの勉強も進んでいないので、もっと勉強します。

それではまた。次の更新がいつになることやら。

--- 2015/05/50 17:30 追記 ---

スレッドを分けすぎているのかもしれないと思って、ピボットよりも小さい配列と大きい配列それぞれについて、要素数が1000個以下の時はqsortNone()を適応してみました。結果、平均が0.126秒となり、場合によっては並列化前よりも高速に動作することもありました。
このことから、遅くなってしまったのは実装の問題だということがわかりました。あまりにスレッドを分けすぎた結果、チャネルのロックやらなんやらのせいで遅くなったものと思われます。
計算が並列に見えるだけとか適当な事書いてすみませんでした。