Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の標準ライブラリ sync パッケージ内の Cond (条件変数) の実装を大幅に改善するものです。主な目的は、パフォーマンスの向上とメモリ割り当ての削減、そして Cond オブジェクトが誤ってコピーされた場合にそれを検出しパニックを発生させるメカニズムの導入です。

コミット

commit 5a20b4a6a9dcf26a402edfe352aa1e8564f2fb01
Author: Dmitriy Vyukov <dvyukov@google.com>
Date:   Tue Aug 13 14:45:36 2013 +0400

    sync: faster Cond
    The new version does not require any memory allocations and is 30-50% faster.
    Also detect and painc if Cond is copied after first.
    
    benchmark            old ns/op    new ns/op    delta
    BenchmarkCond1             317          195  -38.49%
    BenchmarkCond1-2           875          607  -30.63%
    BenchmarkCond1-4          1116          548  -50.90%
    BenchmarkCond1-8          1013          613  -39.49%
    BenchmarkCond1-16          983          450  -54.22%
    BenchmarkCond2             559          352  -37.03%
    BenchmarkCond2-2          1916         1378  -28.08%
    BenchmarkCond2-4          1518         1322  -12.91%
    BenchmarkCond2-8          2313         1291  -44.19%
    BenchmarkCond2-16         1885         1078  -42.81%
    BenchmarkCond4            1070          614  -42.62%
    BenchmarkCond4-2          4899         3047  -37.80%
    BenchmarkCond4-4          3813         3006  -21.16%
    BenchmarkCond4-8          3605         3045  -15.53%
    BenchmarkCond4-16         4148         2637  -36.43%
    BenchmarkCond8            2086         1264  -39.41%
    BenchmarkCond8-2          9961         6736  -32.38%
    BenchmarkCond8-4          8135         7689   -5.48%
    BenchmarkCond8-8          9623         7517  -21.89%
    BenchmarkCond8-16        11661         8093  -30.60%
    
    R=sougou, rsc, bradfitz, r
    CC=golang-dev
    https://golang.org/cl/11573043

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

https://github.com/golang/go/commit/5a20b4a6a9dcf26a402edfe352aa1e8564f2fb01

元コミット内容

このコミットは、Go言語の sync.Cond 型の内部実装を刷新し、そのパフォーマンスを大幅に向上させるとともに、誤用を防ぐためのチェックを追加します。具体的には、以下の点が変更されています。

  1. パフォーマンスの向上: Cond の Wait, Signal, Broadcast メソッドの実行速度が30%から50%改善されました。これは、内部で利用されるセマフォの実装を最適化し、メモリ割り当てを不要にすることで達成されています。
  2. メモリ割り当ての削減: 以前の Cond 実装では、内部でセマフォを表現するために new(uint32) を使用しており、これがヒープ割り当てを発生させていました。新しい実装では、この割り当てが不要になり、ガベージコレクションの負荷が軽減されます。
  3. Cond のコピー検出: sync.Cond は、その性質上、コピーして使用すべきではない型です。コピーされると、内部状態が正しく共有されず、デッドロックや予期せぬ動作を引き起こす可能性があります。このコミットでは、Cond が最初の使用後にコピーされたことを検出し、パニックを発生させる copyChecker が導入されました。

コミットメッセージには、変更前後のベンチマーク結果が詳細に記載されており、その性能向上が数値で示されています。

変更の背景

Go言語の sync.Cond は、複数のゴルーチンが特定の条件が満たされるまで待機し、その条件が満たされたときに他のゴルーチンによって通知されるための同期プリミティブです。これは、生産者-消費者問題や、リソースが利用可能になるまで待機するようなシナリオでよく使用されます。

しかし、Goの初期の sync.Cond 実装は、パフォーマンスのボトルネックとなる可能性がありました。特に、Wait メソッドが呼び出されるたびに内部でセマフォのためのメモリ割り当てが発生し、これが高頻度で Cond を使用するアプリケーションのパフォーマンスに影響を与えていました。また、Cond は構造体であるため、誤って値渡しでコピーされてしまうと、期待通りの同期動作が行われなくなるという問題も存在しました。

このコミットは、これらの課題に対処するために行われました。Dmitriy Vyukov氏（Goランタイムの主要な貢献者の一人）は、より効率的なセマフォの実装を導入し、Cond の内部構造を再設計することで、これらの問題を解決しようとしました。特に、メモリ割り当てをなくすことで、ガベージコレクションのオーバーヘッドを減らし、全体的なスループットを向上させることを目指しました。また、Cond の誤用を防ぐための copyChecker の導入は、Goの同期プリミティブの堅牢性を高める上で重要な変更です。

