ch9¶
bank1/bank.go¶
/gopl.io/ch9/bank1/bank.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 261.
//!+
// Package bank provides a concurrency-safe bank with one account.
package bank
var deposits = make(chan int) // send amount to deposit
var balances = make(chan int) // receive balance
func Deposit(amount int) { deposits <- amount }
func Balance() int { return <-balances }
func teller() {
var balance int // balance is confined to teller goroutine
for {
select {
case amount := <-deposits:
balance += amount
case balances <- balance:
}
}
}
func init() {
go teller() // start the monitor goroutine
}
//!-
bank1/bank_test.go¶
/gopl.io/ch9/bank1/bank_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package bank_test
import (
"fmt"
"testing"
"gopl.io/ch9/bank1"
)
func TestBank(t *testing.T) {
done := make(chan struct{})
// Alice
go func() {
bank.Deposit(200)
fmt.Println("=", bank.Balance())
done <- struct{}{}
}()
// Bob
go func() {
bank.Deposit(100)
done <- struct{}{}
}()
// Wait for both transactions.
<-done
<-done
if got, want := bank.Balance(), 300; got != want {
t.Errorf("Balance = %d, want %d", got, want)
}
}
bank2/bank.go¶
/gopl.io/ch9/bank2/bank.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 262.
// Package bank provides a concurrency-safe bank with one account.
package bank
//!+
var (
sema = make(chan struct{}, 1) // a binary semaphore guarding balance
balance int
)
func Deposit(amount int) {
sema <- struct{}{} // acquire token
balance = balance + amount
<-sema // release token
}
func Balance() int {
sema <- struct{}{} // acquire token
b := balance
<-sema // release token
return b
}
//!-
bank2/bank_test.go¶
/gopl.io/ch9/bank2/bank_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package bank_test
import (
"sync"
"testing"
"gopl.io/ch9/bank2"
)
func TestBank(t *testing.T) {
// Deposit [1..1000] concurrently.
var n sync.WaitGroup
for i := 1; i <= 1000; i++ {
n.Add(1)
go func(amount int) {
bank.Deposit(amount)
n.Done()
}(i)
}
n.Wait()
if got, want := bank.Balance(), (1000+1)*1000/2; got != want {
t.Errorf("Balance = %d, want %d", got, want)
}
}
bank3/bank.go¶
/gopl.io/ch9/bank3/bank.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 263.
// Package bank provides a concurrency-safe single-account bank.
package bank
//!+
import "sync"
var (
mu sync.Mutex // guards balance
balance int
)
func Deposit(amount int) {
mu.Lock()
balance = balance + amount
mu.Unlock()
}
func Balance() int {
mu.Lock()
b := balance
mu.Unlock()
return b
}
//!-
bank3/bank_test.go¶
/gopl.io/ch9/bank3/bank_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package bank_test
import (
"sync"
"testing"
"gopl.io/ch9/bank3"
)
func TestBank(t *testing.T) {
// Deposit [1..1000] concurrently.
var n sync.WaitGroup
for i := 1; i <= 1000; i++ {
n.Add(1)
go func(amount int) {
bank.Deposit(amount)
n.Done()
}(i)
}
n.Wait()
if got, want := bank.Balance(), (1000+1)*1000/2; got != want {
t.Errorf("Balance = %d, want %d", got, want)
}
}
memo1/memo.go¶
/gopl.io/ch9/memo1/memo.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 272.
//!+
// Package memo provides a concurrency-unsafe
// memoization of a function of type Func.
package memo
// A Memo caches the results of calling a Func.
type Memo struct {
f Func
cache map[string]result
}
// Func is the type of the function to memoize.
type Func func(key string) (interface{}, error)
type result struct {
value interface{}
err error
}
func New(f Func) *Memo {
return &Memo{f: f, cache: make(map[string]result)}
}
// NOTE: not concurrency-safe!
func (memo *Memo) Get(key string) (interface{}, error) {
res, ok := memo.cache[key]
if !ok {
res.value, res.err = memo.f(key)
memo.cache[key] = res
}
return res.value, res.err
}
//!-
memo1/memo_test.go¶
/gopl.io/ch9/memo1/memo_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package memo_test
import (
"testing"
"gopl.io/ch9/memo1"
"gopl.io/ch9/memotest"
)
var httpGetBody = memotest.HTTPGetBody
func Test(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Sequential(t, m)
}
// NOTE: not concurrency-safe! Test fails.
func TestConcurrent(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Concurrent(t, m)
}
/*
//!+output
$ go test -v gopl.io/ch9/memo1
=== RUN Test
https://golang.org, 175.026418ms, 7537 bytes
https://godoc.org, 172.686825ms, 6878 bytes
https://play.golang.org, 115.762377ms, 5767 bytes
http://gopl.io, 749.887242ms, 2856 bytes
https://golang.org, 721ns, 7537 bytes
https://godoc.org, 152ns, 6878 bytes
https://play.golang.org, 205ns, 5767 bytes
http://gopl.io, 326ns, 2856 bytes
--- PASS: Test (1.21s)
PASS
ok gopl.io/ch9/memo1 1.257s
//!-output
*/
/*
//!+race
$ go test -run=TestConcurrent -race -v gopl.io/ch9/memo1
=== RUN TestConcurrent
...
WARNING: DATA RACE
Write by goroutine 36:
runtime.mapassign1()
~/go/src/runtime/hashmap.go:411 +0x0
gopl.io/ch9/memo1.(*Memo).Get()
~/gobook2/src/gopl.io/ch9/memo1/memo.go:32 +0x205
...
Previous write by goroutine 35:
runtime.mapassign1()
~/go/src/runtime/hashmap.go:411 +0x0
gopl.io/ch9/memo1.(*Memo).Get()
~/gobook2/src/gopl.io/ch9/memo1/memo.go:32 +0x205
...
Found 1 data race(s)
FAIL gopl.io/ch9/memo1 2.393s
//!-race
*/
memo2/memo.go¶
/gopl.io/ch9/memo2/memo.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 275.
// Package memo provides a concurrency-safe memoization a function of
// type Func. Concurrent requests are serialized by a Mutex.
package memo
import "sync"
// Func is the type of the function to memoize.
type Func func(string) (interface{}, error)
type result struct {
value interface{}
err error
}
func New(f Func) *Memo {
return &Memo{f: f, cache: make(map[string]result)}
}
//!+
type Memo struct {
f Func
mu sync.Mutex // guards cache
cache map[string]result
}
// Get is concurrency-safe.
func (memo *Memo) Get(key string) (value interface{}, err error) {
memo.mu.Lock()
res, ok := memo.cache[key]
if !ok {
res.value, res.err = memo.f(key)
memo.cache[key] = res
}
memo.mu.Unlock()
return res.value, res.err
}
//!-
memo2/memo_test.go¶
/gopl.io/ch9/memo2/memo_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package memo_test
import (
"testing"
"gopl.io/ch9/memo2"
"gopl.io/ch9/memotest"
)
var httpGetBody = memotest.HTTPGetBody
func Test(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Sequential(t, m)
}
func TestConcurrent(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Concurrent(t, m)
}
memo3/memo.go¶
/gopl.io/ch9/memo3/memo.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 276.
// Package memo provides a concurrency-safe memoization a function of
// type Func. Requests for different keys run concurrently.
// Concurrent requests for the same key result in duplicate work.
package memo
import "sync"
type Memo struct {
f Func
mu sync.Mutex // guards cache
cache map[string]result
}
type Func func(string) (interface{}, error)
type result struct {
value interface{}
err error
}
func New(f Func) *Memo {
return &Memo{f: f, cache: make(map[string]result)}
}
//!+
func (memo *Memo) Get(key string) (value interface{}, err error) {
memo.mu.Lock()
res, ok := memo.cache[key]
memo.mu.Unlock()
if !ok {
res.value, res.err = memo.f(key)
// Between the two critical sections, several goroutines
// may race to compute f(key) and update the map.
memo.mu.Lock()
memo.cache[key] = res
memo.mu.Unlock()
}
return res.value, res.err
}
//!-
memo3/memo_test.go¶
/gopl.io/ch9/memo3/memo_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package memo_test
import (
"testing"
"gopl.io/ch9/memo3"
"gopl.io/ch9/memotest"
)
var httpGetBody = memotest.HTTPGetBody
func Test(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Sequential(t, m)
}
func TestConcurrent(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Concurrent(t, m)
}
memo4/memo.go¶
/gopl.io/ch9/memo4/memo.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 276.
// Package memo provides a concurrency-safe memoization a function of
// a function. Requests for different keys proceed in parallel.
// Concurrent requests for the same key block until the first completes.
// This implementation uses a Mutex.
package memo
import "sync"
// Func is the type of the function to memoize.
type Func func(string) (interface{}, error)
type result struct {
value interface{}
err error
}
//!+
type entry struct {
res result
ready chan struct{} // closed when res is ready
}
func New(f Func) *Memo {
return &Memo{f: f, cache: make(map[string]*entry)}
}
type Memo struct {
f Func
mu sync.Mutex // guards cache
cache map[string]*entry
}
func (memo *Memo) Get(key string) (value interface{}, err error) {
memo.mu.Lock()
e := memo.cache[key]
if e == nil {
// This is the first request for this key.
// This goroutine becomes responsible for computing
// the value and broadcasting the ready condition.
e = &entry{ready: make(chan struct{})}
memo.cache[key] = e
memo.mu.Unlock()
e.res.value, e.res.err = memo.f(key)
close(e.ready) // broadcast ready condition
} else {
// This is a repeat request for this key.
memo.mu.Unlock()
<-e.ready // wait for ready condition
}
return e.res.value, e.res.err
}
//!-
memo4/memo_test.go¶
/gopl.io/ch9/memo4/memo_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package memo_test
import (
"testing"
"gopl.io/ch9/memo4"
"gopl.io/ch9/memotest"
)
var httpGetBody = memotest.HTTPGetBody
func Test(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Sequential(t, m)
}
func TestConcurrent(t *testing.T) {
m := memo.New(httpGetBody)
memotest.Concurrent(t, m)
}
memo5/memo.go¶
/gopl.io/ch9/memo5/memo.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 278.
// Package memo provides a concurrency-safe non-blocking memoization
// of a function. Requests for different keys proceed in parallel.
// Concurrent requests for the same key block until the first completes.
// This implementation uses a monitor goroutine.
package memo
//!+Func
// Func is the type of the function to memoize.
type Func func(key string) (interface{}, error)
// A result is the result of calling a Func.
type result struct {
value interface{}
err error
}
type entry struct {
res result
ready chan struct{} // closed when res is ready
}
//!-Func
//!+get
// A request is a message requesting that the Func be applied to key.
type request struct {
key string
response chan<- result // the client wants a single result
}
type Memo struct{ requests chan request }
// New returns a memoization of f. Clients must subsequently call Close.
func New(f Func) *Memo {
memo := &Memo{requests: make(chan request)}
go memo.server(f)
return memo
}
func (memo *Memo) Get(key string) (interface{}, error) {
response := make(chan result)
memo.requests <- request{key, response}
res := <-response
return res.value, res.err
}
func (memo *Memo) Close() { close(memo.requests) }
//!-get
//!+monitor
func (memo *Memo) server(f Func) {
cache := make(map[string]*entry)
for req := range memo.requests {
e := cache[req.key]
if e == nil {
// This is the first request for this key.
e = &entry{ready: make(chan struct{})}
cache[req.key] = e
go e.call(f, req.key) // call f(key)
}
go e.deliver(req.response)
}
}
func (e *entry) call(f Func, key string) {
// Evaluate the function.
e.res.value, e.res.err = f(key)
// Broadcast the ready condition.
close(e.ready)
}
func (e *entry) deliver(response chan<- result) {
// Wait for the ready condition.
<-e.ready
// Send the result to the client.
response <- e.res
}
//!-monitor
memo5/memo_test.go¶
/gopl.io/ch9/memo5/memo_test.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package memo_test
import (
"testing"
"gopl.io/ch9/memo5"
"gopl.io/ch9/memotest"
)
var httpGetBody = memotest.HTTPGetBody
func Test(t *testing.T) {
m := memo.New(httpGetBody)
defer m.Close()
memotest.Sequential(t, m)
}
func TestConcurrent(t *testing.T) {
m := memo.New(httpGetBody)
defer m.Close()
memotest.Concurrent(t, m)
}
memotest/memotest.go¶
/gopl.io/ch9/memotest/memotest.go¶
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 272.
// Package memotest provides common functions for
// testing various designs of the memo package.
package memotest
import (
"fmt"
"io/ioutil"
"log"
"net/http"
"sync"
"testing"
"time"
)
//!+httpRequestBody
func httpGetBody(url string) (interface{}, error) {
resp, err := http.Get(url)
if err != nil {
return nil, err
}
defer resp.Body.Close()
return ioutil.ReadAll(resp.Body)
}
//!-httpRequestBody
var HTTPGetBody = httpGetBody
func incomingURLs() <-chan string {
ch := make(chan string)
go func() {
for _, url := range []string{
"https://golang.org",
"https://godoc.org",
"https://play.golang.org",
"http://gopl.io",
"https://golang.org",
"https://godoc.org",
"https://play.golang.org",
"http://gopl.io",
} {
ch <- url
}
close(ch)
}()
return ch
}
type M interface {
Get(key string) (interface{}, error)
}
/*
//!+seq
m := memo.New(httpGetBody)
//!-seq
*/
func Sequential(t *testing.T, m M) {
//!+seq
for url := range incomingURLs() {
start := time.Now()
value, err := m.Get(url)
if err != nil {
log.Print(err)
continue
}
fmt.Printf("%s, %s, %d bytes\n",
url, time.Since(start), len(value.([]byte)))
}
//!-seq
}
/*
//!+conc
m := memo.New(httpGetBody)
//!-conc
*/
func Concurrent(t *testing.T, m M) {
//!+conc
var n sync.WaitGroup
for url := range incomingURLs() {
n.Add(1)
go func(url string) {
defer n.Done()
start := time.Now()
value, err := m.Get(url)
if err != nil {
log.Print(err)
return
}
fmt.Printf("%s, %s, %d bytes\n",
url, time.Since(start), len(value.([]byte)))
}(url)
}
n.Wait()
//!-conc
}