Goで真面目にコレクション操作ライブラリを作ってみた

はじめに

この記事はGo Advent Calendar 2016 の7日目の記事です。

アローラ！azihsoynです。会社でQiita Teamを使ってますがQiitaの方に投稿するのは初だったりします。

今回はgoでコレクション操作をするライブラリ gollectionを作ったのでGoでライブラリを公開までの流れとTipsなどを交えて紹介しようと思います。

gollectionとは

こういうことができるようになるライブラリです

func main() {
	arr := []int{1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10}
	res, _ := gollection.New(arr).
		Distinct().
		Filter(func(v int) bool {
			return v%2 == 0
		}).
		SortBy(func(v1, v2 int) bool {
			return v1 > v2
		}).
		Map(func(v int) string {
			return fmt.Sprintf("No:%d", v)
		}).
		Result()
	fmt.Println("origin : ", arr)
	fmt.Println("ret    : ", res)
}

origin :  [1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10]
ret    :  [No:10 No:8 No:6 No:4 No:2]

作った経緯

Goのsortインターフェースが新しくなったのは記憶に新しいと思います。

http://mattn.kaoriya.net/software/lang/go/20161004092237.html
https://github.com/golang/go/issues/16721

この変更はgo1.8でリリースされる模様です。

さてこのsortの実装ですが、reflectとinterfaceによって実現されています

func Slice(slice interface{}, less func(i, j int) bool) {
	rv := reflect.ValueOf(slice)
	swap := reflect.Swapper(slice)
	length := rv.Len()
	quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
}

reflectやinterfaceはパフォーマンスや可読性の面で避けられがちですが、これ以外にも公式のパッケージでは普通に使われています。

それならreflectやinterfaceをごりごり使ったライブラリも問題ないんじゃね？と思ったのが始まりでした。

また、もともとgoでコレクション操作したいことがまれによくあったので作ってみた感じです。

実装方針

以下のような方針で作りました。

• 使いやすく
• ちゃんとテスト書く
• ドキュメントも書く
• なるべく速く

試験的に実装して満足ではなく、ちゃんとライブラリとして公開しようと決めてました。

使いやすく

インターフェース

インターフェースはkotlinのコレクション操作を参考にしました。

こちらはとても良くまとまってるので参考にしてました。

深い意味はなくなんとなくkotlinが好きなだけです。他の言語でも大体同じ感じだと思います。

初期実装ではFilterなんかの場合引数が interface{} になっていました。

これは使うときに

res, _ := gollection.New(arr).Filter(func(v interface{}) bool {
	return v.(int) > 5 // func内で型アサーションが必要
}).Result()

とassertが必要になってしまい、微妙に使い勝手が悪くなってました。

またinterface{}が引数だと

res, _ := gollection.New(arr).Reduce(func(v1, v2 interface{}) interface{} { // 書くのがだるい...
	return v1.(int) + v2.(int)
}).Result()

スペルのせいでReduceに渡す関数がめっちゃ横に伸びてしまってました。

今はこうやって使えます。

res, _ := gollection.New(arr).Reduce(func(v1, v2 int) int {
	return v1 + v2
}).Result()

すっきり！

これはfunc部分をまるごとinterface{}として受け取ることで実現しています。

func (g *gollection) Reduce(f /* func(v1, v2 <T>) <T> */ interface{}) *gollection {
	// 省略
}

(ただパフォーマンスは修正前のほうがいいはずです)

また、レスポンスはどうしてもinterface{}にせざるを得ないのでassertが必要なんですが、errと二値を返す方式だとワンライナーで書けないのでResultAsを追加しました。

	arr := []int{0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9}
	ret := []int{}
	err := gollection.New(arr).Distinct().ResultAs(&ret)

便利！

元のスライスをいじらない

kotlinのコレクション操作がreadonlyということと、一度グローバルなスライスをソートしてしまってハマったのでこうしました。

ライブラリのバージョン管理

gopkg.in経由で取得できるようにします。

go get gopkg.in/azihsoyn/gollection.v1

これはgithubにvX.Y.Z形式でタグやブランチを作成すれば勝手に取得できるようになります。

ちゃんとテスト書く

