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

このコミットは、Goランタイムにおけるselect文の実装において、チャネルのロック順序を決定するためのソートアルゴリズムをバブルソートからヒープソートに置き換えるものです。これにより、ソートの計算量が改善され、select文のパフォーマンスが向上します。

コミット

commit cb32ea9c195929d2cc9fb60192c1d1aea2e34a98
Author: Russ Cox <rsc@golang.org>
Date:   Tue Feb 19 10:15:13 2013 -0500

    runtime: replace bubble sort with heap sort in select
    
    R=golang-dev, agl
    CC=golang-dev
    https://golang.org/cl/7304106

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

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

元コミット内容

runtime: replace bubble sort with heap sort in select

このコミットは、Goランタイムのselect文の実装において、バブルソートをヒープソートに置き換えることを目的としています。

変更の背景

Go言語のselect文は、複数のチャネル操作を同時に待機し、準備ができた最初のチャネル操作を実行するための強力なプリミティブです。select文が複数のチャネルを扱う際、デッドロックを防ぐために、チャネルをロックする順序を決定する必要があります。この順序は、チャネルのアドレスに基づいて決定されるのが一般的です。

以前の実装では、このチャネルのロック順序を決定するためにバブルソートが使用されていました。バブルソートは実装が単純である一方で、最悪の場合および平均の場合の計算量がO(n^2)と効率が悪く、多数のチャネルを扱うselect文のパフォーマンスに影響を与える可能性がありました。特に、チャネルの数が増えるにつれて、ソートにかかる時間が非線形に増加し、ランタイムのボトルネックとなることが懸念されました。

このコミットの背景には、select文のパフォーマンス改善という明確な目標があります。ヒープソートは、計算量がO(n log n)であり、スタック使用量が一定であるため、より効率的で安定したパフォーマンスを提供します。これにより、select文が多数のチャネルを扱う場合でも、ソートによるオーバーヘッドを最小限に抑え、全体的なランタイムの応答性を向上させることが期待されます。

前提知識の解説

Goのselect文

Goのselect文は、複数の通信操作（チャネルの送受信）を待機し、そのうちのいずれかが準備できたときにその操作を実行するための構文です。select文は、Goにおける並行処理の重要な要素であり、デッドロックを回避しつつ、複数のチャネルからのイベントを効率的に処理するために使用されます。

select {
case <-ch1:
    // ch1 から値を受信
case ch2 <- value:
    // ch2 へ値を送信
default:
    // どのチャネルも準備できていない場合
}

チャネルのロックとデッドロック

Goのチャネルは、並行に実行されるゴルーチン間の安全な通信を可能にするために、内部的にロック機構を使用しています。複数のチャネルを同時に操作する場合（特にselect文のように）、異なるチャネルのロックを異なる順序で取得しようとすると、デッドロックが発生する可能性があります。デッドロックとは、複数のゴルーチンがお互いに相手が保持しているリソースの解放を待ち続け、結果としてどのゴルーチンも処理を進められなくなる状態を指します。

この問題を回避するため、Goランタイムは、select文で扱われるすべてのチャネルを、そのメモリアドレスに基づいて一貫した順序でロックするようにしています。これにより、ロックの取得順序が常に一定になり、デッドロックの発生を防ぎます。

ソートアルゴリズム

• バブルソート (Bubble Sort): 隣接する要素を比較し、順序が逆であれば交換するという操作を繰り返すことで、要素を整列させるアルゴリズムです。実装が非常に単純ですが、計算量は最悪の場合および平均の場合でO(n^2)と効率が悪いです。要素数が少ない場合には問題になりませんが、要素数が増えるにつれて処理時間が急激に増加します。

• ヒープソート (Heap Sort): ヒープというデータ構造（親要素が子要素よりも常に大きいか小さいという条件を満たす木構造）を利用したソートアルゴリズムです。計算量は最悪の場合でもO(n log n)であり、安定したパフォーマンスを提供します。インプレースソート（追加の作業領域が少ない）であり、スタック使用量も一定であるため、メモリ効率も良いとされています。

技術的詳細

このコミットは、src/pkg/runtime/chan.cファイル内のselectgo関数におけるチャネルのソートロジックを変更しています。selectgo関数は、Goのselect文のランタイム実装を担当しています。

変更の核心は、sel->lockorderという配列（チャネルのポインタを格納）をソートする部分です。この配列は、select文が操作するチャネルのロック順序を決定するために使用されます。

元のコードでは、ネストされたループを持つバブルソートに似たアルゴリズムが使用されていました。具体的には、各要素を挿入ソートのように適切な位置に移動させることでソートを行っていました。

