とあるPRにて
「並べ替えするならsortパッケージよりslicesパッケージ使った方が速いっすよ」
とコメントいただき速度比較した記事を教えてもらいました。
その場で単に変更するのは簡単かもしれませんが、なぜ速度が違うのか気になったので調べてみました。
TL;DR
slicesパッケージはジェネリクスを利用している一方、sortパッケージはinterface{}を使っているため、slicesパッケージの方が実行速度が速い。
まずは事実確認
Goのリポジトリにあるサンプルコードを使って確認しました。
サンプルコードはsortパッケージとslicesパッケージを使ってソートする関数をベンチマークで比較しています。
ベンチマーク結果
% go test -bench=. -benchmem
goos: darwin
goarch: arm64
pkg: github.com/compare-sort-slices
BenchmarkSortInts-8 130 8896256 ns/op 24 B/op 1 allocs/op
BenchmarkSlicesSortInts-8 234 5111604 ns/op 0 B/op 0 allocs/op
BenchmarkSortIsSorted-8 5286 243288 ns/op 25 B/op 1 allocs/op
BenchmarkSlicesIsSorted-8 24919 47829 ns/op 3 B/op 0 allocs/op
BenchmarkSortStrings-8 66 17409972 ns/op 24 B/op 1 allocs/op
BenchmarkSlicesSortStrings-8 80 14541226 ns/op 0 B/op 0 allocs/op
BenchmarkSortStrings_Sorted-8 3164 376935 ns/op 24 B/op 1 allocs/op
BenchmarkSlicesSortStrings_Sorted-8 3831 314397 ns/op 0 B/op 0 allocs/op
BenchmarkSortStructs-8 99 10719252 ns/op 30 B/op 1 allocs/op
BenchmarkSortFuncStructs-8 145 8172721 ns/op 10 B/op 0 allocs/op
PASS
ok github.com/compare-sort-slices 22.798s
ベンチマークの各結果は、左からベンチマーク実行回数、実行時間、メモリ使用量、メモリ割り当て回数となっていますが、sortパッケージを使った場合はslicesパッケージを使った場合よりも実行時間が長く、メモリ使用量も多いことがわかります。
ベンチマーク結果からもslicesパッケージの方が速いことが確認できました。
また、実行速度だけでなく、メモリ使用量もslicesパッケージの方が少ないことがことが確認できました。
なぜ速度が違うのかを確認するためにソースコードを見てみる
それぞれのパッケージを使ったソート関数のソースコードを見てみます。
slicesパッケージ（参照）
slicesパッケージのソート関数
func Sort[S ~[]E, E constraints.Ordered](x S) {
n := len(x)
pdqsortOrdered(x, 0, n, bits.Len(uint(n)))
}
func pdqsortOrdered[E constraints.Ordered](data []E, a, b, limit int) {
const maxInsertion = 12
var (
wasBalanced = true // whether the last partitioning was reasonably balanced
wasPartitioned = true // whether the slice was already partitioned
)
for {
length := b - a
if length <= maxInsertion {
insertionSortOrdered(data, a, b)
return
}
// Fall back to heapsort if too many bad choices were made.
if limit == 0 {
heapSortOrdered(data, a, b)
return
}
// If the last partitioning was imbalanced, we need to breaking patterns.
if !wasBalanced {
breakPatternsOrdered(data, a, b)
limit--
}
pivot, hint := choosePivotOrdered(data, a, b)
if hint == decreasingHint {
reverseRangeOrdered(data, a, b)
// The chosen pivot was pivot-a elements after the start of the array.
// After reversing it is pivot-a elements before the end of the array.
// The idea came from Rust's implementation.
pivot = (b - 1) - (pivot - a)
hint = increasingHint
}
// The slice is likely already sorted.
if wasBalanced && wasPartitioned && hint == increasingHint {
if partialInsertionSortOrdered(data, a, b) {
return
}
}
// Probably the slice contains many duplicate elements, partition the slice into
// elements equal to and elements greater than the pivot.
if a > 0 && !cmpLess(data[a-1], data[pivot]) {
mid := partitionEqualOrdered(data, a, b, pivot)
a = mid
continue
}
mid, alreadyPartitioned := partitionOrdered(data, a, b, pivot)
wasPartitioned = alreadyPartitioned
leftLen, rightLen := mid-a, b-mid
balanceThreshold := length / 8
if leftLen < rightLen {
wasBalanced = leftLen >= balanceThreshold
pdqsortOrdered(data, a, mid, limit)
a = mid + 1
} else {
wasBalanced = rightLen >= balanceThreshold
pdqsortOrdered(data, mid+1, b, limit)
b = mid
}
}
}
sortパッケージ（参照）
sortパッケージのソート関数
func Sort(data Interface) {
n := data.Len()
if n <= 1 {
return
}
limit := bits.Len(uint(n))
pdqsort(data, 0, n, limit)
}
func pdqsort(data Interface, a, b, limit int) {
const maxInsertion = 12
var (
wasBalanced = true // whether the last partitioning was reasonably balanced
wasPartitioned = true // whether the slice was already partitioned
)
for {
length := b - a
if length <= maxInsertion {
insertionSort(data, a, b)
return
}
// Fall back to heapsort if too many bad choices were made.
if limit == 0 {
heapSort(data, a, b)
return
}
// If the last partitioning was imbalanced, we need to breaking patterns.
if !wasBalanced {
breakPatterns(data, a, b)
limit--
}
pivot, hint := choosePivot(data, a, b)
if hint == decreasingHint {
reverseRange(data, a, b)
// The chosen pivot was pivot-a elements after the start of the array.
// After reversing it is pivot-a elements before the end of the array.
// The idea came from Rust's implementation.
pivot = (b - 1) - (pivot - a)
hint = increasingHint
}
// The slice is likely already sorted.
if wasBalanced && wasPartitioned && hint == increasingHint {
if partialInsertionSort(data, a, b) {
return
}
}
// Probably the slice contains many duplicate elements, partition the slice into
// elements equal to and elements greater than the pivot.
if a > 0 && !data.Less(a-1, pivot) {
mid := partitionEqual(data, a, b, pivot)
a = mid
continue
}
mid, alreadyPartitioned := partition(data, a, b, pivot)
wasPartitioned = alreadyPartitioned
leftLen, rightLen := mid-a, b-mid
balanceThreshold := length / 8
if leftLen < rightLen {
wasBalanced = leftLen >= balanceThreshold
pdqsort(data, a, mid, limit)
a = mid + 1
} else {
wasBalanced = rightLen >= balanceThreshold
pdqsort(data, mid+1, b, limit)
b = mid
}
}
}
両者を比べてみるとほとんど同じプログラムになっています。
中身を詳しく見てみる
-
使用しているアルゴリズムは同じ
Pattern-Defeating Quicksort（O(nlogn)）を使用しています。クイックソートの苦手とする同値の並べ替えに対する改良版のアルゴリズムです。
Go1.19でsortパッケージのアルゴリズムが変更されていました。（参照） -
sortパッケージは引数の型にinterface{}を使っている一方でslicesパッケージはジェネリクスを使用
ジェネリクスを使用することで、プログラムの再利用性と型安全性を高めているようでした。 -
slicesパッケージでは受け取れる型に
constraints.Orderedを指定しており、プログラムの安全性が高められていました。
まとめ
sortパッケージにおいては型チェックが動的に（実行時に）行われるため若干メモリを消費し、ジェネリクスを使用するslicesパッケージでは実行時にあらかじめ型がわかっているためsortパッケージ側で行われている処理を減らすことができ、実行速度が速いということがわかりました。
また、プログラムの安全性を高めることも同時に実現されていました。
感想
２つのパッケージで使用されている関数の中身がほとんど同じであることは意外でした。アルゴリズムが違うのかと思って調べ始めましたが、実際には扱う型の違いだけだったのはおもしろい発見でした。
採用しているアルゴリズムがクイックソートの改良版であることがわかり、興味深かったです。
また、処理速度の違いだけでなく、メモリの使用にも影響していることを知れたのはとてもよい副産物でした。
ソースコードをパッケージの中まで読むということは、自分の知識を深めるためにも大切だと改めて感じました。
採用情報
e-dash エンジニアチームは現在一緒にはたらく仲間を募集中です！
同じ夢について語り合える仲間と一緒に、環境問題を解決するプロダクトを作りませんか？
Discussion