この記事はGo2 Advent Calendar 2018の17日目の記事です。
コレクション操作ライブラリ Koazee
12月はじめのこと、go-nutsに「速いコレクション操作ライブラリを作ったぜ」という投稿がありました。
彼のベンチマークによると類似のライブラリに比べてかなり速いという結果が示されています。ここでは彼が作ったコレクション操作ライブラリ Koazee を紹介しつつ、高速化の一端に触れてみます。
Lazy like a koala, smart like a chimpanzee (原文ママ)
Koazeeの特徴は
- イミュータブル
- ストリームスタイル
- 遅延ローディング
- ジェネリックス
- 速い！
とのことでここでは「ジェネリックス」と「速い！」という点を見ていきます。
ジェネリックス
Koazee を使うとストリームの操作をより自然な形で記述することができます。
まず、Koazee の使い方を見る前に、類似ライブラリの go-linq のサンプルを見てみます。
import . "github.com/ahmetb/go-linq"
type Car struct {
year int
owner, model string
}
...
var owners []string
From(cars).Where(func(c interface{}) bool {
return c.(Car).year >= 2015
}).Select(func(c interface{}) interface{} {
return c.(Car).owner
}).ToSlice(&owners)
WhereやSelectに渡される関数リテラルの中で、型アサーションしています。なんだか面倒くさい。go-linqにはWhereTやSelectTといった、関数リテラル自体をinterface{}で受けるものも用意されていますが、「オーバーヘッドがあるよ」と注意書きがされています。
一方、Koazeeのサンプルを見てみると
package main
import (
"fmt"
"github.com/wesovilabs/koazee"
)
var numbers = []int{1, 5, 4, 3, 2, 7, 1, 8, 2, 3}
func main() {
fmt.Printf("input: %v\n", numbers)
stream := koazee.StreamOf(numbers)
fmt.Print("stream.Reduce(sum): ")
fmt.Println(stream.Reduce(func(acc, val int) int {
return acc + val
}).Int())
}
/**
go run main.go
input: [1 5 4 3 2 7 1 8 2 3]
stream.Reduce(sum): 36
*/
型アサーションをしない形で書かれています。実際にReduceは関数リテラルをinterface{}で受け取っています。
go-linqでは遅くなるとされていた方式で、なぜKoazeeは速いのか？
速い！
本人の解説によると、「キャッシュをうまく使っている」とのこと。例として、Filterの実装にあるバリデーションを見てみると、
func (op *Filter) validate() (*filterInfo, *errors.Error) {
item := &filterInfo{}
fnType := reflect.TypeOf(op.Func)
if val := cache.get(op.ItemsType, fnType); val != nil {
return val, nil
//...... Validations for input
item.fnInputType = fnIn.Type()
cache.add(op.ItemsType, fnType, item)
return item, nil
}
cacheにバリデーション結果を保存しているのがわかります。cacheの実態はただの二次元mapです。
また、他の点でもパフォーマンスに気を使っているとのことで、Reverseではちょっと工夫して
func reverseInt16Ptr(itemsValue reflect.Value) interface{}{
input := itemsValue.Interface().([]*int16)
len := len(input)
output := make([]*int16, len)
for index := 0; index < (len/2)+1; index++ {
output[index], output[len-1-index] = input[len-1-index], input[index]
}
return output
}
ループ処理が半分で済むように実装されていたりします。
まとめ
年末に彗星のごとく現れたKoazee、使いやすく、それでいて高速！
キャッシュまわりはgoroutineと併用されたときにどうなるのーとか気になりますが、今後に注目です。