前提知識の解説

このコミットを理解するためには、以下の概念について基本的な知識が必要です。

1. 条件変数 (Condition Variable)

条件変数は、スレッド（Goではゴルーチン）が特定の条件が満たされるまで待機し、他のスレッドがその条件が満たされたことを通知するために使用される同期プリミティブです。通常、ミューテックスと組み合わせて使用されます。

  • Wait(): 条件変数を待機するメソッド。呼び出し元はミューテックスを解放し、条件が満たされるまでブロックされます。条件が満たされ、通知を受け取ると、ミューテックスを再取得して処理を続行します。
  • Signal(): 待機しているゴルーチンのうち、1つを起床させるメソッド。
  • Broadcast(): 待機しているすべてのゴルーチンを起床させるメソッド。

Goの sync.Cond は、Locker インターフェース（通常は sync.Mutex または sync.RWMutex）と関連付けられています。Wait を呼び出す前に Locker をロックし、Wait が返った後も Locker はロックされた状態になります。

2. セマフォ (Semaphore)

セマフォは、リソースへのアクセスを制御するための同期プリミティブです。カウンタを持ち、P 操作（待機、リソース取得）でカウンタを減らし、V 操作（解放、リソース返却）でカウンタを増やします。カウンタが0の場合、P 操作はブロックされます。Goのランタイムでは、ゴルーチンのスケジューリングと同期のために内部的にセマフォが使用されます。

3. ゴルーチン (Goroutine) とスケジューラ

ゴルーチンはGoの軽量な実行単位です。Goランタイムのスケジューラが、OSのスレッド上で多数のゴルーチンを効率的に多重化して実行します。ゴルーチンがブロックされると、スケジューラは自動的にそのゴルーチンを待機させ、他の実行可能なゴルーチンにCPUを割り当てます。

4. sync/atomic パッケージ

sync/atomic パッケージは、アトミック操作（不可分操作）を提供します。これにより、複数のゴルーチンが同時に共有メモリにアクセスしても、データ競合が発生しないように安全に値を読み書きできます。AddUint32 や CompareAndSwapUint32 などがその例です。

5. unsafe パッケージ

unsafe パッケージは、Goの型安全性をバイパスする機能を提供します。ポインタ演算や、異なる型の間の変換など、通常では許可されない操作が可能になります。これは非常に強力ですが、誤用するとプログラムの安定性や移植性を損なう可能性があるため、慎重に使用する必要があります。このコミットでは、copyChecker の実装で unsafe.Pointer が使用されています。

6. runtime パッケージと sema.goc

runtime パッケージはGoランタイムのコア部分であり、ガベージコレクタ、スケジューラ、同期プリミティブなどの低レベルな機能を提供します。sema.goc は、C言語で書かれたGoランタイムのセマフォ実装の一部です。Goの sync パッケージは、これらの低レベルなランタイム関数を呼び出すことで、高レベルな同期プリミティブを実現しています。

技術的詳細

このコミットの技術的な核心は、sync.Cond の内部で使われるセマフォの実装を、従来の「世代管理」方式から、よりシンプルで効率的な「単一のセマフォと待機者数カウンタ」方式に切り替えた点にあります。

従来の sync.Cond の問題点

以前の sync.Cond は、oldWaiters, oldSema, newWaiters, newSema というフィールドを持っていました。これは、Signal が呼び出されたときに、その時点で待機していたゴルーチンと、Signal の後に Wait を呼び出したゴルーチンを区別するために「世代」を管理するアプローチでした。

  • Wait() が呼ばれると、newSema に対応するセマフォで待機し、newWaiters をインクリメントします。もし newSema が nil であれば、new(uint32) で新しいセマフォを割り当てていました。これがメモリ割り当ての原因でした。
  • Signal() が呼ばれると、まず oldWaiters が0で newWaiters が1以上の場合、new 世代を old 世代に「昇格」させます。その後、oldSema に対応するセマフォを解放し、oldWaiters をデクリメントします。
  • Broadcast() は、oldSema と newSema の両方で待機しているすべてのゴルーチンを起床させます。

この世代管理は、複雑であり、特に new(uint32) による動的なメモリ割り当てがパフォーマンスのオーバーヘッドとなっていました。

新しい sync.Cond の実装

新しい実装では、sync.Cond の内部構造が以下のように変更されました。

