Reviewers: dvyukov, mtj,
Message:
Hello dvyukov@google.com, michael.jones@gmail.com (cc:
golangdev@googlegroups.com),
I'd like you to review this change to
https://code.google.com/p/go
Description:
math/big: more conservative use of lock for divisor table
Fixes issue 4218.
Please review this at http://codereview.appspot.com/6643053/
Affected files:
M src/pkg/math/big/nat.go
M src/pkg/math/big/nat_test.go
Index: src/pkg/math/big/nat.go
===================================================================
 a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ 920,8 +920,10 @@
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 {
+ table [64]divisor // cached divisors for base 10
+ mu sync.Mutex // protects table
+}
// expWW computes x**y
func (z nat) expWW(x, y Word) nat {
@@ 937,27 +939,22 @@
// 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.mu.Lock()
+ defer cacheBase10.mu.Unlock()
+ 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[k1].ndigits == 0 {
 if cached {
 cacheLock.Lock() // begin critical section
 }

// add new entries as needed
var larger nat
for i := 0; i < k; i++ {
@@ 980,10 +977,6 @@
table[i].nbits = table[i].bbb.bitLen()
}
}

 if cached {
 cacheLock.Unlock() // end critical section
 }
}
return table
Index: 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 TestScanPiParallel(t *testing.T) {
+ const n = 2
+ c := make(chan bool)
+ for i := 0; i < n; i++ {
+ go func() {
+ TestScanPi(t)
+ c < true
+ }()
+ }
+ for i := 0; i < n; i++ {
+ <c
+ }
+}
+
func BenchmarkScanPi(b *testing.B) {
for i := 0; i < b.N; i++ {
var x nat
@@ 516,7 +530,7 @@
func LeafSizeHelper(b *testing.B, base Word, size int) {
b.StopTimer()
originalLeafSize := leafSize
 resetTable(cacheBase10[:])
+ resetTable(cacheBase10.table[:])
leafSize = size
b.StartTimer()
@@ 533,7 +547,7 @@
}
b.StopTimer()
 resetTable(cacheBase10[:])
+ resetTable(cacheBase10.table[:])
leafSize = originalLeafSize
b.StartTimer()
}