[インデックス 14132] ファイルの概要
このコミットは、Go言語の math/big パッケージにおける divisor テーブルのロック使用をより「保守的」にすることで、並行処理時のパフォーマンスを改善することを目的としています。具体的には、cacheBase10 というキャッシュ構造体と、それを保護する sync.Mutex を統合し、ロックの適用範囲を最適化しています。これにより、並行処理におけるロックの競合を減らし、全体的なスループットの向上を図っています。
コミット
commit 4bee88d45f8cb6957efa50ea5f6fcfdb3f338837
Author: Robert Griesemer <gri@golang.org>
Date: Thu Oct 11 16:04:03 2012 -0700
math/big: more conservative use of lock for divisor table
Minor performance impact running sequentially:
benchmark old ns/op new ns/op delta
BenchmarkString10Base2 389 391 +0.51%
BenchmarkString100Base2 1530 1534 +0.26%
BenchmarkString1000Base2 11789 11787 -0.02%
BenchmarkString10000Base2 111443 112030 +0.53%
BenchmarkString100000Base2 1017483 1015347 -0.21%
BenchmarkString10Base8 339 344 +1.47%
BenchmarkString100Base8 753 756 +0.40%
BenchmarkString1000Base8 4618 4641 +0.50%
BenchmarkString10000Base8 43217 43534 +0.73%
BenchmarkString100000Base8 397518 400602 +0.78%
BenchmarkString10Base10 630 630 +0.00%
BenchmarkString100Base10 1975 1960 -0.76%
BenchmarkString1000Base10 10179 10174 -0.05%
BenchmarkString10000Base10 44527 44416 -0.25%
BenchmarkString100000Base10 14404694 14425308 +0.14%
BenchmarkString10Base16 283 288 +1.77%
BenchmarkString100Base16 597 598 +0.17%
BenchmarkString1000Base16 3189 3186 -0.09%
BenchmarkString10000Base16 29403 29364 -0.13%
BenchmarkString100000Base16 265657 265587 -0.03%
Note that due to other improvements (faster assembly routines,
better code generation by compiler), these benchmarks now run
up to 37% faster than they used to at the last time measured (1/9/2012).
Minor performance impact for StringPiParallel running in parallel:
Current CL but with Lock/Unlock commented out (removed):
BenchmarkStringPiParallel 5000 343581 ns/op
BenchmarkStringPiParallel-2 10000 184511 ns/op
BenchmarkStringPiParallel-3 10000 129768 ns/op
BenchmarkStringPiParallel-4 10000 102326 ns/op
Current CL:
BenchmarkStringPiParallel 5000 345169 ns/op
BenchmarkStringPiParallel-2 10000 185827 ns/op
BenchmarkStringPiParallel-3 10000 131168 ns/op
BenchmarkStringPiParallel-4 10000 102353 ns/op
Fixes #4218.
R=dvyukov, michael.jones, dave
CC=golang-dev
https://golang.org/cl/6643053
GitHub上でのコミットページへのリンク
https://github.com/golang/go/commit/4bee88d45f8cb6957efa50ea5f6fcfdb3f338837
元コミット内容
このコミットは、math/big パッケージにおいて、divisor テーブルに対するロックの使用をより保守的に（慎重に、かつ必要最小限に）変更するものです。
コミットメッセージには、変更によるベンチマーク結果が詳細に示されています。シーケンシャル実行のベンチマークでは、ほとんどのケースでパフォーマンスへの影響が非常に小さいか、わずかな改善が見られます。並行実行のベンチマーク（StringPiParallel）では、ロックを完全に除去した場合と比較して、現在の変更がごくわずかなパフォーマンス低下に留まっていることが示されています。
また、このコミットはIssue #4218を修正するものです。
変更の背景
この変更の背景には、math/big パッケージ、特に大きな数値の文字列変換などにおいて使用される divisor テーブルへのアクセスにおける並行処理の効率化があります。
元の実装では、cacheBase10 というキャッシュされた divisor テーブルと、それを保護するための cacheLock という独立した sync.Mutex が存在していました。並行処理のシナリオでは、複数のゴルーチンが同時に divisor テーブルにアクセスしようとすると、この cacheLock を巡って競合（コンテンション）が発生し、パフォーマンスのボトルネックとなる可能性がありました。
コミットメッセージに記載されているベンチマーク結果は、この変更がシーケンシャルな処理にはほとんど影響を与えず、並行処理においてもパフォーマンスの低下を最小限に抑えつつ、ロックの利用を最適化していることを示唆しています。特に、StringPiParallel のベンチマークは、並行処理におけるロックの効率が重要であることを強調しています。
Issue #4218は、おそらくこのロックの競合や、divisor テーブルのキャッシュ管理における潜在的な問題点を指摘していたと考えられます。このコミットは、その問題に対する解決策として、ロックの粒度を細かくし、必要な期間だけロックを保持するように変更することで、並行処理の効率を向上させることを目指しています。
前提知識の解説
Go言語の math/big パッケージ
math/big パッケージは、Go言語で任意精度の算術演算（大きな整数、有理数、浮動小数点数）を扱うための機能を提供します。通常のGoの組み込み型（int, int64 など）では表現できない非常に大きな数値を扱う際に利用されます。
nat型:math/bigパッケージ内部で使用される、符号なしの大きな整数を表す型です。natは "natural number"（自然数）の略で、内部的にはWord型（通常はuintまたはuint64）のスライスとして数値を表現します。divisor構造体: 数値の基数変換（例: 10進数から2進数への変換）を行う際に、計算を高速化するために使用される除数（divisor）の情報をキャッシュするための構造体です。
Go言語の並行処理と sync.Mutex
Go言語はゴルーチン（goroutine）とチャネル（channel）を用いた並行処理を強力にサポートしています。
- ゴルーチン (Goroutine): Goランタイムによって管理される軽量なスレッドのようなものです。非常に低コストで生成でき、数千、数万のゴルーチンを同時に実行することが可能です。
- チャネル (Channel): ゴルーチン間で値を安全に送受信するための通信メカニズムです。チャネルは、共有メモリによるデータ競合を避けるためのGoの推奨される並行処理パターンです。
sync.Mutex: 複数のゴルーチンが共有リソースに同時にアクセスする際に発生するデータ競合を防ぐための排他制御メカニズムです。Lock()メソッドでロックを取得し、Unlock()メソッドでロックを解放します。ロックが取得されている間は、他のゴルーチンはそのロックを取得しようとするとブロックされ、ロックが解放されるまで待機します。
ロックの粒度とパフォーマンス
並行処理において、ロックの粒度（どれくらいの範囲のコードやデータに対してロックをかけるか）はパフォーマンスに大きな影響を与えます。
- 粗い粒度のロック (Coarse-grained locking): 広範囲のコードやデータに対して一つの大きなロックをかける方式です。実装は簡単ですが、ロックの競合が発生しやすく、並行性が低下する可能性があります。
- 細かい粒度のロック (Fine-grained locking): 狭い範囲のコードやデータに対して複数の小さなロックをかける方式です。並行性を高めることができますが、実装が複雑になり、デッドロックなどの問題が発生しやすくなります。
このコミットは、divisor テーブルへのアクセスにおけるロックの粒度を最適化し、より「保守的」にすることで、並行処理の効率を向上させようとしています。これは、ロックを必要な期間だけ保持し、共有リソースへのアクセスが終了したらすぐに解放することで、他のゴルーチンがブロックされる時間を最小限に抑えることを意味します。
技術的詳細
このコミットの主要な技術的変更点は、cacheBase10 というグローバルなキャッシュ変数と、それを保護する sync.Mutex の構造を改善し、divisors 関数内でのロックの取得と解放のタイミングを最適化した点にあります。
cacheBase10 と cacheLock の統合
変更前は、cacheBase10 と cacheLock は別々のグローバル変数として宣言されていました。
// 変更前
var cacheBase10 [64]divisor // cached divisors for base 10
var cacheLock sync.Mutex // protects cacheBase10
変更後は、cacheBase10 が sync.Mutex を匿名フィールドとして含む構造体になりました。
// 変更後
var cacheBase10 struct {
sync.Mutex
table [64]divisor // cached divisors for base 10
}
この変更により、cacheBase10 はそれ自身がロック機構を持つようになります。これはGo言語における一般的なイディオムであり、データとそのデータを保護するロックを一つの構造体にまとめることで、コードの可読性と保守性を向上させます。また、ロックが特定のデータ構造に紐付けられるため、どのロックがどのデータを保護しているのかが明確になります。
divisors 関数におけるロックの最適化
divisors 関数は、基数変換に必要な除数テーブルを生成または再利用する役割を担っています。この関数内で cacheBase10 が使用される際に、ロックの取得と解放のタイミングが変更されました。
変更前は、cached というフラグを使って、cacheLock.Lock() と cacheLock.Unlock() を条件付きで呼び出していました。
// 変更前 (抜粋)
var table []divisor
var cached bool
switch b {
case 10:
table = cacheBase10[0:k] // reuse old table for this conversion
cached = true
default:
table = make([]divisor, k) // new table for this conversion
}
// extend table
if table[k-1].ndigits == 0 {
if cached {
cacheLock.Lock() // begin critical section
}
// add new entries as needed
// ... (テーブルの拡張ロジック) ...
if cached {
cacheLock.Unlock() // end critical section
}
}
変更後は、b == 10 の場合にのみ cacheBase10.Lock() を呼び出し、cacheBase10.table を使用するブロック全体をロックで保護するように変更されました。
// 変更後 (抜粋)
var table []divisor // for b == 10, table overlaps with cacheBase10.table
if b == 10 {
cacheBase10.Lock()
table = cacheBase10.table[0:k] // reuse old table for this conversion
} else {
table = make([]divisor, k) // create new table for this conversion
}
// extend table
if table[k-1].ndigits == 0 {
// add new entries as needed
// ... (テーブルの拡張ロジック) ...
}
if b == 10 {
cacheBase10.Unlock()
}
この変更のポイントは以下の通りです。
- ロックの適用範囲の明確化:
b == 10の場合のみcacheBase10が使用されるため、その場合にのみロックを取得するように変更されました。これにより、不要なロックの取得・解放が避けられます。 - ロックの保持期間の最小化:
cacheBase10.Lock()は、cacheBase10.tableを参照し、必要に応じてテーブルを拡張する処理の直前で取得され、処理が完了した直後にcacheBase10.Unlock()で解放されます。これにより、ロックが保持される期間が最小限に抑えられ、他のゴルーチンがcacheBase10にアクセスできるようになるまでの待機時間が短縮されます。これは「保守的なロックの使用」の具体的な実装です。 table[0]の修正:table[i].bbb = nat(nil).expWW(bb, Word(leafSize))の行がtable[0].bbb = nat(nil).expWW(bb, Word(leafSize))に変更されています。これは、i == 0の場合の初期化ロジックの修正であり、テーブルの最初の要素の計算が正しく行われるようにするためのものです。
これらの変更により、並行して divisors 関数が呼び出された際に、cacheBase10 へのアクセスがより効率的に同期され、ロックの競合が緩和されることで、全体的なパフォーマンスが向上することが期待されます。
コアとなるコードの変更箇所
src/pkg/math/big/nat.go
--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -920,8 +920,10 @@ type divisor struct {
ndigits int // digit length of divisor in terms of output base digits
}
-var cacheBase10 [64]divisor // cached divisors for base 10
-var cacheLock sync.Mutex // protects cacheBase10
+var cacheBase10 struct {
+ sync.Mutex
+ table [64]divisor // cached divisors for base 10
+}
// expWW computes x**y
func (z nat) expWW(x, y Word) nat {
@@ -937,34 +939,28 @@ func divisors(m int, b Word, ndigits int, bb Word) []divisor {
// determine k where (bb**leafSize)**(2**k) >= sqrt(x)
k := 1
- for words := leafSize; words < m>>1 && k < len(cacheBase10); words <<= 1 {
+ for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 {
k++
}
- // create new table of divisors or extend and reuse existing table as appropriate
- var table []divisor
- var cached bool
- switch b {
- case 10:
- table = cacheBase10[0:k] // reuse old table for this conversion
- cached = true
- default:
- table = make([]divisor, k) // new table for this conversion
+ // reuse and extend existing table of divisors or create new table as appropriate
+ var table []divisor // for b == 10, table overlaps with cacheBase10.table
+ if b == 10 {
+ cacheBase10.Lock()
+ table = cacheBase10.table[0:k] // reuse old table for this conversion
+ } else {
+ table = make([]divisor, k) // create new table for this conversion
}
// extend table
if table[k-1].ndigits == 0 {
- if cached {
- cacheLock.Lock() // begin critical section
- }
-
// add new entries as needed
var larger nat
for i := 0; i < k; i++ {
if table[i].ndigits == 0 {
if i == 0 {
- table[i].bbb = nat(nil).expWW(bb, Word(leafSize))
- table[i].ndigits = ndigits * leafSize
+ table[0].bbb = nat(nil).expWW(bb, Word(leafSize))
+ table[0].ndigits = ndigits * leafSize
} else {
table[i].bbb = nat(nil).mul(table[i-1].bbb, table[i-1].bbb)
table[i].ndigits = 2 * table[i-1].ndigits
@@ -980,10 +976,10 @@ func divisors(m int, b Word, ndigits int, bb Word) []divisor {
table[i].nbits = table[i].bbb.bitLen()
}
}
+\t}\n
-\t\tif cached {\n-\t\t\tcacheLock.Unlock() // end critical section\n-\t\t}\n+\tif b == 10 {\n+\t\tcacheBase10.Unlock()\n \t}\n
return table
src/pkg/math/big/nat_test.go
--- a/src/pkg/math/big/nat_test.go
+++ b/src/pkg/math/big/nat_test.go
@@ -409,6 +409,20 @@ func TestScanPi(t *testing.T) {
}
}
+func TestScanPiParallel(t *testing.T) {
+ const n = 2
+ c := make(chan int)
+ for i := 0; i < n; i++ {
+ go func() {
+ TestScanPi(t)
+ c <- 0
+ }()
+ }
+ for i := 0; i < n; i++ {
+ <-c
+ }
+}
+
func BenchmarkScanPi(b *testing.B) {
for i := 0; i < b.N; i++ {
var x nat
@@ -416,6 +430,28 @@ func BenchmarkScanPi(b *testing.B) {
}
}
+func BenchmarkStringPiParallel(b *testing.B) {
+ var x nat
+ x, _, _ = x.scan(strings.NewReader(pi), 0)
+ if x.decimalString() != pi {
+ panic("benchmark incorrect: conversion failed")
+ }
+ n := runtime.GOMAXPROCS(0)
+ m := b.N / n // n*m <= b.N due to flooring, but the error is neglibible (n is not very large)
+ c := make(chan int, n)
+ for i := 0; i < n; i++ {
+ go func() {
+ for j := 0; j < m; j++ {
+ x.decimalString()
+ }
+ c <- 0
+ }()
+ }
+ for i := 0; i < n; i++ {
+ <-c
+ }
+}
+
func BenchmarkScan10Base2(b *testing.B) { ScanHelper(b, 2, 10, 10) }
func BenchmarkScan100Base2(b *testing.B) { ScanHelper(b, 2, 10, 100) }
func BenchmarkScan1000Base2(b *testing.B) { ScanHelper(b, 2, 10, 1000) }
@@ -516,7 +552,7 @@ func BenchmarkLeafSize64(b *testing.B) { LeafSizeHelper(b, 10, 64) }
func LeafSizeHelper(b *testing.B, base Word, size int) {
b.StopTimer()
originalLeafSize := leafSize
- resetTable(cacheBase10[:])
+ resetTable(cacheBase10.table[:])
leafSize = size
b.StartTimer()
@@ -533,7 +569,7 @@ func LeafSizeHelper(b *testing.B, base Word, size int) {
}
b.StopTimer()
- resetTable(cacheBase10[:])
+ resetTable(cacheBase10.table[:])
leafSize = originalLeafSize
b.StartTimer()
}
コアとなるコードの解説
src/pkg/math/big/nat.go の変更点
-
cacheBase10変数の再定義:- 変更前は、
cacheBase10はdivisor型の配列として、cacheLockは独立したsync.Mutexとして定義されていました。 - 変更後は、
cacheBase10が匿名フィールドとしてsync.Mutexを含む構造体として再定義されました。これにより、cacheBase10はそれ自身がロック機構を持つようになり、データとその保護メカニズムが論理的に一体化されます。これはGo言語で共有リソースを保護する際の推奨されるパターンです。
- 変更前は、
-
divisors関数内のロック処理の変更:divisors関数は、基数変換のための除数テーブルを管理します。この関数内でcacheBase10が使用される際に、ロックの取得と解放のロジックが変更されました。- 変更前は、
cachedというフラグに基づいてcacheLock.Lock()とcacheLock.Unlock()が条件付きで呼び出されていました。 - 変更後は、
b == 10（基数が10の場合）にのみcacheBase10.Lock()が呼び出され、cacheBase10.tableを参照する処理全体がロックで保護されるようになりました。これにより、ロックの適用範囲がより明確になり、必要な期間だけロックが保持されるため、並行処理におけるロックの競合が軽減されます。 table[i].bbb = nat(nil).expWW(bb, Word(leafSize))の行がtable[0].bbb = nat(nil).expWW(bb, Word(leafSize))に変更されたのは、i == 0の場合の初期化ロジックの修正であり、テーブルの最初の要素の計算が正しく行われるようにするためのものです。
src/pkg/math/big/nat_test.go の変更点
-
TestScanPiParallelの追加:- このテスト関数は、
TestScanPiを複数のゴルーチンで並行して実行し、並行処理環境下でのmath/bigパッケージの動作を検証します。これは、cacheBase10のロック変更が並行処理に与える影響を評価するための重要なテストです。
- このテスト関数は、
-
BenchmarkStringPiParallelの追加:- このベンチマーク関数は、
x.decimalString()メソッド（大きな数値を10進数文字列に変換する処理）を複数のゴルーチンで並行して実行し、そのパフォーマンスを測定します。このベンチマークは、divisors関数が内部的に使用するcacheBase10のロック機構が、並行処理のスループットにどのように影響するかを直接的に評価するために導入されました。コミットメッセージに記載されているベンチマーク結果は、この新しいベンチマークによって得られたものです。
- このベンチマーク関数は、
-
LeafSizeHelperの修正:resetTable(cacheBase10[:])がresetTable(cacheBase10.table[:])に変更されました。これは、cacheBase10の構造が変更されたことに伴う、配列スライスへのアクセス方法の修正です。
これらの変更は、math/big パッケージが並行処理環境でより効率的に動作するように、共有リソースへのアクセスをより細かく制御し、ロックの競合を最小限に抑えることを目的としています。
関連リンク
- GitHub Issue: Fixes #4218
- Go Code Review: https://golang.org/cl/6643053
参考にした情報源リンク
- Go言語の
sync.Mutexのドキュメント: https://pkg.go.dev/sync#Mutex - Go言語の
math/bigパッケージのドキュメント: https://pkg.go.dev/math/big - Go言語における並行処理の基本（ゴルーチンとチャネル）に関する一般的な情報源。