sort.Slice の実装をかいつまんで紹介し、様々な型 (特に様々なスライス型) を受け取りつつ速度を落とさず処理をするヒントを探ってみようと思います。
Go 1.8 から追加されている sort.Slice は、従来の sort.Sort と同等の速度で動作します。
気になるのが、sort.Slice には様々な型のスライスを渡せるのに、要素の交換についての処理をユーザーが記述しなくても良いということです。
// 従来の sort.Sort では、ソート対象に関する操作を定義して sort.Interface として渡している。
type ByValue []string
func (s ByValue) Len() int { return len(s) }
func (s ByValue) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s ByValue) Less(i, j int) bool { return s[i] < s[j] }
var sslice []string = ...
sort.Sort(ByValue(sslice))
// sort.Slice
var sslice []string = ...
sort.Slice(sslice, func(i, j int) bool { return sslice[i] < sslice[j] })
// あれ、従来の Len や Swap に相当する処理は定義しなくて良いの?
sort.Slice の内部では、どのように要素を交換しているのでしょうか？
たとえば「sort.Slice みたいにどんな型でも受け取りつつ統一的な処理をするような関数を実装しろ」といわれたら、リフレクションを使って汎用的に処理を記述することを思いつくかと思います。
ですが、それではリフレクションが足かせとなり、実行速度が大きく損なわれてしまいます。
sort.Slice はどのようにして高速な実行速度を実現しているのでしょうか。
sort.Slice は様々な型のスライスを受け付けられる
Go では、下のようにしてスライスをソートできます。
// []int
hoge := []int{6, 2, 7, 1, 8, 4, 5}
sort.Slice(hoge, func(i, j int) { return hoge[i] < hoge[j] })
// []string
piyo := []string{"6", "2", "7", "1", "8", "4", "5"}
sort.Slice(piyo, func(i, j int) { return piyo[i] < piyo[j] })
この例のように、[]int や []string を同じ関数 Slice に処理させることができます。
ですので、スライスのベースとなる型ごとに SortIntSlice や SortMyStructSlice といった関数を定義する必要はありません。
sort.Slice 内部では要素の交換を行っているのに、型を意識せずにスライスを渡せば OK というのがすごいところです。
interface{} + reflect
sort.Slice の第一引数は interface{} となっていますし、実は内部で reflect パッケージを使って処理しています。
そのため、どのようなスライスでも処理できるようになっています。
なのに遅くない
前回の投稿 sort.Sort と sort.Slice の速度比較 にもあるように、sort.Slice ではリフレクションを使っているにもかかわらず、遅くありません。というかリフレクション使ってない版と同程度の速度です。
通常、Go でリフレクションを駆使して処理した場合、リフレクションを使わない場合よりも実行速度が 1/10 程度に低下するものです。
ソートの処理の主役
ソートにおける主な処理には「要素の比較」と「要素の交換」があります。
比較の処理は sort.Slice の呼び出し側がクロージャーとして渡しているので、リフレクションは絡まず、したがってリフレクション特有の速度低下がありません。
ですが、要素の交換は interface{} に変換されたものに対して行う必要があるため、そこでリフレクションを使ったりして速度が低下してそうなものです。
一体、何故、sort.Slice は速度低下がないのでしょうか？
キモは reflect.Swapper
要素の交換を行うのは、sort.Slice の内部で生成された swap という関数です。(ソース)
この swap は、関数を返す関数 reflect.Swapper によって生成されます。
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))
}
swap の生成後、ソートの処理としては肝心の quickSort_func に渡しています。
quickSort_func では、この swap を使うことで要素の交換を行います。
それでは、reflect.Swapper はどのような swap 関数を生成しているのでしょうか。
これが生成している swap 関数が良い感じになっているために実行速度が低下していないのだと考えられます。
reflect.Swapper 高速化のためのアプローチ
そういうわけで、reflect.Swapper がどのようにして高速な実行速度を実現しているのか見ていきましょう。
実は内部で型 (型のサイズ) ごとに処理していた
reflect.Swapper では swap 関数を生成する際に、Type Switch 的なことをしており、それによって型サイズごとの swap 関数を生成しています。 (ソース)
Swapper は型ではなく型のサイズで場合分けをしています。
// return されているのが、sort.Slice が使おうとしている swap の実体
switch size {
case 8:
is := *(*[]int64)(v.ptr)
return func(i, j int) { is[i], is[j] = is[j], is[i] }
case 4:
is := *(*[]int32)(v.ptr)
return func(i, j int) { is[i], is[j] = is[j], is[i] }
case 2:
is := *(*[]int16)(v.ptr)
return func(i, j int) { is[i], is[j] = is[j], is[i] }
case 1:
is := *(*[]int8)(v.ptr)
return func(i, j int) { is[i], is[j] = is[j], is[i] }
}
細かい挙動よりも、要素の型サイズごとに変換したスライス is を取得していることに注目してください。
また、返している関数がスライスを参照するクロージャーになっています。
結果的に、ここで返している swap 関数はそれぞれの型に特化した処理を行うことになります。
これはリフレクションとは無関係な普通のスライス要素の交換ですので、リフレクションによる速度低下とは無縁です。
厳密には「型に特化」というよりも「特定のサイズの型に特化」といったほうが正確です。
ですが、普通の Type Switch を使って本来のビルトイン型に変更する場合でも同様に、リフレクションとは無縁の速度で処理できます。
いずれにしても、interface{} や reflect.Value のような汎用的な型を操作するのではなく、ビルトイン型に落とし込んでいくことが重要そうです。
想定の型サイズ (ビルトイン型など) 以外は、力技で対処していた
では、sort.Slice に []struct MyStruct{ xxx } を渡していた場合はどうでしょうか。
このような型があるかことは、当然ながら、Swapper には知る由はありません。
もしかすると、1つの要素が 100 bytes もあるような型かもしれません。
その場合、memmove で直接 メモリ操作を行います。(ソース)
何がなんでも1回で1要素を操作したいようです。
s := (*sliceHeader)(v.ptr)
tmp := unsafe_New(typ) // swap scratch space
return func(i, j int) {
if uint(i) >= uint(s.Len) || uint(j) >= uint(s.Len) {
panic("reflect: slice index out of range")
}
val1 := arrayAt(s.Data, i, size)
val2 := arrayAt(s.Data, j, size)
typedmemmove(typ, tmp, val1)
typedmemmove(typ, val1, val2)
typedmemmove(typ, val2, tmp)
}
つまり、sort.Slice 内部ではさほどリフレクションを使わないようにしているわけです。
リフレクションを使ってもなお早い、とかなら夢と希望があったんですけどね。
まぁ、そんな魔法はないということですね…
スライスの内部データ (配列) に触る
さて、上で触れたように swap 関数はクロージャーなので、引数 i, j とは別に関数外の変数を参照できます。
そのため、swap 内部からは is という元々の操作対象のスライスが参照している配列領域を操作できるわけです。
関数外の変数云々についてですが、結局のところ sort.Slice に比較関数を渡すのと同じことをしているわけです。
sort.Slice に学ぶ高速化のヒント
というわけで、これまでのところで、sort.Slice のように様々な型を受け入れつつも高速に (特別な速度低下なしに) 操作を実現する方法を見てきました。
以下のヒントがありましたので、まとめておきたいと思います。
- 極力ビルトイン型に変換する。リフレクションは最小限度かつ局所に抑える。
- アクセス手段の抽象化をする。
極力ビルトイン型に変換する。リフレクションは最小限度かつ局所に抑える。
- リフレクションは遅いので避ける。
- 引数では interface{} として受け取っても、最終的には何かしら具体的な型に落とし込む。
- 変換やリフレクションの使用は早めに終わらせ、ループなどの繰り返しの処理では行わない。局所的なものとする。
リフレクションを局所に抑えているのは、reflect.Swapper で関数 swap を生成する箇所が該当します。
2つ目のヒント「アクセス手段の共通化」にも関係しますが、swap を生成した後はリフレクションの処理は行いません。
つまりソートの繰り返し処理中にはリフレクションを使いません。
アクセス手段の抽象化をする。
ソートにおける主な処理には「要素の比較」と「要素の交換」があると言いました。
では sort.Slice においてはどのように抽象化されていたでしょうか。
- 要素の比較 : クロージャーで、sort.Slice の第一引数と同じスライスを使った比較処理を渡している
- 要素の交換 : クロージャー swap で、sort.Slice が第一引数で受け取ったスライスに対する操作を渡している
このように、コンテナを直接操作したり参照したりするのではなく、抽象化されたクロージャーを通して行うようにします。
たとえば、スライスの要素にアクセスしようとして someSlice[i] としてしまうと、途端にその要素の型を意識したコードが要求されます。
someSlice[i] が int なのか string なのかといった判定をソートの処理中にすることになるので、対応できる型が限定されてしまったり、リフレクションを使わないといけなくなったりします。
スライスには直接触れず、あくまでも添字を受け取る関数として抽象化されている方法を使うことで、sort.Slice では swap の生成以外では型を意識せずにすみ、上記の問題が起きません。
コンテナやその要素のアクセス手段を知っているのは、あくまでもユーザーコードだけです。