カバレッジはほぼ100%を保つようにしてます

ほぼというのはgoroutineを使ってる関係上どうやっても100%にするのが難しいからです。

default:
    continue ← ここ

テストのライブラリはtestify/assert使ってます。

ドキュメントも書く

上記の検索フォームにgithubのリンクを入れるとgodoc上に生成されます。

ここで幾つかハマりました

• Exampleをgodocに反映させるのにExampleXXXX形式ではなくExample_xXXXでテストを書かないといけない

  例)

  func Example_distinct() {
  	// これはOK
  }
  
  func ExampleDistinct() {
  	// これはNG
  }
  

• exportされてないtypeがレシーバーのメソッド(本ライブラリの*gollectionみたいな)だとgodocに反映されない

  // Distinct ここにコメント書いてもgodoc上に反映されません
  func (g *gollection) Distinct() *gollection{
  }
  
  // Distinct exportされていればgodoc上に反映されます
  func (g *Gollection) Distinct() *Gollection{
  }
  

  v2作るときは気をつけたいと思います。。。

なるべく早く

本ライブラリではベンチマークを公開しています。

go test -bench <regexp> -bencmem

$ go test -bench . -benchmem
BenchmarkNew-8                            	20000000	        99.5 ns/op	      96 B/op	       2 allocs/op
BenchmarkDistinct-8                       	  300000	      4267 ns/op	    1155 B/op	      36 allocs/op
BenchmarkDistinct_WithoutGollection-8     	 1000000	      1211 ns/op	     339 B/op	       2 allocs/op
BenchmarkDistinctBy-8                     	  200000	      9064 ns/op	    1955 B/op	      56 allocs/op
BenchmarkDistinctBy_WithoutGollection-8   	 1000000	      1267 ns/op	     339 B/op	       2 allocs/op
BenchmarkFilter-8                         	  200000	      7145 ns/op	    1568 B/op	      53 allocs/op
BenchmarkFilter_WithoutGollection-8       	20000000	        84.8 ns/op	     160 B/op	       1 allocs/op
BenchmarkFlatMap-8                        	  200000	      8498 ns/op	    2256 B/op	      71 allocs/op
BenchmarkFlatMap_WithoutGollection-8      	 5000000	       240 ns/op	     368 B/op	       4 allocs/op
BenchmarkFlatten-8                        	  500000	      2990 ns/op	    1296 B/op	      31 allocs/op
BenchmarkFlatten_WithoutGollection-8      	10000000	       232 ns/op	     368 B/op	       4 allocs/op
BenchmarkFold-8                           	  200000	      6847 ns/op	    1448 B/op	      44 allocs/op
BenchmarkFold_WithoutGollection-8         	100000000	        10.8 ns/op	       0 B/op	       0 allocs/op
BenchmarkMap-8                            	  200000	      7645 ns/op	    1952 B/op	      65 allocs/op
BenchmarkMap_WithoutGollection-8          	20000000	        83.7 ns/op	     160 B/op	       1 allocs/op
BenchmarkReduce-8                         	  200000	      7254 ns/op	    1384 B/op	      42 allocs/op
BenchmarkReduce_WithoutGollection-8       	100000000	        14.6 ns/op	       0 B/op	       0 allocs/op
BenchmarkSort-8                           	  100000	     22518 ns/op	    4336 B/op	     129 allocs/op
BenchmarkSort_WithoutGollection-8         	 3000000	       437 ns/op	      32 B/op	       1 allocs/op
BenchmarkTake-8                           	 3000000	       600 ns/op	     448 B/op	       8 allocs/op
BenchmarkTake_WithoutGollection-8         	 5000000	       229 ns/op	     160 B/op	       1 allocs/op

軒並み遅いですね。。。やはりreflectが遅いというのは間違いなかったです。

素のfor文で書いたのと比べると早くても50% 遅いのだと1%とかになってます。

reflectのCallを使う処理が特に遅いですね。

それでも少しでも早くしようと工夫した点を幾つか紹介したいと思います。

sync.Poolで中間の配列を使いまわす

uberのzapというログライブラリ uber-go/zap でも使われているテクニックです