// Original (simplified)
for(i=0; i<sel->ncase; i++) {
    c = sel->scase[i].chan;
    for(j=i; j>0 && sel->lockorder[j-1] >= c; j--)
        sel->lockorder[j] = sel->lockorder[j-1];
    sel->lockorder[j] = c;
}

このコードは、実際には挿入ソートの一種であり、その計算量はO(n^2)です。

新しい実装では、この部分がヒープソートに置き換えられました。ヒープソートは、以下の2つの主要なフェーズで構成されます。

1. ヒープ構築 (Heapify): 配列の要素をヒープのプロパティ（親が子より大きい/小さい）を満たすように再配置します。このコミットでは、sel->lockorder配列に要素を一つずつ追加しながら、ヒープのプロパティを維持するようにしています。これは、要素をヒープに挿入する操作に相当します。

   // Heap construction phase (simplified)
   for(i=0; i<sel->ncase; i++) {
       j = i;
       c = sel->scase[j].chan;
       while(j > 0 && sel->lockorder[k=(j-1)/2] < c) { // Compare with parent
           sel->lockorder[j] = sel->lockorder[k]; // Move parent down
           j = k;
       }
       sel->lockorder[j] = c; // Place element
   }
   

   この部分は、最大ヒープを構築しています。sel->lockorder[k=(j-1)/2]は親ノードを指し、c（現在の要素）が親より大きい場合、親を下に移動させてcを上に持ち上げています。

2. ソート (Sortdown): ヒープの根（最大値または最小値）を配列の末尾に移動させ、残りの要素でヒープを再構築するという操作を繰り返します。これにより、ソートされた配列が完成します。

   // Sortdown phase (simplified)
   for(i=sel->ncase; i-->0; ) { // Iterate from end to beginning
       c = sel->lockorder[i]; // Current largest element (from previous step)
       sel->lockorder[i] = sel->lockorder[0]; // Move root (largest) to current position
       j = 0; // Start from root
       for(;;) {
           k = j*2+1; // Left child
           if(k >= i) // No children or beyond sorted part
               break;
           if(k+1 < i && sel->lockorder[k] < sel->lockorder[k+1]) // Right child exists and is larger
               k++; // Use right child
           if(c < sel->lockorder[k]) { // Current element is smaller than child
               sel->lockorder[j] = sel->lockorder[k]; // Move child up
               j = k; // Move down to child's position
               continue;
           }
           break; // Correct position found
       }
       sel->lockorder[j] = c; // Place element
   }
   

   この部分は、ヒープの根（最大値）を配列の末尾に移動させ、残りの要素でヒープを再構築する操作を繰り返しています。これにより、配列が降順にソートされます。チャネルのアドレスはポインタ値であり、その大小関係でソートされるため、降順でも昇順でも一貫した順序が得られれば問題ありません。

この変更により、ソートの計算量がO(n^2)からO(n log n)に改善され、特に多数のチャネルを扱うselect文のパフォーマンスが大幅に向上します。また、ヒープソートはスタック使用量が一定であるため、メモリ効率の面でも有利です。

コメントアウトされたデバッグコード（runtime·printfとruntime·throwを含む部分）は、ソートが正しく行われているかを確認するためのもので、本番コードには含まれません。

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

変更はsrc/pkg/runtime/chan.cファイル内のselectgo関数に集中しています。

--- a/src/pkg/runtime/chan.c
+++ b/src/pkg/runtime/chan.c
@@ -840,7 +840,7 @@ static void*
 selectgo(Select **selp)
 {
 	Select *sel;
-	uint32 o, i, j;
+	uint32 o, i, j, k; // 'k' variable added for heap sort
 	Scase *cas, *dfl;
 	Hchan *c;
 	SudoG *sg;
@@ -874,12 +874,42 @@ selectgo(Select **selp)
 	}
 
 	// sort the cases by Hchan address to get the locking order.
+	// simple heap sort, to guarantee n log n time and constant stack footprint.
 	for(i=0; i<sel->ncase; i++) {
-		c = sel->scase[i].chan;
-		for(j=i; j>0 && sel->lockorder[j-1] >= c; j--)
-			sel->lockorder[j] = sel->lockorder[j-1];
+		j = i;
+		c = sel->scase[j].chan;
+		while(j > 0 && sel->lockorder[k=(j-1)/2] < c) {
+			sel->lockorder[j] = sel->lockorder[k];
+			j = k;
+		}
 		sel->lockorder[j] = c;
 	}
