【Go】実行速度と汎用性を両立させたContains関数作ってみた

きっかけ

Goの可変長配列であるスライス。配列の実態を考慮する必要がないシンプルさが売りです。

が、シンプルすぎるが故欲しい関数が実装されていない事もしばしば。特に特定の値が存在するか判定するContains関数などは使いたい場面が多いです。

そこで今回は出来る限り汎用性と実行速度を両立させたContains関数の実装を目指します。

書いてみる

まずはシンプルに実装します

func main() {
    Contains([]int{1, 2, 3, 4, 5}, 3)
}

func Contains(s []int, n int) bool {
    for _, v := range s {
        if v == n {
            return true
        }
    }

    return false
}

動く！けどintのスライス型しか引数にとれませんね

reflectで引数に汎用性を持たせる

引数に汎用性を持たせる為によく使う手法がreflectパッケージによる抽象化です。

reflectパッケージとはinterface{}型の変数から型と値情報を検出するパッケージ。

調べるとGoで型に縛られない良い感じのContains関数の書き方に実装例が紹介されていました。やっぱり誰か試してるよね。

structだろうがfloatだろうがpanic起こさず判別出来ます。

問題点

reflectパッケージの欠点として実行速度が遅さが挙げられます。コンパイル時点で型定義できないのでアロケーション回数が増えてしまう様ですね。

一体どの程度実行速度に影響が生まれるのでしょうか？

ベンチマーク

実際に二つの実行速度を計測します

  • ContainsSim reflectなし
  • ContainsCom reflectあり

結果

BenchmarkContainsSim
BenchmarkContainsSim-4      85581004            12.01 ns/op
BenchmarkContainsCom
BenchmarkContainsCom-4        870052          1243 ns/op

うーむ。。。１００倍近い差が生まれています

改善

いくらなんでもパフォーマンスに差があり過ぎるので、少し改善を測ってみます。

ボトルネック調査

41.3% reflect.DeepEqual
25.8% reflect.Value.Interface
 5.6% reflect.Value.Index

プロファイル結果の一部抜粋。様はDeepEqualとInterfaceがボトルネックっぽいですね。

改善案1

  • DeepEqualを抜きたい

    • 引数の型を絞る
    • 構造体等は諦めて、stringやint,floatのみ

  • Interface()を抜きたい

    • 調べてみるとreflect.Typeの構造体をInterface{}型の変数に戻すだけのメソッド
    • DeepEqualを使わないのであればinterface{}型の変数は必要ないはず

結局Contains関数の第一引数に入るのはほとんどの場合[]int []string []floatのどれかだと思うので、構造体は諦めて実装

func ContainsMid(list interface{}, elem interface{}) bool {
    listV := reflect.ValueOf(list)
 
    if listV.Kind() == reflect.Slice {
        for i := 0; i < listV.Len(); i++ {
            item := listV.Index(i)

            if !reflect.TypeOf(elem).ConvertibleTo(item.Type()) {
                return false
            }
         
            switch elem.(type) {
            case string:
                if elem == item.String() {
                    return true
                }
            case int:
                if elem == int(item.Int()) {
                    return true
                }
            case int64:
                if elem == item.Int() {
                    return true
                }
            case int32:
                if elem == int32(item.Int()) {
                    return true
                }
            case int16:
                if elem == int16(item.Int()) {
                    return true
                }
            case int8:
                if elem == int8(item.Int()) {
                    return true

                }
            case float64:
                if elem == float64(item.Int()) {
                    return true
                }
            case float32:
                if elem == float32(item.Int()) {
                    return true
                }
            default:
                panic(errors.New("contains() cannot take a type other than string and int as an argument"))
            }
        }
    }

    return false
}

string, int8-64, float以外の型を与えるとpanicが出る設計。err返しちゃった方が良いのかな

結果

BenchmarkContainsMid
BenchmarkContainsMid-4       4004848           302.7 ns/op

3倍速にはなりましたがまだ遅いですね

プロファイル結果をみるとConvertible位は削れそう

24.5% reflect.Value.Index()
19.6% reflect.Convertible()

加えて引数にintのスライスとstringを与えるとバグが発生

func main() {
  Contains([]int{1, 2, 3}, "a") // panic
}

Convertible()というメソッド名からintとstringの差分を検出してくれそうな気がしていたのですが機能していない様子。何するメソッドなんやこれ。doc読んでも良くわかりませんでした

改善案2

func ContainsMid(list interface{}, elem interface{}) bool {
    listV := reflect.ValueOf(list)

    if listV.Kind() == reflect.Slice {
        for i := 0; i < listV.Len(); i++ {
            item := listV.Index(i)

            switch elem.(type) {
            case string:
                if item.Kind() == reflect.String && elem == item.String() {
                    return true
                }
            case int:
                if item.Kind() == reflect.Int && elem == int(item.Int()) {
                    return true
                }
            case int64:
                if item.Kind() == reflect.Int64 && elem == item.Int() {
                    return true
                }
            case int32:
                if item.Kind() == reflect.Int32 && elem == int32(item.Int()) {
                    return true
                }
            case int16:
                if item.Kind() == reflect.Int16 && elem == int16(item.Int()) {
                    return true
                }
            case int8:
                if item.Kind() == reflect.Int8 && elem == int8(item.Int()) {
                    return true

                }
            case float64:
                if item.Kind() == reflect.Float64 && elem == float64(item.Int()) {
                    return true
                }
            case float32:
                if item.Kind() == reflect.Float32 && elem == float32(item.Int()) {
                    return true
                }
            default:
                panic(errors.New("contains() cannot take a type other than string and int as an argument"))
            }
        }
    }

    return false
}

結果

BenchmarkContainsMid
BenchmarkContainsMid-4        7484228          157.6 ns/op
PASS

更に倍速になりました。

結論

  • 引数をstring, int, float型に限定する事でパフォーマンスは10倍程度あがった
  • 汎用性を削った結果予期しない引数を与えるとpanicが発生

器用貧乏。。。？引数の汎用性を落とすなら、素直にプリミティブ型それぞれにContainsXXX()といった形でメソッド作った方がいい気もします。

けど折角作ったので暫くideの予測変換に追加して使ってみようと思います

参考

Goにおけるreflect周り調べた