これをやるために中間配列を[]interface{}で持ち回すように修正しようとしてます(途中のPR)

interfaceのmap

これは意外だったのですが

m := make(map[interface{}]true)

よりも

m := reflect.MakeMap(<reflect.Type>, <reflect.Type>)

の方が速いです。(もちろん非interfaceの方が速いです)

検証コード(gist)

$ go test -bench BenchmarkSet . -benchmem -v
BenchmarkSetIntMap-4         	 5000000	       324 ns/op	      44 B/op	       0 allocs/op
BenchmarkSetInterfaceMap-4   	 2000000	       747 ns/op	      97 B/op	       1 allocs/op
BenchmarkSetReflectMap-4     	 3000000	       444 ns/op	      46 B/op	       1 allocs/op

streamに対応する

コレクションをメソッドチェーンで単純に実装すると、書くメソッド毎に最大n(最初の要素数)回ループが走ります。

これをgoのgoroutine/channel使ったら早くなるのではと思ってstreamでも使えるようにしてあります。

NewをNewStreamに変えるだけです(これも使いやすさを考慮して)

	arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println("start  :", time.Now())
	res, _ := gollection.NewStream(arr).Filter(func(v int) bool {
		time.Sleep(1 * time.Second)
		fmt.Println("process 1st filter")
		return true
	}).Filter(func(v int) bool {
		time.Sleep(1 * time.Second)
		fmt.Println("process 2st filter")
		return true
	}).Result()
	fmt.Println("origin : ", arr)

何もFilterしない処理を2つ書いています。

非streamだと10 * 1s * 2で20秒ほどかかりますが、stream版だと10秒ぐらいで終わります。

このstreamのベンチ結果は以下の通りです。

$ go test -bench . -benchmem
BenchmarkNewStream-8                      	  200000	     10247 ns/op	     289 B/op	       8 allocs/op
BenchmarkDistinct_Stream-8                	    5000	    265562 ns/op	    1717 B/op	      49 allocs/op
BenchmarkDistinctBy_Stream-8              	    5000	    296762 ns/op	    2678 B/op	      89 allocs/op
BenchmarkFilter_Stream-8                  	   10000	    157181 ns/op	    1952 B/op	      83 allocs/op
BenchmarkFlatMap_Stream-8                 	   10000	    144181 ns/op	    2656 B/op	      80 allocs/op
BenchmarkFlatten_Stream-8                 	   10000	    121338 ns/op	    1856 B/op	      60 allocs/op
BenchmarkFold_Stream-8                    	   10000	    100037 ns/op	    1744 B/op	      68 allocs/op
BenchmarkMap_Stream-8                     	   10000	    135785 ns/op	    2720 B/op	      97 allocs/op
BenchmarkReduce_Stream-8                  	   10000	    113624 ns/op	    1680 B/op	      65 allocs/op
BenchmarkSort_Stream-8                    	    5000	    222876 ns/op	    7136 B/op	     232 allocs/op
BenchmarkTake_Stream-8                    	   50000	     34518 ns/op	    1221 B/op	      24 allocs/op

遅い、、、非stream版より遅い、、、

ベンチの書き方のせいかもしれませんが、

• goroutineの生成コスト
• channelへの送信コスト
• channelの生成コスト
• 並列化によるリソース消費

などがあるのかなと思ってます。

作ってみて分かったこと

• reflectはやっぱり遅い(けど要件次第で十分使える)

• 実際作ってみて業務のプロダクト(APIサーバー)に適用してみたのですが(リリースはしてません)、思ったよりコレクション操作したくなるところがありませんでした

• コレクション操作はlambda式で書けないと不便(というかめんどくさい)

  _, _ := gollection.New(arr).FilterBy(v -> v != 2).Result()
  

こんな感じで書けたらいいですね。

終わりに

• reflectやinterfaceは適切に使えばものすごく便利
• ベンチマーク大事
• Goでライブラリ公開するの簡単

よいGoライフを！

---

本記事を書きながら去年のAdvent Calendarを眺めてたら関連してそうな記事がありました。

lazyなGoやリスト演算なGoについて

https://github.com/robpike/filter なんてライブラリがあったんですね...