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

このコミットは、Go言語の標準ライブラリ sort パッケージにおける maxDepth の計算ロジックのバグ修正に関するものです。具体的には、quickSort 関数がヒープソートに切り替えるべき深さを決定する際に使用する maxDepth の計算が、特定の大きな入力サイズ（n > 1<<30、32ビット整数環境の場合）で無限ループに陥る問題を解決しています。この修正により、ソートアルゴリズムの堅牢性が向上し、非常に大きなデータセットに対しても正しく動作するようになります。

コミット

commit c5488d4f004e9f38e5fb996dd709a73aed03cd00
Author: Stefan Nilsson <snilsson@nada.kth.se>
Date:   Tue Mar 20 14:23:12 2012 -0700

    sort: fix computation of maxDepth to avoid infinite loop
    
    The current computation loops indefinitely if n > 1<<30 (for 32-bit ints).
    
    R=golang-dev, gri
    CC=golang-dev
    https://golang.org/cl/5848067

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

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

元コミット内容

sort: fix computation of maxDepth to avoid infinite loop

The current computation loops indefinitely if n > 1<<30 (for 32-bit ints).

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

変更の背景

Go言語の sort パッケージでは、quickSort（クイックソート）がデフォルトのソートアルゴリズムとして使用されています。クイックソートは平均的には高速ですが、最悪の場合にはO(n^2)の計算量となり、非常に遅くなる可能性があります。この最悪ケースを避けるため、多くの実装では、再帰の深さが一定の閾値を超えた場合に、より安定したO(n log n)の計算量を持つヒープソートなどの別のアルゴリズムに切り替える「イントロソート」のような戦略を採用しています。

このコミット以前のGoのsortパッケージでは、この閾値（maxDepth）を計算するロジックに問題がありました。具体的には、n（ソート対象の要素数）が非常に大きい場合、特に32ビットシステムでn > 1<<30（約10億）のような値になると、maxDepthを計算するためのループが無限に続く可能性がありました。これは、1<<uint(maxDepth)という計算がオーバーフローを起こし、予期せぬ小さな値になることで、ループの終了条件が満たされなくなるためです。この無限ループは、ソート処理が完了しない、あるいはシステムリソースを枯渇させるなどの問題を引き起こす可能性がありました。

このバグは、特に大規模なデータセットをソートする際に顕在化するため、Go言語のソート機能の信頼性とパフォーマンスを確保するために修正が必要でした。

前提知識の解説

• クイックソート (QuickSort): 分割統治法に基づくソートアルゴリズム。配列からピボット要素を選び、ピボットより小さい要素を左に、大きい要素を右に配置し、これを再帰的に繰り返します。平均計算量はO(n log n)と高速ですが、最悪計算量はO(n^2)になります。
• ヒープソート (HeapSort): 選択ソートの一種で、ヒープというデータ構造を利用します。計算量は常にO(n log n)であり、安定した性能を提供します。
• イントロソート (IntroSort): クイックソート、ヒープソート、挿入ソートを組み合わせたハイブリッドソートアルゴリズム。クイックソートを主に使用し、再帰の深さが一定の閾値を超えるとヒープソートに切り替え、要素数が非常に少なくなると挿入ソートに切り替えます。これにより、クイックソートの平均的な高速性と、ヒープソートの最悪ケースでの安定性を両立させます。Goのsortパッケージもこの戦略に似たアプローチを取っています。
• maxDepth: イントロソートにおいて、クイックソートからヒープソートに切り替える再帰の深さの閾値。通常、2 * ceil(log2(n))（nは要素数）のように計算されます。これは、クイックソートの再帰の深さがlog2(n)程度になることを期待し、その2倍の深さに達したら最悪ケースに陥っている可能性が高いと判断して切り替えるためです。
• ceil(log2(n)): nの2を底とする対数を切り上げた値。これは、n個の要素を二分探索木で表現した場合の深さ、あるいはnを1にするために2で割る回数に相当します。ビット演算では、nの最上位ビットの位置を求めることと関連します。
• ビットシフト演算 (<<, >>):
  • 1 << k: 1をkビット左にシフトする。これは2^kと同じ意味になります。
  • i >>= 1: iを1ビット右にシフトする。これはiを2で割って小数点以下を切り捨てることと同じ意味になります。この操作をiが0になるまで繰り返すことで、log2(i)の整数部分を効率的に計算できます。
• 整数オーバーフロー: 整数型で表現できる最大値を超えた場合に、値が予期せず最小値に戻ったり、負の値になったりする現象。32ビット符号なし整数（uint32）の場合、2^32 - 1が最大値であり、これを超えると0に戻ります。

技術的詳細

GoのsortパッケージのSort関数内では、クイックソートのmaxDepthを計算するために以下のループが使用されていました。

// 旧コード
maxDepth := 0
for 1<<uint(maxDepth) < n {
    maxDepth++
}
maxDepth *= 2

このコードの意図は、maxDepthがlog2(n)の整数部分（またはそれに近い値）になるように計算することです。1<<uint(maxDepth)は2^maxDepthを意味します。ループは2^maxDepthがn以上になるまでmaxDepthをインクリメントします。

しかし、この実装には以下の問題がありました。