type Cond struct {
	L Locker
	sema    syncSema // 新しいセマフォ構造体
	waiters uint32   // 待機中のゴルーチンの数
	checker copyChecker // コピー検出用
}

  1. syncSema の導入: src/pkg/sync/runtime.go で type syncSema [3]uintptr として定義され、src/pkg/runtime/sema.goc で SyncSema 構造体として実体が定義されています。この SyncSema は、ミューテックスと SemaWaiter のリスト（head と tail）を持つ、より汎用的なセマフォキューとして機能します。 sema.goc では、Sema が SemaWaiter にリネームされ、nrelease フィールドが追加されました。これは、セマフォの解放時に複数のゴルーチンを起床させる（または、セマフォの獲得時に複数のリソースを消費する）ためのカウンタとして機能します。

  2. runtime_Syncsemacquire と runtime_Syncsemrelease: これらの関数は、sema.goc で新しく定義された低レベルのセマフォ操作です。

    • runtime_Syncsemacquire(s *SyncSema): s で表現されるセマフォを獲得しようとします。もし利用可能な解放がない場合、ゴルーチンは runtime·park を呼び出してブロックされます。
    • runtime_Syncsemrelease(s *SyncSema, n uint32): s で表現されるセマフォを n 回解放します。これにより、待機中のゴルーチンが起床されます。

  3. Wait() メソッドの変更: Wait() は、atomic.AddUint32(&c.waiters, 1) で待機者数をインクリメントした後、runtime_Syncsemacquire(&c.sema) を呼び出してセマフォを獲得しようとします。これにより、従来の new(uint32) によるメモリ割り当てが不要になりました。

  4. Signal() と Broadcast() メソッドの変更: これらのメソッドは signalImpl(all bool) という内部ヘルパー関数に統合されました。

    • signalImpl は、atomic.LoadUint32(&c.waiters) で現在の待機者数を読み込み、atomic.CompareAndSwapUint32(&c.waiters, old, new) でアトミックに待機者数を更新します。
    • その後、runtime_Syncsemrelease(&c.sema, old-new) を呼び出して、必要な数のゴルーチンを起床させます。Signal の場合は1つ、Broadcast の場合はすべての待機者を起床させます。

  5. copyChecker の導入: copyChecker は、uintptr 型のフィールドで、Cond が最初に利用される際に、自身のメモリアドレスを記録します。その後、check() メソッドが呼び出されるたびに、現在のメモリアドレスが記録されたアドレスと一致するかどうかを確認します。もし一致しない場合（つまり、Cond がコピーされた場合）、panic("sync.Cond is copied") を発生させます。 このメカニズムは、unsafe.Pointer を使用してポインタと uintptr の間で変換を行うことで実現されています。Cond の Wait, Signal, Broadcast メソッドの冒頭で c.checker.check() が呼び出されるため、コピーされた Cond が使用されるとすぐに検出されます。

パフォーマンス向上とメモリ割り当て削減の理由

  • メモリ割り当ての排除: 従来の Cond は、new(uint32) を使ってセマフォをヒープに割り当てていました。新しい実装では、sync.Cond 構造体自体が syncSema を内部に持ち、この syncSema はスタック上に割り当てられるか、または Cond 構造体の一部としてヒープに割り当てられるため、Wait ごとの追加のヒープ割り当てがなくなります。これにより、ガベージコレクションの頻度が減り、パフォーマンスが向上します。
  • セマフォ操作の効率化: runtime_Syncsemacquire と runtime_Syncsemrelease は、Goランタイムの低レベルなCコードで実装されており、ゴルーチンのブロックと起床をより効率的に行います。特に、待機中のゴルーチンをキューで管理し、必要な数だけ起床させるロジックが最適化されています。
  • アトミック操作の活用: waiters カウンタを sync/atomic パッケージのアトミック操作で管理することで、ロックの粒度を細かくし、競合を減らしています。

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

