Help us understand the problem. What is going on with this article?

高速コレクション操作ライブラリ「Koazee」

この記事は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)

WhereSelectに渡される関数リテラルの中で、型アサーションしています。なんだか面倒くさい。go-linqにはWhereTSelectTといった、関数リテラル自体を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と併用されたときにどうなるのーとか気になりますが、今後に注目です。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away