[インデックス 14118] ファイルの概要

このコミットは、Go言語の標準ライブラリである container/heap パッケージ内のヒープ操作（up および down 関数）におけるパフォーマンス最適化を導入しています。特に、ヒープ内に重複する要素が多数存在する場合の効率を向上させることを目的としています。変更は heap.go の比較ロジックの修正と、その効果を測定するための新しいベンチマーク BenchmarkDup の追加が heap_test.go に含まれています。

コミット

• コミットハッシュ: c12dab2aa606fda6b8ff54082de775bf7737c866
• Author: Taj Khattra taj.khattra@gmail.com
• Date: Wed Oct 10 11:35:57 2012 -0700

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/c12dab2aa606fda6b8ff54082de775bf7737c866

元コミット内容

container/heap: optimization in case heap has many duplicates

benchmark       old ns/op    new ns/op    delta
BenchmarkDup      3075682       609448  -80.18%

R=gri
CC=golang-dev
https://golang.org/cl/6613064

変更の背景

このコミットの主な背景は、Go言語の container/heap パッケージが、ヒープ内に多数の重複要素が存在する特定のシナリオにおいて、非効率な動作をしていた点にあります。ヒープの up (ヒープアップ) および down (ヒープダウン) 操作は、要素の挿入や削除の際にヒープのプロパティ（親が子よりも小さい/大きいという順序）を維持するために不可欠です。

従来の比較ロジック h.Less(i, j) は、「i番目の要素がj番目の要素より小さいか」を評価します。しかし、要素が重複している場合、例えば h.Less(i, j) が false であっても、h.Less(j, i) も false である（つまり i と j が等しい）という状況が発生します。このような場合、従来のロジックでは不要なスワップが発生したり、ループが余分に繰り返されたりする可能性がありました。

特に、すべての要素が同じ値であるような極端なケース（BenchmarkDup でシミュレートされているシナリオ）では、この非効率性が顕著になり、パフォーマンスが大幅に低下していました。このコミットは、この問題を解決し、重複要素が多い場合のヒープ操作のパフォーマンスを劇的に改善することを目的としています。ベンチマーク結果が示すように、約80%のパフォーマンス向上が達成されています。

前提知識の解説

ヒープ (Heap)

ヒープは、ツリーベースのデータ構造であり、特定のヒーププロパティを満たすものです。最も一般的なヒープは二分ヒープで、以下の2つの主要なプロパティを持ちます。

1. 形状プロパティ (Shape Property): ヒープは完全二分木（Complete Binary Tree）である必要があります。これは、木のすべてのレベルが完全に埋まっており、最後のレベルのノードは可能な限り左に詰められていることを意味します。これにより、配列を使って効率的にヒープを表現できます。

   • 配列のインデックス i の要素の親は (i-1)/2
   • 左の子は 2*i + 1
   • 右の子は 2*i + 2

2. ヒーププロパティ (Heap Property):

   • 最小ヒープ (Min-Heap): 各ノードの値は、その子ノードの値よりも小さいか等しい。したがって、根（ルート）ノードがヒープ内の最小値になります。
   • 最大ヒープ (Max-Heap): 各ノードの値は、その子ノードの値よりも大きいか等しい。したがって、根ノードがヒープ内の最大値になります。

Go言語の container/heap パッケージは、最小ヒープとして実装されており、sort.Interface を満たす任意の型で動作します。

container/heap パッケージ

Goの container/heap パッケージは、sort.Interface を実装する任意のコレクションに対してヒープ操作を提供します。sort.Interface は以下の3つのメソッドを定義します。

• Len() int: コレクションの要素数を返します。
• Less(i, j int) bool: i 番目の要素が j 番目の要素より小さい場合に true を返します。
• Swap(i, j int): i 番目と j 番目の要素を交換します。

heap パッケージの主要な関数には以下があります。

• Push(h Interface, x interface{}): ヒープに要素 x を追加します。要素を追加した後、ヒーププロパティを維持するために up 操作が内部的に呼び出されます。
• Pop(h Interface) interface{}: ヒープの最小要素（ルート）を削除し、返します。要素を削除した後、ヒーププロパティを維持するために down 操作が内部的に呼び出されます。
• Fix(h Interface, i int): i 番目の要素が変更された場合に、ヒーププロパティを復元します。これは up または down を呼び出すことで行われます。
• Remove(h Interface, i int) interface{}: i 番目の要素を削除します。

up (ヒープアップ) 操作

up 関数は、新しく追加された要素（または変更された要素）がヒーププロパティを破っている場合に、その要素を適切な位置に「持ち上げる」ために使用されます。具体的には、要素が親よりも小さい場合、親と子を交換し、このプロセスを根に到達するか、ヒーププロパティが満たされるまで繰り返します。

down (ヒープダウン) 操作

down 関数は、ヒープの根の要素が削除された後、または変更された要素がヒーププロパティを破っている場合に、その要素を適切な位置に「沈める」ために使用されます。具体的には、要素が子よりも大きい場合、より小さい子と交換し、このプロセスを葉に到達するか、ヒーププロパティが満たされるまで繰り返します。