+	for(i=sel->ncase; i-->0; ) {
+		c = sel->lockorder[i];
+		sel->lockorder[i] = sel->lockorder[0];
+		j = 0;
+		for(;;) {
+			k = j*2+1;
+			if(k >= i)
+				break;
+			if(k+1 < i && sel->lockorder[k] < sel->lockorder[k+1])
+				k++;
+			if(c < sel->lockorder[k]) {
+				sel->lockorder[j] = sel->lockorder[k];
+				j = k;
+				continue;
+			}
+			break;
+		}
+		sel->lockorder[j] = c;
+	}
+	/*
+	for(i=0; i+1<sel->ncase; i++)
+		if(sel->lockorder[i] > sel->lockorder[i+1]) {
+			runtime·printf("i=%d %p %p\n", i, sel->lockorder[i], sel->lockorder[i+1]);
+			runtime·throw("select: broken sort");
+		}
+	*/
 	sellock(sel);
 
 loop:

コアとなるコードの解説

1. 変数kの追加: uint32 o, i, j;がuint32 o, i, j, k;に変更され、ヒープソートの実装に必要なインデックス変数kが追加されました。

2. バブルソート（挿入ソート）部分の削除: 以下の元のソートロジックが削除されました。

   for(i=0; i<sel->ncase; i++) {
       c = sel->scase[i].chan;
       for(j=i; j>0 && sel->lockorder[j-1] >= c; j--)
           sel->lockorder[j] = sel->lockorder[j-1];
       sel->lockorder[j] = c;
   }
   

   これは、各要素をソート済み部分に挿入していく挿入ソートの典型的な実装です。

3. ヒープソートの実装: 削除されたソートロジックの代わりに、ヒープソートの2つのフェーズが追加されました。

   • ヒープ構築フェーズ: 最初のforループ（for(i=0; i<sel->ncase; i++) { ... }）は、sel->lockorder配列を最大ヒープとして構築します。 j = i;で現在の要素のインデックスを初期化し、c = sel->scase[j].chan;でチャネルポインタを取得します。 while(j > 0 && sel->lockorder[k=(j-1)/2] < c)ループは、現在の要素cが親ノード（sel->lockorder[k]）よりも大きい間、親ノードを下に移動させ（sel->lockorder[j] = sel->lockorder[k];）、現在の要素のインデックスを親のインデックスに更新します（j = k;）。これにより、cがヒープの適切な位置に「浮上」します。 最終的にsel->lockorder[j] = c;でcをその位置に配置します。

   • ソートフェーズ: 2番目のforループ（for(i=sel->ncase; i-->0; ) { ... }）は、ヒープから最大要素を一つずつ取り出し、配列の末尾から順に配置することでソートを完了させます。 c = sel->lockorder[i];で現在のヒープの最大要素（ソート済み部分の先頭）を一時的に保存し、sel->lockorder[i] = sel->lockorder[0];でヒープの根（現在の最大値）を配列の現在の末尾に移動させます。 j = 0;で根から開始し、内部のfor(;;)ループでヒープの再構築（heapify down）を行います。 k = j*2+1;で左の子ノードのインデックスを計算します。 if(k >= i)は、子ノードが存在しないか、ソート済み部分を超えている場合にループを終了します。 if(k+1 < i && sel->lockorder[k] < sel->lockorder[k+1]) k++;は、右の子ノノードが存在し、かつ左の子ノードよりも大きい場合に、より大きい方の子ノードを選択します。 if(c < sel->lockorder[k])は、一時的に保存した要素cが、選択された子ノードよりも小さい場合に、子ノードを上に移動させ（sel->lockorder[j] = sel->lockorder[k];）、現在のインデックスを子ノードのインデックスに更新します（j = k;）。これを繰り返すことで、cがヒープの適切な位置に「沈降」します。 最終的にsel->lockorder[j] = c;でcをその位置に配置します。

4. デバッグコードのコメントアウト: ソートが正しく行われたかを確認するためのデバッグ用のコメントアウトされたコードブロックが残されています。これは、ソート後のsel->lockorder配列が昇順になっているかをチェックし、問題があればランタイムエラーを発生させるものです。

これらの変更により、select文が多数のチャネルを扱う際のパフォーマンスが、ソートアルゴリズムの効率改善によって大幅に向上しました。

関連リンク

• Go言語のselect文に関する公式ドキュメントやチュートリアル
• Goのチャネル実装に関する詳細な技術記事やGoランタイムのソースコード解析
• ヒープソートアルゴリズムに関する一般的な情報源

参考にした情報源リンク

• Go言語の公式ドキュメント: https://golang.org/
• Goのソースコードリポジトリ: https://github.com/golang/go
• Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/ (コミットメッセージに記載されているhttps://golang.org/cl/7304106は、このGerritの変更リストへのリンクです。)
• ヒープソートに関する一般的なアルゴリズムの教科書やオンラインリソース (例: Wikipedia, GeeksforGeeksなど)
• バブルソートに関する一般的なアルゴリズムの教科書やオンラインリソース
• Goのチャネルと並行処理に関するブログ記事や解説記事