このコミットにおける主要なコード変更は以下のファイルに集中しています。

  1. src/pkg/runtime/sema.goc:

    • Sema 構造体が SemaWaiter にリネームされ、nrelease フィールドが追加されました。
    • SemaRoot 構造体の head と tail フィールドの型が Sema から SemaWaiter に変更されました。
    • 新しいセマフォ構造体 SyncSema が定義されました。
    • runtime_Syncsemacquire と runtime_Syncsemrelease という新しいランタイム関数が追加され、sync.Cond の新しいセマフォ操作を実装しています。
    • runtime_Syncsemcheck が追加され、syncSema のサイズがGoとランタイムで一致しているかを確認します。

  2. src/pkg/sync/cond.go:

    • Cond 構造体から oldWaiters, oldSema, newWaiters, newSema フィールドが削除されました。
    • 代わりに sema syncSema, waiters uint32, checker copyChecker フィールドが追加されました。
    • Wait() メソッドの内部ロジックが runtime_Syncsemacquire を使用するように変更されました。
    • Signal() と Broadcast() メソッドが signalImpl ヘルパー関数を呼び出すように変更され、runtime_Syncsemrelease を使用してゴルーチンを起床させます。
    • copyChecker 型とその check() メソッドが追加され、Cond のコピーを検出します。

  3. src/pkg/sync/cond_test.go:

    • TestCondCopy という新しいテストが追加され、Cond がコピーされた場合にパニックが発生することを確認します。
    • TestRace という新しいテストが追加され、Cond を使用したゴルーチン間の競合状態をテストします。
    • 新しいベンチマーク関数 (BenchmarkCond1 から BenchmarkCond32) が追加され、新しい Cond 実装のパフォーマンスを測定します。

  4. src/pkg/sync/runtime.go:

    • syncSema 型が [3]uintptr として定義されました。これは、sema.goc で定義された SyncSema 構造体のGo側での抽象的な表現です。
    • runtime_Syncsemacquire, runtime_Syncsemrelease, runtime_Syncsemcheck のGo側の宣言が追加されました。
    • init() 関数が追加され、runtime_Syncsemcheck を呼び出して syncSema のサイズの一貫性を検証します。

コアとなるコードの解説

src/pkg/runtime/sema.goc の変更点

このファイルはGoランタイムのC言語部分であり、低レベルなセマフォ操作を定義しています。

// 変更前: typedef struct Sema Sema; struct Sema { ... };
// 変更後: typedef struct SemaWaiter SemaWaiter; struct SemaWaiter { ... };
// SemaWaiter は、セマフォを待機しているゴルーチン (G*) と、
// そのゴルーチンが解放されるべき回数 (nrelease) を保持します。
// nrelease が -1 の場合は acquire (獲得) を意味し、正の値は release (解放) を意味します。

// 新しいセマフォ構造体
typedef struct SyncSema SyncSema;
struct SyncSema
{
	Lock; // ミューテックス
	SemaWaiter*	head; // 待機者キューの先頭
	SemaWaiter*	tail; // 待機者キューの末尾
};

// Syncsemacquire は、SyncSema s 上で対応する Syncsemrelease を待ちます。
func runtime_Syncsemacquire(s *SyncSema) {
	SemaWaiter w, *wake;
	int64 t0;

	w.g = g; // 現在のゴルーチン
	w.nrelease = -1; // acquire 操作を示す
	w.next = nil;
	w.releasetime = 0;
	// ... プロファイリング関連のコード ...

	runtime·lock(s); // SyncSema をロック
	if(s->head && s->head->nrelease > 0) {
		// 待機中の release があれば、それを消費
		wake = nil;
		s->head->nrelease--;
		if(s->head->nrelease == 0) {
			// release がすべて消費されたらキューから削除
			wake = s->head;
			s->head = wake->next;
			if(s->head == nil)
				s->tail = nil;
		}
		runtime·unlock(s);
		if(wake)
			runtime·ready(wake->g); // ゴルーチンを起床
	} else {
		// 待機中の release がなければ、自身をキューに追加し、park (ブロック)
		if(s->tail == nil)
			s->head = &w;
		else
			s->tail->next = &w;
		s->tail = &w;
		runtime·park(runtime·unlock, s, "semacquire"); // ロックを解放してブロック
		// ... プロファイリング関連のコード ...
	}
}

// Syncsemrelease は、SyncSema s 上で n 個の対応する Syncsemacquire を待ちます。
func runtime_Syncsemrelease(s *SyncSema, n uint32) {
	SemaWaiter w, *wake;

	w.g = g;
	w.nrelease = (int32)n; // 解放する回数
	w.next = nil;
	w.releasetime = 0;

	runtime·lock(s); // SyncSema をロック
	while(w.nrelease > 0 && s->head && s->head->nrelease < 0) {
		// 待機中の acquire があれば、それを満たす
		wake = s->head;
		s->head = wake->next;
		if(s->head == nil)
			s->tail = nil;
		// ... プロファイリング関連のコード ...
		runtime·ready(wake->g); // ゴルーチンを起床
		w.nrelease--;
	}
	if(w.nrelease > 0) {
		// まだ解放すべき acquire が残っていれば、自身をキューに追加し、park (ブロック)
		if(s->tail == nil)
			s->head = &w;
		else
			s->tail->next = &w;
		s->tail = &w;
		runtime·park(runtime·unlock, s, "semarelease"); // ロックを解放してブロック
	} else
		runtime·unlock(s); // すべての acquire を満たしたらロックを解放
}