1. 1<<uint(maxDepth)のオーバーフロー: maxDepthが大きくなりすぎると、1<<uint(maxDepth)の計算がuint型の最大値を超えてオーバーフローを起こす可能性があります。例えば、32ビットシステムでuintがuint32の場合、maxDepthが32以上になると、1<<uint(maxDepth)は0または非常に小さな値にラップアラウンドします。
2. 無限ループ: 1<<uint(maxDepth)がオーバーフローしてnよりも小さくなった場合、ループ条件1<<uint(maxDepth) < nが再び真になり、maxDepthが無限にインクリメントされ続けることになります。コミットメッセージにあるn > 1<<30という条件は、このオーバーフローが起こりやすいnの範囲を示唆しています。

この問題を解決するため、maxDepthの計算ロジックが以下のように変更されました。

// 新コード
// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 {
    maxDepth++
}
maxDepth *= 2

新しいコードでは、maxDepthの計算にfor i := n; i > 0; i >>= 1というループを使用しています。このループは、iをnから開始し、iが0になるまでiを1ビット右にシフト（2で割る）し続けます。maxDepthはループが実行された回数をカウントします。

この新しい計算方法は、nの2を底とする対数（log2(n)）の整数部分を正確かつ安全に計算します。例えば、n=8の場合、

• i=8, maxDepth=0 -> i=4, maxDepth=1
• i=4, maxDepth=1 -> i=2, maxDepth=2
• i=2, maxDepth=2 -> i=1, maxDepth=3
• i=1, maxDepth=3 -> i=0, maxDepth=4 (ループ終了) 結果としてmaxDepthは4になります。これはceil(log2(8+1))に近い値です（log2(9)は約3.17、切り上げると4）。

この方法の利点は以下の通りです。

• オーバーフローの回避: i >>= 1という操作は、iの値を常に減少させるため、オーバーフローの心配がありません。
• 正確な計算: log2(n)の整数部分を効率的に計算できます。
• 堅牢性: どのようなnの値に対しても、正しくmaxDepthを計算し、無限ループに陥ることを防ぎます。

また、コメントも2*ceil(lg(n))から2*ceil(lg(n+1))に変更されています。これは、n=0の場合にlog2(0)が未定義になるのを避けるため、あるいはnが2のべき乗の場合にlog2(n)が整数になるため、n+1とすることで常に切り上げが必要な状況を作り出し、より正確なceilの挙動を模倣するためと考えられます。

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

--- a/src/pkg/sort/sort.go
+++ b/src/pkg/sort/sort.go
@@ -186,10 +186,10 @@ func quickSort(data Interface, a, b, maxDepth int) {
 // Sort sorts data.
 // The algorithm used is not guaranteed to be a stable sort.
 func Sort(data Interface) {
-	// Switch to heapsort if depth of 2*ceil(lg(n)) is reached.
+	// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
 	n := data.Len()
 	maxDepth := 0
-	for 1<<uint(maxDepth) < n {
+	for i := n; i > 0; i >>= 1 {
 		maxDepth++
 	}
 	maxDepth *= 2

コアとなるコードの解説

変更はsrc/pkg/sort/sort.goファイル内のSort関数にあります。

変更前:

// Switch to heapsort if depth of 2*ceil(lg(n)) is reached.
n := data.Len()
maxDepth := 0
for 1<<uint(maxDepth) < n { // 問題のあったループ
    maxDepth++
}
maxDepth *= 2

この旧コードでは、maxDepthを計算するために1<<uint(maxDepth)という左シフト演算を使用していました。この演算は2のmaxDepth乗を計算しますが、maxDepthがuint型（通常はuint32またはuint64）のビット幅を超えると、オーバーフローが発生し、結果が予期せぬ小さな値になります。例えば、32ビットシステムでmaxDepthが32以上になると、1<<32は0になります。これにより、0 < nという条件が常に真となり、ループが無限に実行され続ける可能性がありました。

変更後:

// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 { // 新しい、安全なループ
    maxDepth++
}
maxDepth *= 2

新しいコードでは、maxDepthの計算にfor i := n; i > 0; i >>= 1というループが導入されました。

• i := n: iをソート対象の要素数nで初期化します。
• i > 0: ループはiが0になるまで続きます。
• i >>= 1: iを1ビット右にシフトします。これはiを2で割って小数点以下を切り捨てることと同じです。

このループは、nを2で割り続けることで、nが何回2で割れるか（つまりlog2(n)の整数部分）をmaxDepthにカウントします。この方法はオーバーフローの心配がなく、どのようなnの値に対しても安全かつ正確にmaxDepthを計算できます。

また、コメントが2*ceil(lg(n))から2*ceil(lg(n+1))に変更されました。これは、n=0の場合のlog2(0)の未定義を避けるため、またはnが2のべき乗の場合でも常に切り上げが必要な状況を明示するためと考えられます。

関連リンク

• Go CL 5848067: sort: fix computation of maxDepth to avoid infinite loop

参考にした情報源リンク

• Go言語のsortパッケージのドキュメントやソースコード
• クイックソート、ヒープソート、イントロソートに関する一般的なアルゴリズムの解説
• ビットシフト演算と対数計算の関係に関する情報
• 整数オーバーフローに関する一般的なプログラミングの知識