技術的詳細

このコミットの核心は、up 関数と down 関数内の比較ロジックの変更です。

変更前 (h.Less(i, j))

従来のロジックでは、h.Less(i, j) を使用して要素 i と j を比較していました。

• up 関数では、if i == j || h.Less(i, j) という条件がありました。これは「親が子より小さいか、または同じ位置にいるか」をチェックします。もし親が子より小さい（または等しい）場合、ヒーププロパティは満たされているため、ループを抜けます。
• down 関数では、if h.Less(i, j) という条件がありました。これは「親が子より小さいか」をチェックします。もし親が子より小さい場合、ヒーププロパティは満たされているため、ループを抜けます。

このロジックの問題点は、h.Less(i, j) が false を返しても、i と j が等しい可能性があることです。例えば、h.Less(i, j) が false で、かつ h.Less(j, i) も false の場合、これは i と j が等しいことを意味します。従来のロジックでは、この「等しい」ケースで不要なスワップが発生したり、ループが継続したりする可能性がありました。

変更後 (!h.Less(j, i))

変更後のロジックでは、!h.Less(j, i) を使用しています。これは「j 番目の要素が i 番目の要素より小さくないか」を評価します。

• up 関数: if i == j || !h.Less(j, i)

  • !h.Less(j, i) は、「j が i より小さくない」という意味です。これは j >= i と同義です（Less が厳密な比較である場合）。
  • 最小ヒープの up 操作では、子要素 j が親要素 i よりも小さい場合にスワップが必要です。つまり、h.Less(j, i) が true の場合にスワップします。
  • したがって、!h.Less(j, i) が true の場合（つまり h.Less(j, i) が false の場合）、スワップは不要であり、ループを抜けるべきです。この変更により、i と j が等しい場合でも、h.Less(j, i) は false を返すため、正しくループを抜けることができます。

• down 関数: if !h.Less(j, i)

  • 最小ヒープの down 操作では、親要素 i が子要素 j よりも大きい場合にスワップが必要です。つまり、h.Less(j, i) が true の場合にスワップします。
  • したがって、!h.Less(j, i) が true の場合（つまり h.Less(j, i) が false の場合）、スワップは不要であり、ループを抜けるべきです。この変更も up 関数と同様に、i と j が等しい場合でも、h.Less(j, i) は false を返すため、正しくループを抜けることができます。

最適化の理由

この変更の鍵は、Less メソッドが「厳密に小さい」ことを意味する場合にあります。

• h.Less(i, j) が true なら i < j
• h.Less(i, j) が false なら i >= j

従来の h.Less(i, j) を使用した比較では、i と j が等しい場合（i == j）、h.Less(i, j) は false を返します。このとき、ヒーププロパティが満たされているにもかかわらず、ループが継続してしまう可能性がありました。

新しい !h.Less(j, i) という条件は、j が i より小さくない、つまり j >= i であることを意味します。最小ヒープでは、親は子より小さいか等しいべきです。したがって、j >= i であれば、ヒーププロパティは満たされており、それ以上スワップする必要はありません。

この変更により、特に重複する要素が多いヒープにおいて、不要な比較やスワップの試行が削減され、up および down 操作の効率が大幅に向上します。BenchmarkDup の結果（80.18%のパフォーマンス向上）がこの効果を明確に示しています。

コアとなるコードの変更箇所

src/pkg/container/heap/heap.go の up 関数と down 関数の条件式が変更されています。