これらの関数は、Cond の Wait, Signal, Broadcast の基盤となる、より効率的なセマフォ操作を提供します。nrelease フィールドとキューイングメカニズムにより、メモリ割り当てなしで複数のゴルーチンの起床/ブロックを管理できます。

src/pkg/sync/cond.go の変更点

このファイルは sync.Cond 型のGo言語での実装です。

import (
	"sync/atomic"
	"unsafe"
)

type Cond struct {
	L Locker
	sema    syncSema // ランタイムのSyncSemaに対応するGo側の型
	waiters uint32   // 待機中のゴルーチンの数をアトミックに管理
	checker copyChecker // コピー検出用
}

func (c *Cond) Wait() {
	c.checker.check() // コピー検出
	// ... raceenabled の処理 ...
	atomic.AddUint32(&c.waiters, 1) // 待機者数をインクリメント
	// ... raceenabled の処理 ...
	c.L.Unlock() // 関連するLockerを解放
	runtime_Syncsemacquire(&c.sema) // ランタイムのセマフォを獲得
	c.L.Lock() // 関連するLockerを再ロック
}

func (c *Cond) Signal() {
	c.signalImpl(false) // 1つのゴルーチンを起床
}

func (c *Cond) Broadcast() {
	c.signalImpl(true) // すべてのゴルーチンを起床
}

func (c *Cond) signalImpl(all bool) {
	c.checker.check() // コピー検出
	// ... raceenabled の処理 ...
	for {
		old := atomic.LoadUint32(&c.waiters) // 現在の待機者数をアトミックに読み込み
		if old == 0 {
			// 待機者がいなければ何もしない
			// ... raceenabled の処理 ...
			return
		}
		new := old - 1 // Signal の場合、1つ減らす
		if all {
			new = 0 // Broadcast の場合、すべて減らす
		}
		if atomic.CompareAndSwapUint32(&c.waiters, old, new) {
			// 待機者数をアトミックに更新できたら
			// ... raceenabled の処理 ...
			runtime_Syncsemrelease(&c.sema, old-new) // ランタイムのセマフォを解放してゴルーチンを起床
			return
		}
		// CAS が失敗したらループを続行 (他のゴルーチンが waiters を変更したため)
	}
}

// copyChecker はオブジェクトのコピーを検出するためのバックポインタを保持します。
type copyChecker uintptr

func (c *copyChecker) check() {
	// uintptr(*c) は、以前に記録されたアドレス。
	// uintptr(unsafe.Pointer(c)) は、現在の copyChecker のアドレス。
	// 最初の条件: 以前に記録されたアドレスが現在の copyChecker のアドレスと異なる場合 (コピーされた可能性)
	// かつ、2番目の条件: アトミックに 0 から現在のアドレスに設定しようとして失敗した場合 (既に設定済みで、かつアドレスが異なる)
	// かつ、3番目の条件: 以前に記録されたアドレスが現在の copyChecker のアドレスと異なる場合 (再度確認)
	if uintptr(*c) != uintptr(unsafe.Pointer(c)) &&
		!atomic.CompareAndSwapUintptr((*uintptr)(c), 0, uintptr(unsafe.Pointer(c))) &&
		uintptr(*c) != uintptr(unsafe.Pointer(c)) {
		panic("sync.Cond is copied") // コピーされたことを検出したらパニック
	}
}

Wait メソッドは、c.L.Unlock() で関連するミューテックスを解放し、runtime_Syncsemacquire を呼び出してゴルーチンをブロックします。起床後、c.L.Lock() でミューテックスを再取得します。 signalImpl は、waiters カウンタをアトミックに操作し、runtime_Syncsemrelease を呼び出すことで、必要な数のゴルーチンを効率的に起床させます。 copyChecker は、Cond が値渡しでコピーされるという一般的な誤用パターンを検出し、早期に問題を報告することで、デバッグを容易にします。

関連リンク

参考にした情報源リンク

  • Goのコミット履歴 (GitHub): https://github.com/golang/go/commits/master
  • Goのコードレビューシステム (Gerrit): https://go-review.googlesource.com/ (コミットメッセージに記載されている https://golang.org/cl/11573043 はGerritの変更リストへのリンクです)
  • Goのランタイムに関するブログ記事やドキュメント (一般的なGoの知識として)
  • 条件変数とセマフォに関する一般的な並行プログラミングの概念
  • Dmitriy Vyukov氏のGoランタイムに関する他の貢献 (例: Goスケジューラ、メモリモデルなど)I have generated the detailed technical explanation of the commit as requested, following all the specified instructions and chapter structure. The output is in Markdown format and is printed to standard output only.