--- a/src/pkg/container/heap/heap.go
+++ b/src/pkg/container/heap/heap.go
@@ -79,7 +79,7 @@ func Remove(h Interface, i int) interface{} {
 func up(h Interface, j int) {
 	for {
 		i := (j - 1) / 2 // parent
-		if i == j || h.Less(i, j) {
+		if i == j || !h.Less(j, i) {
 			break
 		}
 		h.Swap(i, j)
@@ -97,7 +97,7 @@ func down(h Interface, i, n int) {
 	if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
 		j = j2 // = 2*i + 2  // right child
 	}
-	if h.Less(i, j) {
+	if !h.Less(j, i) {
 		break
 	}
 	h.Swap(i, j)

また、src/pkg/container/heap/heap_test.go に新しいベンチマーク BenchmarkDup が追加されています。

--- a/src/pkg/container/heap/heap_test.go
+++ b/src/pkg/container/heap/heap_test.go
@@ -170,3 +170,16 @@ func TestRemove2(t *testing.T) {\n     		}\n     	}\n     }\n    +\n    +func BenchmarkDup(b *testing.B) {\n    +\tconst n = 10000\n    +\th := make(myHeap, n)\n    +\tfor i := 0; i < b.N; i++ {\n    +\t\tfor j := 0; j < n; j++ {\n    +\t\t\tPush(&h, 0) // all elements are the same\n    +\t\t}\n    +\t\tfor h.Len() > 0 {\n    +\t\t\tPop(&h)\n    +\t\t}\n    +\t}\n    +}\n```

## コアとなるコードの解説

### `src/pkg/container/heap/heap.go` の変更

#### `up` 関数

```go
func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // parent
		// 変更前: if i == j || h.Less(i, j) {
		if i == j || !h.Less(j, i) { // 変更後
			break
		}
		h.Swap(i, j)
		j = i
	}
}

• i := (j - 1) / 2: 現在の要素 j の親のインデックス i を計算します。
• if i == j || !h.Less(j, i):
  • i == j: j が根（ルート）に到達した場合、それ以上上に移動できないためループを終了します。
  • !h.Less(j, i): これが変更の核心です。
    • h.Less(j, i) は「j が i より小さいか」を意味します。
    • !h.Less(j, i) は「j が i より小さくないか」を意味します。つまり、「j が i 以上であるか」ということです。
    • 最小ヒープのプロパティは「親 <= 子」です。up 操作では、子 j が親 i より小さい場合にスワップが必要です。
    • もし j が i 以上であれば（!h.Less(j, i) が true）、ヒーププロパティは既に満たされているか、またはスワップが不要な状態です。この場合、ループを終了します。
• h.Swap(i, j): もし上記の条件が満たされなければ（つまり j が i より小さい場合）、親と子を交換します。
• j = i: 交換後、j は新しい親の位置になり、次のループでさらに上に移動できるかチェックします。

この変更により、i と j が等しい場合（h.Less(j, i) が false となる）に、不要なスワップを試みることなくループを終了できるようになり、特に重複要素が多い場合の効率が向上します。

down 関数

func down(h Interface, i, n int) {
	for {
		j1 := 2*i + 1 // left child
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
			j = j2 // = 2*i + 2  // right child
		}
		// 変更前: if h.Less(i, j) {
		if !h.Less(j, i) { // 変更後
			break
		}
		h.Swap(i, j)
		i = j
	}
}

• j1 := 2*i + 1: 現在の要素 i の左の子のインデックス j1 を計算します。
• if j1 >= n || j1 < 0: 子が存在しない場合（ヒープの範囲外）はループを終了します。
• j := j1: 比較対象の子を最初は左の子とします。
• if j2 := j1 + 1; j2 < n && !h.Less(j1, j2):
  • 右の子 j2 が存在し、かつ左の子 j1 が右の子 j2 より小さくない場合（つまり j1 >= j2）、より小さい子（または等しい子）を選択するために j を右の子 j2 に設定します。最小ヒープでは、親と交換するのは常に「より小さい方の子」です。
• if !h.Less(j, i): これが変更の核心です。
  • h.Less(j, i) は「j が i より小さいか」を意味します。
  • !h.Less(j, i) は「j が i より小さくないか」を意味します。つまり、「j が i 以上であるか」ということです。
  • 最小ヒープの down 操作では、親 i が子 j より大きい場合にスワップが必要です。
  • もし j が i 以上であれば（!h.Less(j, i) が true）、ヒーププロパティは既に満たされているか、またはスワップが不要な状態です。この場合、ループを終了します。
• h.Swap(i, j): もし上記の条件が満たされなければ（つまり j が i より小さい場合）、親と子を交換します。
• i = j: 交換後、i は新しい子の位置になり、次のループでさらに下に移動できるかチェックします。

この変更も up 関数と同様に、i と j が等しい場合（h.Less(j, i) が false となる）に、不要なスワップを試みることなくループを終了できるようになり、特に重複要素が多い場合の効率が向上します。

src/pkg/container/heap/heap_test.go の変更

BenchmarkDup の追加

func BenchmarkDup(b *testing.B) {
	const n = 10000
	h := make(myHeap, n)
	for i := 0; i < b.N; i++ {
		for j := 0; j < n; j++ {
			Push(&h, 0) // all elements are the same
		}
		for h.Len() > 0 {
			Pop(&h)
		}
	}
}

• このベンチマークは、n=10000 個の要素を持つヒープを対象としています。
• Push(&h, 0): すべての要素が 0 という同じ値でヒープに挿入されます。これは、ヒープ内に多数の重複要素が存在するシナリオを意図的に作り出しています。
• Pop(&h): ヒープからすべての要素を削除します。
• b.N 回の繰り返しで、ヒープの構築と削除のサイクルを測定します。

このベンチマークは、まさにこのコミットが解決しようとしている「重複要素が多い場合のパフォーマンス問題」を浮き彫りにし、その改善効果を定量的に示すために導入されました。コミットメッセージにある BenchmarkDup の結果は、このベンチマークが変更前と変更後で劇的なパフォーマンス改善を示したことを裏付けています。

関連リンク

• Go CL (Change List): https://golang.org/cl/6613064

参考にした情報源リンク

• Go言語 container/heap パッケージのドキュメント: https://pkg.go.dev/container/heap
• Go言語 sort.Interface のドキュメント: https://pkg.go.dev/sort#Interface
• ヒープ (データ構造) - Wikipedia: https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)
• 完全二分木 - Wikipedia: https://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%88%86%E6%9C%A8