type N int

func main() {
    const c = 1
    var n N = c
    fmt.Println(n)
}

and program V uses variable declaration (source code):

type N int

func main() {
    var c = 1
    var n N = c
    fmt.Println(n)
}

Before scrolling down to see answers, please think for a moment about results of both C and V …

.

.

.

.

.

.

.

Program C writes to stdout 1. The second one (V) might be a small surprise. It doesn’t build at all and gives compile-time error: cannot use c (type int) as type N in assignment. If you would like to understand what is exactly happening then just keep reading and in 2 minutes you’ll get it.

Constants in Go can be either typed or untyped. Untyped are created when constant declaration doesn’t specify type (source code):

const x float64 = 12
fmt.Printf("%T\n", x) // float64
const y = 12
fmt.Printf("%T\n", y) // int

Constant y is untyped. When printing its type we’re getting int though…

An untyped constant has a default type which is the type to which the constant is implicitly converted in contexts where a typed value is required.

For example default type for integer constant is int or it’s float64 for floating-point number.

In program V variable c is being set to untyped constant expression 1. Default type of integer constant is int so type of c is ultimately set to int — implicit conversion happens because variables always need to have a type (source code):

var c = 1
fmt.Println(reflect.TypeOf(c).Name()) // int

In program V while executing second assignment:

var n N = c

then assignability rules from language specification apply. Since n is of type N and c is of type int then we’ve a type mismatch and assignment statement is invalid. Why the program C works then? Because in that scenario c is an untyped constant and there is a dedicated assignability rule for such case:

x is assignable to T if x is an untyped constant representable by a value of type T.

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

Resources

• https://golang.org/ref/spec#Constants
• https://golang.org/ref/spec#Assignability

Untyped constants in Go was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

One more gotcha with re-using range clause variables.

This story will start with a puzzle (source code):

type T struct {
    name string
}

func (t T) M(wg *sync.WaitGroup) {
    fmt.Println(t.name)
    wg.Done()
}

func main() {
    var wg sync.WaitGroup
    for _, v := range []T{{"foo"}, {"bar"}, {"baz"}} {
        wg.Add(1)
        go v.M(&wg)
    }
    wg.Wait()
}

Think for a moment about what will be written to stdout? The answer is not that simple. It can be actually many different things. Program will always print foo, bar and baz, each in separate line but the order might be different each time:

baz
foo
bar

It’s really up to the scheduler how to run goroutines. Scheduler isn’t the topic of this post though. Let’s modify that program slightly to use a pointer receiver instead (source code):

func (t *T) M(wg *sync.WaitGroup) {
    fmt.Println(t.name)
    wg.Done()
}

It also depends on runtime’s scheduler but usually I get the same line three times:

baz
baz
baz

If you got intrigued why it differs from the first example then keep reading. This post will explain what is really happening here.

defer vs go statements

It’s worth to mention that we’ll get similar behaviour if we’ll replace go statement with defer statement (source code):

type T struct {
    name string
}

func (t T) M() {
    fmt.Println(t.name)
}

func main() {
    for _, v := range []T{{"foo"}, {"bar"}, {"baz"}} {
        defer v.M()
    }
}

Output:

baz
bar
foo

This is slightly different than code with go statement since output is deterministic — it doesn’t depend on the scheduler (deferred functions are called in LIFO order). If we’ll use pointer receiver then we’re also deterministic behaviour but outcome varies (source code):

type T struct {
    name string
}

func (t *T) M() {
    fmt.Println(t.name)
}

func main() {
    for _, v := range []T{{"foo"}, {"bar"}, {"baz"}} {
        defer v.M()
    }
}

Output:

baz
baz
baz

It’s again the same line three times. To make our analysis slightly easier let’s focus on case with defer statement first since it gives deterministic behaviour.

Many people already know that loops and closures can be tricky (source code):

for _, v := range []string{"foo", "bar", "baz"} {
    defer func() {
        fmt.Println(v)
    }()
}

Output:

baz
baz
baz

It isn’t anything specific to Golang. The same happens in other languages like JavaScript (source code):

(function() {
  var funcs = [];
  for (var v of ["foo", "bar", "baz"]) {
    funcs.push(function() {
      console.info(v);
    });
  }
  funcs.forEach(f => f());
})();

In browser console you’ll see baz logged 3 times. With range clause we need to be extra careful since in Go iteration variables are re-used for each iteration (source code):

type T struct {
    name string
}

func main() {
    names := []T{{"foo"}, {"bar"}, {"baz"}}
    for _, name := range names {
        fmt.Printf("%p\n", &name)
    }
}

Output:

0x40c138
0x40c138
0x40c138

Now that we got a refresher on closures and intricacies of range clause variables, let’s move on to method calls.

x.m()

Such call is valid if method set of x’s type contains m. What is a method set of arbitrary type T?

• Method set of T contains all methods with receiver type T.
• The method set of pointer type *T is the set of all methods declared with receiver *T or T.

Yes, there is asymmetry here. Language specification has additional rule:

If x is addressable and &x's method set contains m, x.m() is shorthand for (&x).m():

For example map elements aren’t addressable — https://play.golang.org/p/isfZwRiIL2a.

This extra rule is relevant in our case. What it actually means? Let’s analyse snippet from above (source code):

type T struct {
    name string
}

func (t *T) M() {
    fmt.Println(t.name)
}

func main() {
    for _, v := range []T{{"foo"}, {"bar"}, {"baz"}} {
        defer v.M()
    }
}

It’s equivalent to:

func main() {
    for _, v := range []T{{"foo"}, {"bar"}, {"baz"}} {
        defer (&v).M()
    }
}

Now it should be slightly clearer. In the examples where we see duplicated lines, methods on pointers to iterations variables are being called. Go doesn’t re-defines iteration variables — those are being re-used. Let’s add a bit more logging (source code):

for _, v := range []T{{"foo"}, {"bar"}, {"baz"}} {
    fmt.Printf("%p\n", &v)
    defer (&v).M()
 }

Output:

0x40c138
0x40c138
0x40c138
baz
baz
baz

Method is called on pointer and for every iteration we’re using the same pointer (referencing memory location of variable v). Deferred functions are fired after outer function finishes so v will be set to last element of slice — {"baz"}. This is why in stdout we see baz three times.

How is this different to the case when we’ve value receiver?

type T struct {
    name string
}

func (t T) M() {
    fmt.Println(t.name)
}

func main() {
    for _, v := range []T{{"foo"}, {"bar"}, {"baz"}} {
        defer v.M()
    }
}

Now we aren’t using pointers but deferring method on copy of each slice element — v contains copy of {"foo"} during first iteration, {"bar"} during 2nd iteration and so forth. This is why we don’t have duplicates.

Examples with go statements are pretty much the same. The only difference is that scheduler may run methods in different order than slice is being traversed.

👏👏👏 👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

Resources

• https://medium.com/golangspec/range-clause-and-the-address-of-iteration-variable-b1796885d2b7
• https://golang.org/ref/spec#Go_statements
• https://golang.org/ref/spec#Defer_statements
• https://golang.org/ref/spec#Calls
• https://golang.org/ref/spec#Method_sets

Pointer receiver methods and iteration variables was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

Tale of comparison operators and {DeepEqual,Equal,EqualFold} methods

You’ve probably seen == or != operators many times in .go files. It turns out that some types like e.g. maps or slices can’t be used as operands to these operators. It’s sometimes needed to compare such values though. In this post we’ll explore all rules behind equality operators in Go, how it plays with Unicode and what are the methods to compare non-comparable types.

Let’s start with something simple and actually not hiding many secrets. For booleans and numeric types (floats, integers, complex numbers) equality operators work without bigger surprises. Type float64 has few special values like NaN (IEEE 754 “not a number” value), positive and negative infinity. It’s worth to mention that NaN is not equal to NaN (source code):

nan := math.NaN()
pos_inf := math.Inf(1)
neg_inf := math.Inf(-1)
fmt.Println(nan == nan)         // false
fmt.Println(pos_inf == pos_inf) // true
fmt.Println(neg_inf == neg_inf) // true
fmt.Println(pos_inf == neg_inf) // false

Pointers

Two pointers are equal if either both are nil or both point to exactly the same address in memory (source code):

var p1, p2 *string
name := "foo"
fmt.Println(p1 == p2) // true
p1 = &name
p2 = &name
fmt.Println(p1)       // 0x40c148
fmt.Println(p2)       // 0x40c148
fmt.Println(&p1)      // 0x40c138
fmt.Println(&p2)      // 0x40c140
fmt.Println(*p1)      // foo
fmt.Println(*p2)      // foo
fmt.Println(p1 == p2) // true

Language spec also says:

A struct or array type has size zero if it contains no fields (or elements, respectively) that have a size greater than zero. Two distinct zero-size variables may have the same address in memory.

Let’s see that rule in action (source code):

type S struct{}

func main() {
    var p1, p2 *S
    s1 := S{}
    s2 := S{}
    p1 = &s1
    p2 = &s2
    fmt.Printf("%p\n", p1) // 0x1e52bc
    fmt.Printf("%p\n", p2) // 0x1e52bc
    fmt.Println(p1)        // &{}
    fmt.Println(p2)        // &{}
    fmt.Println(&p1)       // 0x40c138
    fmt.Println(&p2)       // 0x40c140
    fmt.Println(*p1)       // {}
    fmt.Println(*p2)       // {}
    fmt.Println(p1 == p2)  // true
}

By changing S type definition to non-empty struct like S struct {f int} you’ll see that p1 and p2 are not equal anymore — source code.

Channels

With basic concurrency primitive in Go we’ve two rules i.e. two channels are equal when either:

• both are nil
• both are created by the same call to built-in function make

Code snippet above demonstrates this behaviour (source code):

func f(ch1 chan int, ch2 *chan int) {
    fmt.Println(ch1 == *ch2) // true
}

func main() {
    var ch1, ch2 chan int
    fmt.Println(ch1 == ch2) // true
    ch1 = make(chan int)
    ch2 = make(chan int)
    fmt.Println(ch1 == ch2) // false
    ch2 = ch1
    fmt.Printf("%p\n", &ch1) // 0x40c138
    fmt.Printf("%p\n", &ch2) // 0x40c140
    fmt.Println(ch1 == ch2)  // true
    f(ch1, &ch1)
}

Interfaces

First case might seem simple — two interface values are equal if both are nil. It’s important to remember when exactly interface value is nil. It happens when both dynamic type and dynamic value are nil (source code):

type I interface{ m() }

type T []byte

func (t T) m() {}

func main() {
    var t T
    fmt.Println(t == nil) // true
    var i I = t
    fmt.Println(i == nil)                   // false
    fmt.Println(reflect.TypeOf(i))          // main.T
    fmt.Println(reflect.ValueOf(i).IsNil()) // true
}

More about interfaces in earlier series — https://medium.com/golangspec/interfaces-in-go-part-i-4ae53a97479c.

If dynamic types are identical and dynamic values are equal then two interface values are equal (source code):

type A int
type B = A
type C int

type I interface{ m() }

func (a A) m() {}

func (c C) m() {}

func main() {
    var a I = A(1)
    var b I = B(1)
    var c I = C(1)
    fmt.Println(a == b) // true
    fmt.Println(b == c) // false
    fmt.Println(a == c) // false
}

It’s possible to compare value x of non-interface type X with value i of interface type I . There are few limitations though:

• type X implements interface I
• type X is comparable

If dynamic type of i is X and dynamic value of i is equal to x then values are equal (source code):

type I interface{ m() }

type X int

func (x X) m() {}

type Y int

func (y Y) m() {}

type Z int

func main() {
    var i I = X(1)
    fmt.Println(i == X(1)) // true
    fmt.Println(i == Y(1)) // false
    // fmt.Println(i == Z(1)) // mismatched types I and C
    // fmt.Println(i == 1) // mismatched types I and int
}

If dynamic types of interface values are identical but not comparable then it will generate runtime panic (source code):

type A []byte

func main() {
    var i interface{} = A{}
    var j interface{} = A{}
    fmt.Println(i == j)
}

Output:

panic: runtime error: comparing uncomparable type main.A

If types are different but still not comparable then interface values aren’t equal (source code):

type A []byte
type B []byte

func main() {
    // A{} == A{} // slice can only be compared to nil
    var i interface{} = A{}
    var j interface{} = B{}
    fmt.Println(i == j) // false
}

Structs

While comparing structs, corresponding non-blank fields are checked for equality — both exported and non-exported (source code):

type A struct {
    _ float64
    f1 int
    F2 string
}

type B struct {
    _ float64
    f1 int
    F2 string
}

func main() {
    fmt.Println(A{1.1, 2, "x"} == A{0.1, 2, "x"}) // true
    // fmt.Println(A{} == B{}) // mismatched types A and B 
}

It’s worth to introduce now main rule applicable not only for structs but all types:

x == y is allowed only when either x is assignable to y or y is assignable to x.

This is why A{} == B{} above generates compile-time error.

Arrays

This is similar to struct explained earlier. Corresponding elements needs to be equal for the whole arrays to be equal (source code):

type T struct {
    name string
    age int
    _ float64
}

func main() {
   x := [...]float64{1.1, 2, 3.14}
   fmt.Println(x == [...]float64{1.1, 2, 3.14}) // true
   y := [1]T{{"foo", 1, 0}}
   fmt.Println(y == [1]T{{"foo", 1, 1}}) // true
}

Strings

Strings are in effect immutable slices of bytes and equality works for them by running comparison byte by byte (source code):

fmt.Println(strings.ToUpper("ł") == "Ł")     // true
fmt.Println("foo" == "foo")                  // true
fmt.Println("foo" == "FOO")                  // false
fmt.Println("Michał" == "Michal")            // false
fmt.Println("żondło" == "żondło")            // true
fmt.Println("żondło" != "żondło")            // false
fmt.Println(strings.EqualFold("ąĆź", "ĄćŹ")) // true

Comparing something non-comparable

In this bucket we’ve three types: functions, maps and slices. We can’t do much about the functions. There is not way to compare them in Go (source code):

f := func(int) int { return 1 }
g := func(int) int { return 2 }
f == g

It generates compile-time error: invalid operation: f == g (func can only be compared to nil). It also gives a hint that we can compare functions to nil. The same is true for maps and slices (source code):

f1 := func(int) int { return 1 }
m1 := make(map[int]int)
s1 := make([]byte, 10)
fmt.Println(f1 == nil) // false
fmt.Println(m1 == nil) // false
fmt.Println(s1 == nil) // false
var f2 func()
var m2 map[int]int
var s2 []byte
fmt.Println(f2 == nil) // true
fmt.Println(m2 == nil) // true
fmt.Println(s2 == nil) // true

Are there any options for maps or slices though? Luckily there are and we’ll explore them right now…

[]byte

Package bytes offers utilities to deal with byte slices and it provides functions to check if slices are equal and even equal under Unicode case-folding (source code):

s1 := []byte{'f', 'o', 'o'}
s2 := []byte{'f', 'o', 'o'}
fmt.Println(bytes.Equal(s1, s2)) // true
s2 = []byte{'b', 'a', 'r'}
fmt.Println(bytes.Equal(s1, s2)) // false
s2 = []byte{'f', 'O', 'O'}
fmt.Println(bytes.EqualFold(s1, s2)) // true
s1 = []byte("źdźbło")
s2 = []byte("źdŹbŁO")
fmt.Println(bytes.EqualFold(s1, s2)) // true
s1 = []byte{}
s2 = nil
fmt.Println(bytes.Equal(s1, s2)) // true

What about maps or slices where elements of underlying arrays are not bytes? We’ve two options: reflect.DeepEqual , cmp package or writing ad-hoc comparison code using e.g. for statement. Let’s see first two approaches in action.

reflect.DeepEqual

This function is generic method to compare any values:

func DeepEqual(x, y interface{}) bool

Let’s see how it works with maps (source code):

m1 := map[string]int{"foo": 1, "bar": 2}
m2 := map[string]int{"foo": 1, "bar": 2}
// fmt.Println(m1 == m2) // map can only be compared to nil
fmt.Println(reflect.DeepEqual(m1, m2)) // true
m2 = map[string]int{"foo": 1, "bar": 3}
fmt.Println(reflect.DeepEqual(m1, m2)) // false
m3 := map[string]interface{}{"foo": [2]int{1,2}}
m4 := map[string]interface{}{"foo": [2]int{1,2}}
fmt.Println(reflect.DeepEqual(m3, m4)) // true
var m5 map[float64]string
fmt.Println(reflect.DeepEqual(m5, nil)) // false
fmt.Println(m5 == nil) // true

and slices (source code):

s := []string{"foo"}
fmt.Println(reflect.DeepEqual(s, []string{"foo"})) // true
fmt.Println(reflect.DeepEqual(s, []string{"bar"})) // false
s = nil
fmt.Println(reflect.DeepEqual(s, []string{})) // false
s = []string{}
fmt.Println(reflect.DeepEqual(s, []string{})) // true

You can even apply it to types covered earlier like structs (source code):

type T struct {
    name string
    Age  int
}

func main() {
    t := T{"foo", 10}
    fmt.Println(reflect.DeepEqual(t, T{"bar", 20})) // false
    fmt.Println(reflect.DeepEqual(t, T{"bar", 10})) // false
    fmt.Println(reflect.DeepEqual(t, T{"foo", 10})) // true
}

cmp package

Package cmp offers additional capabilities like customisable Equal methods , option to ignore non-exported struct fields or get diff of two values (source code):

import (
    "fmt"

    "github.com/google/go-cmp/cmp"
)

type T struct {
    Name string
    Age  int
    City string
}

func main() {
    x := T{"Michał", 99, "London"}
    y := T{"Adam", 88, "London"}
    if diff := cmp.Diff(x, y); diff != "" {
        fmt.Println(diff)
    }
}

Output:

  main.T{
-       Name: "Michał",
+       Name: "Adam",
-       Age:  99,
+       Age:  88,
        City: "London",
  }

Please check documentation out to learn more.

Timing attacks

To prevent timing attacks there’s a standard package with function where time to compare slices is independent of the parameters’ content.

import (
    "bytes"
    "crypto/subtle"
    "testing"
)

var (
    x = []byte{'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}
    y = []byte{'b', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a'}
    z = []byte{'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'b'}
)

func BenchmarkBytesEqualXY(b *testing.B) {
    for n := 0; n < b.N; n++ {
        bytes.Equal(x, y)
    }
}

func BenchmarkBytesEqualXZ(b *testing.B) {
    for n := 0; n < b.N; n++ {
        bytes.Equal(x, z)
    }
}

func BenchmarkConstTimeCompXY(b *testing.B) {
    for n := 0; n < b.N; n++ {
        subtle.ConstantTimeCompare(x, y)
    }
}

func BenchmarkConstTimeCompXZ(b *testing.B) {
    for n := 0; n < b.N; n++ {
        subtle.ConstantTimeCompare(x, z)
    }
}

$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/mlowicki/subtle
BenchmarkBytesEqualXY-12        554047392          2.09 ns/op
BenchmarkBytesEqualXZ-12        274583632          4.38 ns/op
BenchmarkConstTimeCompXY-12     66717505           15.0 ns/op
BenchmarkConstTimeCompXZ-12     70632979           15.6 ns/op

Time to compare x and y using bytes.Equal is doubled compared to x and z so it clearly depends on the content of parameters as length is always the same in tests above. That difference is negligible when using subtle.ConstantTimeCompare.

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

Resources

• https://golang.org/ref/spec#Comparison_operators
• https://medium.com/golangspec/interfaces-in-go-part-i-4ae53a97479c

Equality in Golang was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

Deferred function is declared inside another function and is called when surrounding function exits — either normally or if goroutine panics. This mechanism is used e.g. to do cleanup and close open files or sockets.

Deferred functions are evaluated in LIFO fashion (source code):

func f() {
    fmt.Println("f()")
}

func g() {
    fmt.Println("g()")
}

func h() {
    fmt.Println("h()")
}

func main() {
    defer f()
    defer g()
    defer h()
}

Output:

h()
g()
f()

defer statement can be used anywhere inside the function so it’s not limited only to its beginning (source code):

func f() {
    fmt.Println("boo")
}

func main() {
    fmt.Println("one")
    defer f()
    fmt.Println("two")
}

Output:

one
two
boo

Anonymous functions

It’s allowed to used both, named and anonymous functions with defer statement (source code):

func main() {
     defer func() {
         fmt.Println("foo")
     }()
}

Output is foo.

Evaluating deferred function

When deferred function is nil then runtime error is thrown but it’s done when outer function exists not at the moment statement is executed (source code):

func main() {
    var f func()
    defer f()
    fmt.Println("foo")
}

Output:

foo
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0xffffffff addr=0x0 pc=0x8d034]

goroutine 1 [running]:
main.main()
	/tmp/sandbox581176742/prog.go:11 +0xdb

(11th line is the closing bracket of main function)

Function used by defer statement is evaluated at the moment statement is encountered, not when surrounding function exists (source code):

func main() {
    var f func()
    defer f()
    f = func() {
        fmt.Println("foo")
    }
}

Output:

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0xffffffff addr=0x0 pc=0x8ce94]

goroutine 1 [running]:
main.main()
	/tmp/sandbox806328181/prog.go:13 +0x7b

Evaluating parameters of deferred function

While processing defer statement arguments are evaluated. Those arguments will be used when outer function exists (source code):

func g() int {
    fmt.Println("g()")
    return 0
}

func f(int) {
    fmt.Println("f()")
}

func main() {
    defer f(g())
    fmt.Println("Hello world!")
}

Output:

g()
Hello world!
f()

If array is passed and modified before outer function exists then original (at the moment of defer statement) value will be used (source code):

func f(nums [4]int) {
    fmt.Printf("%v\n", nums)
}

func main() {
    nums := [...]int{0,1,2,3}
    defer f(nums)
    nums[0] += 1
}

Output is [0 1 2 3].

If we’ll use type which is a descriptor like slice then modified arguments will be used (source code):

func f(nums []int) {
    fmt.Printf("%v\n", nums)
}

func main() {
    nums := []int{0,1,2,3}
    defer f(nums)
    nums[0] += 1
}

Output is [1 1 2 3]. The same is true for e.g. maps (source code):

func f(nums map[string]int) {
    fmt.Printf("%v\n", nums)
}

func main() {
    nums := map[string]int{"one": 1}
    defer f(nums)
    nums["one"] += 1
}

Output is map[one:2].

Changing return value(s) of surrounding function

If outer function has named result value(s) then deferred function has access to it through closure and can modify it (source code):

func f() (v int) {
    defer func() {
        v *= 2
    }()
    v = 2
    return
}

func main() {
    fmt.Println(f())
}

Output is 4.

Return value(s) of deferred function

Whatever deferred function returns is discarded (source code):

func f() int {
    defer func() int {
        return 5
    }()
    return 0
}
 
func main() {
    fmt.Println(f())
}

Output is 0.

Resources

The Go Programming Language Specification

In 2nd part we’ll discuss handling panics, common uses cases of defer statement and performance of deferred functions. Stay tuned.

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

Defer statement in Golang (part I) was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

In contrast to many other languages, Go doesn’t have multiple constructs for executing block of code repeatedly. There’s single statement (for statement) which takes different forms to support various scenarios and also integrates well with Go-specific mechanisms like slices or channels. In this post we’ll examine under a microscope something which is more interesting than it may seem at first glance.

1. Single boolean condition

Let’s start with the simplest form where only optional bool condition is in use (source code):

var v int = 39
for v != 0 {
     fmt.Println(v)
     if v > 16 {
         v /= 4
     } else {
         v /= 2
     }
}

Output:

39
9
4
2
1

It’s pretty straightforward so the result shouldn’t be any surprise. Delicate modification unveils rule which must be followed by conditions used inside for statements (source code):

var v int = 39
for v {
    fmt.Println(v)
    if v > 16 {
        v /= 4
    } else {
        v /= 2
    }
}

Such program doesn’t compile. It’s required to use boolean condition:

non-bool v (type int) used as for condition

Condition is checked before each loop so if it evaluates to false immediately, block isn’t executed even once.

It’s legal to omit condition completely and then it’s equivalent to boolean value true:

package main

import (
    "net/http"
    "time"
)

func main() {
    for {
        resp, err := http.Get("https://facebook.com")
        if err != nil {
            time.Sleep(time.Second)
        }
        defer resp.Body.Close()
        break
    }
}

2. “For” clause

This is the form, most coders are familiar with. It’s an extension to previous one. It adds init and post statements (source code):

for i := 0; i < 5; i++ {
    fmt.Println(i)
}

Output:

0
1
2
3
4

Init statement ( i := 0) is executed only once before evaluating condition for the very first time. We can omit this statement if needed (source code):

i := 0
for ; i < 5; i++ {
    fmt.Println(i)
}

Output:

0
1
2
3
4

Semicolon before condition is required. What can be used as init statement?

• short variable declaration
• assignment
• increment / decrement statement
• send statement (source code):

ch := make(chan int, 1)
i := 0
for ch <- 1; i < 5; i++ {
    fmt.Println(i)
}

• expression statement like e.g. function call (source code):

i := 0
for fmt.Println("start"); i < 5; i++ {
    fmt.Println(i)
}

Post statement is executed each time block inside for statement is executed (source code):

for i := 0; i < 5; fmt.Println("after") {
    fmt.Println(i)
    i++
}

Output:

0
after
1
after
2
after
3
after
4
after

for i := 0; i < 5; fmt.Println("after") {
    i++
    break
}

This program doesn’t print anything (source code) because of break statement but it’s different story when continue statement is in use (source code):

for i := 0; i < 5; fmt.Println("after") {
    i++
    continue
 }

Output:

after
after
after
after
after

The same rules apply to post statement but with one exception — short variable declaration is not possible there (source code):

for i := 0; i < 5; j := 0 {
    fmt.Println(i)
    i++
}

Such code doesn’t compile and gives:

syntax error: cannot declare in post statement of for loop

Post statement can be omitted but semicolon after condition is then required (source code):

for i := 0; i < 5; {
    fmt.Println(i)
    i++
}

Output:

0
1
2
3
4

3. “Range” clause

This variant allows to iterate through array, pointer to array, slice, string, map or values received on a channel. Let’s go through all types to observe all nuances.

slice

Basic use cases are pretty obvious (source code):

nums := []string{"one", "two", "three"}
for idx, num := range nums {
    fmt.Printf("%d: %s\n", idx, num)
}
for idx := range nums {
   fmt.Println(idx)
}
for range nums {
   fmt.Println("tick")
}

Output:

0: one
1: two
2: three
0
1
2
tick
tick
tick

It’s worth to note that assigning different slice to a variable won’t change iterations (source code):

a := []string{"one", "two", "three", "four", "five"}
b := a[:3]
for idx, num := range b {
    b = b[:5]
    fmt.Printf("%d: %s\n", idx, num)
}

Output:

0: one
1: two
2: three

It’s possible though to change values of slice’s element during iterations and this will be visible if respective iteration entry hasn’t been created yet (source code):

a := []string{"one", "two", "three", "four", "five"}
for idx, num := range a {
    a[4] = "six"
    fmt.Printf("%d: %s\n", idx, num)
}

Output:

0: one
1: two
2: three
3: four
4: six

No iterations will be created for nil slice.

array

Usage and behaviour is similar to slice (source code):

nums := [...]string{"one", "two", "three"}
for idx, num := range nums {
    fmt.Printf("%d: %s\n", idx, num)
}
for idx := range nums {
    fmt.Println(idx)
}
for range nums {
    fmt.Println("tick")
}

Output:

0: one
1: two
2: three
0
1
2
tick
tick
tick

Changing the content of array won’t be reflected when for loop already started (source code):

a := [...]string{"one", "two", "three", "four", "five"}
for idx, num := range a {
    a[4] = "six"
    fmt.Printf("%d: %s\n", idx, num)
}

Output:

0: one
1: two
2: three
3: four
4: five

It’ll be reflected though if at most one iteration variable will be used (source code):

a := [...]string{"one", "two", "three", "four", "five"}
for idx := range a {
    a[4] = "six"
    fmt.Printf("%d: %s\n", idx, a[idx])
}

Output:

0: one
1: two
2: three
3: four
4: six

pointer to array

This is almost identical to pure array (source code):

nums := &[...]string{"one", "two", "three"}
for idx, num := range *nums {
    fmt.Printf("%d: %s\n", idx, num)
}
for idx, num := range nums {
    fmt.Printf("%d: %s\n", idx, num)
}
for idx := range nums {
    fmt.Println(idx)
}
for range nums {
   fmt.Println("tick")
}

Output:

0: one
1: two
2: three
0: one
1: two
2: three
0
1
2
tick
tick
tick

The difference is with changing value of array’s elements which will be visible in loop which has already started even if two iteration variables will be used (source code):

a := &[...]string{"one", "two", "three", "four", "five"}
for idx, num := range a {
    a[4] = "six"
    fmt.Printf("%d: %s\n", idx, num)
}

Output:

0: one
1: two
2: three
3: four
4: six

string

We’ll explore this scenario with string containing non-ASCII characters (source code):

s := "żądło"
for i := 0; i < len(s); i++ {
    fmt.Printf("%q\n", s[i])
}
fmt.Println(strings.Repeat("*", 10))
for i, c := range s {
    fmt.Printf("%d: %q\n", i, c)
}

Output:

'Å'
'¼'
'Ä'
'\u0085'
'd'
'Å'
'\u0082'
'o'
**********
0: 'ż'
2: 'ą'
4: 'd'
5: 'ł'
7: 'o'

How to interpret above result? Using built-in len function, loop iterates over each byte within a string. The second for statement goes through Unicode code points, encoded as UTF-8. Index value points to index of first byte of the current code point.

If only one iteration variable is present then it’ll be assigned to index iteration value — index of first byte of current code point (source code):

s := "żądło"
for i := range s {
    fmt.Printf("%d\n", i)
}

Output:

0
2
4
5
7

map

Let’s begin with few basic examples (source code):

m := map[string]int{"one": 1, "two": 2, "three": 3}
for range m {
     fmt.Println("loop")
}
for k := range m {
     fmt.Printf("key: %q\n", k)
}
for k, v := range m {
     fmt.Printf("key: %q, value: %d\n", k, v)
}

Output:

loop
loop
loop
key: "one"
key: "two"
key: "three"
key: "one", value: 1
key: "two", value: 2
key: "three", value: 3

Idiomatic code skips iteration variable instead of using blank identifier (source code):

m := map[string]int{"one": 1, "two": 2, "three": 3}
for range m { // idiomatic
    fmt.Println("a")
}
for _ = range m {
    fmt.Println("b")
}
for _, _ = range m {
    fmt.Println("c")
}
for k := range m { // idiomatic
    fmt.Printf("key: %q\n", k)
}
for k, _ := range m {
    fmt.Printf("key: %q\n", k)
}

Output:

a
a
a
b
b
b
c
c
c
key: "two"
key: "three"
key: "one"
key: "one"
key: "two"
key: "three"

There’re none iterations over nil map (source code):

var m map[string]int
for range m {
    fmt.Println("foo")
}
m = map[string]int{"one": 1, "two": 2}
for range m {
    fmt.Println("bar")
}

Output:

bar
bar

Map is a mutable data structure so while iterating, its content may change by adding / removing keys or changing values associated with keys. If key has been added while going over map then specification says it’s undefined behaviour if iteration for that key will be created — will be either skipped or processed (source code):

m := make(map[string]int)
m["one"] = 1
m["two"] = 2
for k := range m {
    fmt.Println(k)
    m["four"] = 4
}

Such program will always print one and two (order is not defined). It’s undefined though if also four will be written to stdout.

It’s guaranteed by spec that if key for which iteration value hasn’t been produced yet will be removed then such key won’t be produced (source code):

m := make(map[string]int)
m["one"] = 1
m["two"] = 2
for k := range m {
    fmt.Println(k)
    delete(m, "two")
}

If the first iteration value will be “one” then it’s guaranteed that second iteration won’t happen.

Changes to map’s values will be reflected in already running loop (source code):

nums := map[string]int{"one": 1, "two": 2}
for idx, num := range nums {
    fmt.Printf("%s: %d\n", idx, num)
    nums["one"] = 11
    nums["two"] = 22
}
nums = map[string]int{"one": 1, "two": 2}
for idx := range nums {
    fmt.Printf("%s: %d\n", idx, nums[idx])
    nums["one"] = 11
    nums["two"] = 22
}

Output depends on the order of how keys will be processed but in any way, the second iteration will show updated value like:

one: 1
two: 22
two: 2
one: 11

channel

Range clause with channel iterates over all values sent to channel until that channel is closed (source code):

ch := make(chan int)
go func() {
    time.Sleep(3 * time.Second)
    ch <- 1
    time.Sleep(2 * time.Second)
    ch <- 2
    time.Sleep(time.Second)
    close(ch)
}()
fmt.Printf("before:\t\t%s\n", time.Now())
for v := range ch {
    fmt.Printf("tick #%d:\t%s\n", v, time.Now())
}
fmt.Printf("after:\t\t%s\n", time.Now())

Output:

before:		2009-11-10 23:00:00 +0000 UTC m=+0.000000001
tick #1:	2009-11-10 23:00:03 +0000 UTC m=+3.000000001
tick #2:	2009-11-10 23:00:05 +0000 UTC m=+5.000000001
after:		2009-11-10 23:00:06 +0000 UTC m=+6.000000001

If nothing has been sent for already closed channel then no iterations will be executed (source code):

ch := make(chan int)
close(ch)
for range ch {
    fmt.Println("tick")
}
fmt.Println("done!")

It printsdone! to stdout.

Range clause with channel supports only one (optional) iteration variable (source code):

ch := make(chan int, 2)
ch <- 1
ch <- 2
close(ch)
for a, b := range ch {
}

This program gives compile-time error: ./prog.go:8:14: too many variables in range.

If channel is not closed (source code):

ch := make(chan int)
for range ch {
}

or nil channel is used (zero value for channel types) (source code):

var ch chan int
for range ch {
}

then for statement hangs forever and ultimately produces runtime error:

fatal error: all goroutines are asleep - deadlock!

short variable declaration

Variable defined in outer scope will be still reachable after for statement and its value will be set to value from last iteration (source code):

nums := []string{"zero", "one", "two"}
var idx int
for idx = range nums {
}
fmt.Println(idx)

Output is 2.

If variable within range clause will be declared using short variable declaration then its scope will be for statement (source code):

nums := []string{"zero", "one", "two"}
for idx := range nums {
}
fmt.Println(idx)

This produce compile-time error undefined: idx.

range clause and the address of iteration variable

This topic has been described in one of previous stories so let’s link it here. It’s recommended to read it since it’s a trap many engineers fall into.

range clause and the address of iteration variable

Resources

• The Go Programming Language Specification
• Blocking goroutine forever
• Range over channels in Go

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

“for” statement and its all faces in Golang was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

package main

import (
    "fmt"
)

type T struct {
    id int
}

func main() {
    t1 := T{id: 1}
    t2 := T{id: 2}
    ts1 := []T{t1, t2}
    ts2 := []*T{}
    for _, t := range ts1 {
        ts2 = append(ts2, &t)
    }
    for _, t := range ts2 {
        fmt.Println((*t).id)
    }
}

Think for a moment about expected output of this program..

For some (including me) the result might be surprising at first glance:

2
2

I’ve personally expected

1
2

but it turned out to be wrong answer.

Iteration variable t is declared using short variable declaration. Its scope is the block of the “for” statement. It’s a variable which during first iteration hold value of the first element and during 2nd iteration value of the second element . But it’s just another place in memory which hold current element of slice being iterated over. It doesn’t point to values stored inside slice’s underlying array — it’s a temporary bucket where next elements are copied over. So &t will have the same value in each iteration since it’s a auxiliary variable to hold currently iterated element.

(source code)

t1 := T{id: 1}
t2 := T{id: 2}
ts1 := []T{t1, t2}
ts2 := []*T{}
for _, t := range ts1 {
    t.id = 3
    ts2 = append(ts2, &t)
}
for _, t := range ts2 {
    fmt.Println((*t).id)
}
fmt.Println(ts1)
fmt.Println(t1)
fmt.Println(t2)

output:

3
3
[{1} {2}]
{1}
{2}

Possible solution is to use index and get the address of slice’s element (source code):

t1 := T{id: 1}
t2 := T{id: 2}
ts1 := []T{t1, t2}
ts2 := []*T{}
for i, _ := range ts1 {
    ts2 = append(ts2, &ts1[i])
}
for _, t := range ts2 {
    fmt.Println((*t).id)
}

output:

1
2

Resources

https://golang.org/ref/spec#For_range

range clause and the address of iteration variable was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

Solving readers-writers problems

Readers-writers problems (plural since there’re some variations) occur when shared piece of data needs to be accessed by multiple threads. There’re two types of threads accessing data — readers and writers. Readers only read data and writers modify it. When writer has access to data then none other thread (reader or writer) can share such access. This constraint takes place in real life when e.g writer cannot modify data (like database) in atomic way so reading incomplete changes must be blocked to prevent loading corrupted data. There’re many modifications of the core problem like:

• writers cannot be starved (waiting indefinitely for their turn)
• readers cannot be starved
• no thread shall be allowed to starve

Concrete implementation of multi-reader / single-writer mutual exclusion lock (like sync.RWMutex) solve one of readers-writers problems. Let’s see how it’s done in Go and what kind of guarantees it gives…

As a bonus we’ll look into profiling contended mutexes.

Article has been translated into Chinese — here.

Usage

Before diving into implementation details let’s see sync.RWMutex in action. Program below uses reader/writer mutex to protect critical section — sleep(). To visualise the whole process critical section is decorated with counting how many readers and writers are currently executing it (source code):

package main

import (
    "fmt"
    "math/rand"
    "strings"
    "sync"
    "time"
)

func init() {
    rand.Seed(time.Now().Unix())
}

func sleep() {
    time.Sleep(time.Duration(rand.Intn(1000)) * time.Millisecond)
}

func reader(c chan int, m *sync.RWMutex, wg *sync.WaitGroup) {
    sleep()
    m.RLock()
    c <- 1
    sleep()
    c <- -1
    m.RUnlock()
    wg.Done()
}

func writer(c chan int, m *sync.RWMutex, wg *sync.WaitGroup) {
    sleep()
    m.Lock()
    c <- 1
    sleep()
    c <- -1
    m.Unlock()
    wg.Done()
}

func main() {
    var m sync.RWMutex
    var rs, ws int
    rsCh := make(chan int)
    wsCh := make(chan int)
    go func() {
        for {
            select {
            case n := <-rsCh:
                rs += n
            case n := <-wsCh:
                ws += n
            }
            fmt.Printf("%s%s\n", strings.Repeat("R", rs),
                    strings.Repeat("W", ws))
        }
    }()
    wg := sync.WaitGroup{}

    for i := 0; i < 10; i++ {
        wg.Add(1)
        go reader(rsCh, &m, &wg)
    }
    for i := 0; i < 3; i++ {
        wg.Add(1)
        go writer(wsCh, &m, &wg)
    }
    wg.Wait()
}

Environment of programs launched on play.golang.org is deterministic (e.g. when time begins) so rand.Seed(time.Now().Unix()) will provide the same seed value and the program’s output will be most likely the same. Either put different seed each time or run program on your machine.

Sample output:

W

R
RR
RRR
RRRR
RRRRR
RRRR
RRR
RRRR
RRR
RR
R

W

R
RR
RRR
RRRR
RRR
RR
R

W

New line is printed each time set of goroutines (readers and writers) executing critical section changes. It’s visible that RWMutex allows for either at least one reader or exactly one writer.

What is also important and will be discussed further is that once writer calls Lock() then new readers are blocked. Writer waits for current set of readers to finish their jobs (departure) and when done writer is ready to go. It’s visible by decreasing number of readers one at a time and afterwards writer is displayed in a single line:

...
RRRRR
RRRR
RRR
RR
R

W

...

Once writer ends, previously blocked readers are resumed and next writer can start. Worth to know is the fact that if writer is done and there’re both readers and writers waiting then first readers will be unblocked and then writer. This way writer need to wait for the current set of readers so neither readers or writers will get starved.

Implementation

Be warned that implementation being investigated (718d6c58) can change any time.

RWMutex exposes two methods used by readers (RLock and RUnlock) and two dedicated for writers (Lock and Unlock).

RLock

For the sake of brevity let’s skip parts related to race detector (they will be replaced by ...).

func (rw *RWMutex) RLock() {
    ...
    if atomic.AddInt32(&rw.readerCount, 1) < 0 {    
        runtime_SemacquireMutex(&rw.readerSem, false)
    }
    ...
}

Field readerCount is an int32 value indicating number of pending readers — already reading data or blocked by writer. This is basically the number of readers which have called RLock function but no RUnlock yet.

atomic.AddInt32 is the atomic equivalent of:

*addr += delta
return *addr

where addr has type *int32 and delta has type int32. Because it’s atomic operation there is no risk that adding delta will interfere with other threads (more about fetch-and-add).

If writers don’t come into play then readerCount is always greater than or equal to 0 and readers have fast non-blocking path involving only calls of atomic.AddInt32.

Semaphore

It’s a data structure invented by Edsger Dijkstra and it’s useful to solve many synchronization problems. It’s an integer with two operations:

• acquire (known also as wait, decrement or P)
• release (signal, increment or V)

Operation acquire decreases the semaphore by 1. If the result is negative then thread blocks and cannot resume until other thread will increment the semaphore. If result is positive then thread continues execution.

Operation release increases the semaphore by 1. If there’re blocked threads then one of them gets unblocked.

Go’s runtime provides runtime_SemacquireMutex and runtime_Semrelease functions which are used e.g. to implement sync.RWMutex.

Lock

func (rw *RWMutex) Lock() {
    ...
    rw.w.Lock()
    r := atomic.AddInt32(&rw.readerCount, -rwmutexMaxReaders) + rwmutexMaxReaders
    if r != 0 && atomic.AddInt32(&rw.readerWait, r) != 0 {     
        runtime_SemacquireMutex(&rw.writerSem, false)
    }
    ...
}

Method Lock is used by writers to get exclusive access to shared data. First it’ll acquire a mutex w which excludes other writers. This mutex is unlocked at the very end of Unlock function. Next it decreases readerCount by rwmutexMaxReaders (1 << 30). When readerCount becomes negative then RLock will block upcoming readers:

if atomic.AddInt32(&rw.readerCount, 1) < 0 {
    // A writer is pending, wait for it.    
    runtime_SemacquireMutex(&rw.readerSem, false)
}

Since new readers will be blocked then what happens with readers already running? Field readerWait is used to remember current number of readers and block writer on semaphore. This semaphore will be unblocked when last reader unlocks the mutex in RUnlock method discussed below.

If there aren’t active readers then writer simply continues its execution.

rwmutexMaxReaders

In rwmutex.go there is a constant:

const rwmutexMaxReaders = 1 << 30

What it does and what is the meaning of 1 << 30 number?

Field readerCount is of type int32 so has range:

[-1 << 31, (1 << 31) — 1] or [-2147483648, 2147483647]

RWMutex uses this field both for counting pending readers and to mark pending writer. In Lock method:

r := atomic.AddInt32(&rw.readerCount, -rwmutexMaxReaders) + rwmutexMaxReaders

field readerCount is decreased by 1<<30. Negative value of readerCount means that writer is pending and readerCount + rwmutexMaxReaders is the current number of pending readers. It also limits how many readers can be pending. If we would have rwmutexMaxReaders or more pending readers then readerCount would be non-negative which would collapse the whole mechanism. So the actual limit on the number of readers is:

rwmutexMaxReaders - 1

which is still over a billion — 1073741823.

RUnlock

func (rw *RWMutex) RUnlock() {
    ...
    if r := atomic.AddInt32(&rw.readerCount, -1); r < 0 {
        if r+1 == 0 || r+1 == -rwmutexMaxReaders {
            race.Enable()
            throw("sync: RUnlock of unlocked RWMutex")
        }
        // A writer is pending.
        if atomic.AddInt32(&rw.readerWait, -1) == 0 {
            // The last reader unblocks the writer.       
            runtime_Semrelease(&rw.writerSem, false)
        }
    }
    ...
}

This method decrements readerCount (incremented by RLock). If readerCount is negative then it means that writer is either waiting or running. It’s because because readerCount has been decreased by rwmutexMaxReaders in Lock method. Afterwards it’s checked if number of departing readers (readerWait) is finally 0 because it means that writer can finally acquire semaphore.

Unlock

func (rw *RWMutex) Unlock() {
    ...
    r := atomic.AddInt32(&rw.readerCount, rwmutexMaxReaders)
    if r >= rwmutexMaxReaders {
        race.Enable()
        throw("sync: Unlock of unlocked RWMutex")
    }
    for i := 0; i < int(r); i++ {
        runtime_Semrelease(&rw.readerSem, false)
    }
    rw.w.Unlock()
    ...
}

To unlock the mutex held by writer first readerCount is increased by rwmutexMaxReaders so it’ll be again non-negative number. If readerCount is greater than zero then it means that some readers were waiting for writer to finish so now it’s time to wake them up. Afterwards writer mutex is released to allow writer to lock the RWMutex for writing.

Unlock and Runlock methods will throw an error if reader or writer will try to unlock unlocked mutex (source code):

m := sync.RWMutex{}
m.Unlock()

Output:

fatal error: sync: Unlock of unlocked RWMutex
...

Recursive read locking

Documentation says:

If a goroutine holds a RWMutex for reading and another goroutine might call Lock, no goroutine should expect to be able to acquire a read lock until the initial read lock is released. In particular, this prohibits recursive read locking. This is to ensure that the lock eventually becomes available; a blocked Lock call excludes new readers from acquiring the lock.

RWMutex works in a way that if there is a pending writer then all attempts to call RLock will lock no matter if e.g. read lock has been already acquired (source code):

package main

import (
    "fmt"
    "sync"
    "time"
)

var m sync.RWMutex

func f(n int) int {
    if n < 1 {
        return 0
    }
    fmt.Println("RLock")
    m.RLock()
    defer func() {
        fmt.Println("RUnlock")
        m.RUnlock()
    }()
    time.Sleep(100 * time.Millisecond)
    return f(n-1) + n
}

func main() {
    done := make(chan int)
    go func() {
        time.Sleep(200 * time.Millisecond)
        fmt.Println("Lock")
        m.Lock()
        fmt.Println("Unlock")
        m.Unlock()
        done <- 1
    }()
    f(4)
    <-done
}

Output:

RLock
RLock
RLock
Lock
RLock
fatal error: all goroutines are asleep - deadlock!

Copying locks

go tool vet is able to detect if locks are copied by value which can result in deadlocks. More about it in one of previous stories:

Detect locks passed by value in Go

Performance

Some time ago it was discovered that RWMutex’s performance degrades with increased number of CPU cores — https://github.com/golang/go/issues/17973.

Contention

Go ≥ 1.8 enables profiling contended mutex (patch). Let’s see how it works:

package main

import (
    "net/http"
    _ "net/http/pprof"
    "runtime"
    "sync"
    "time"
)

func main() {
    var mu sync.Mutex
    runtime.SetMutexProfileFraction(5)
    for i := 0; i < 10; i++ {
        go func() {
            for {
                mu.Lock()
                time.Sleep(100 * time.Millisecond)
                mu.Unlock()
            }
        }()
    }
    http.ListenAndServe(":8888", nil)
}

> go build mutexcontention.go
> ./mutexcontention

While the program mutexcontention is running:

> go tool pprof mutexcontention http://localhost:8888/debug/pprof/mutex?debug=1
Fetching profile over HTTP from http://localhost:8888/debug/pprof/mutex?debug=1
Saved profile in /Users/mlowicki/pprof/pprof.mutexcontention.contentions.delay.003.pb.gz
File: mutexcontention
Type: delay
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) list main
Total: 57.28s
ROUTINE ======================== main.main.func1 in /Users/mlowicki/projects/golang/src/github.com/mlowicki/mutexcontention/mutexcontention.go
0     57.28s (flat, cum)   100% of Total
.          .     14:   for i := 0; i < 10; i++ {
.          .     15:           go func() {
.          .     16:                   for {
.          .     17:                           mu.Lock()
.          .     18:                           time.Sleep(100 * time.Millisecond)
.     57.28s     19:                           mu.Unlock()
.          .     20:                   }
.          .     21:           }()
.          .     22:   }
.          .     23:
.          .     24:   http.ListenAndServe(":8888", nil)

What’s this 57.28s and why it points to mu.Unlock() ?

When goroutine blocks on mutex by calling Lock method then exact time when it happens is recorded — acquiretime. Afterwards when another goroutine unlocks that mutex and there is at least one goroutine waiting to acquire it then one of them is unblocked and mutexevent function is called. Function mutexevent checks if based on rate set by SetMutexProfileFraction this particular event should be saved or discarded. Such event contains time spent on waiting (current time — acquiretime). In listing above total wait time across all goroutines blocked on particular mutex is gathered and displayed.

Contention on reader lock (Rlock and RUnlock) will be added in Go 1.11 (patch).

Resources

• “The Little Book of Semaphores” by Allen B. Downey
• Documentation of sync.RWMutex
• Readers-writers problem on Wikipedia
• Reusable barriers in Golang
• Synchronization queues in Golang

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

sync.RWMutex was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

how to use channels to write idiomatic code in Go

Problem

Let’s suppose we’re running an IT company employing programmers and testers. To give people a chance to get to know each other and relax a bit we’ve bought a ping-pong table and established following rules:

• exactly two people can play at the same time,
• next pair can start their game only when previous one finished so it’s not allowed to switch one player,
• testers can only work with programmers and vice versa (never two testers or two programmers together). If programmer or tester wants play then needs to wait for tester or programmer respectively to establish a valid pair.

func main() {
    for i := 0; i < 10; i++ {
        go programmer()
    }
    for i := 0; i < 5; i++ {
        go tester()
    }
    select {} // long day at work...
}

func programmer() {
    for {
        code()
        pingPong()
    }
}

func tester() {
    for {
        test()
        pingPong()
    }
}

We’ll mimic testing, coding and playing ping-pong by time.sleep:

func test() {
    work()
}

func code() {
    work()
}

func work() {
    // Sleep up to 10 seconds.
    time.Sleep(time.Duration(rand.Intn(10000)) * time.Millisecond)
}

func pingPong() {
    // Sleep up to 2 seconds.
    time.Sleep(time.Duration(rand.Intn(2000)) * time.Millisecond)
}

func programmer() {
    for {
        code()
        fmt.Println("Programmer starts")
        pingPong()
        fmt.Println("Programmer ends")

    }
}

func tester() {
    for {
        test()
        fmt.Println("Tester starts")
        pingPong()
        fmt.Println("Tester ends")
    }
}

Such program emits stream of messages like this:

> go run pingpong.go
Tester starts
Programmer starts
Programmer starts
Tester ends
Programmer ends
Programmer starts
Programmer ends
Programmer ends

But to play ping-pong in accordance with the rules our stream of messages can consists only of such 4-lines long sequences (in any order and repeated arbitrary number of times):

Tester starts
Programmer starts
Tester ends
Programmer ends

Tester starts
Programmer starts
Programmer ends
Tester ends

Programmer starts
Tester starts
Tester ends
Programmer ends

Programmer starts
Tester starts
Programmer ends
Tester ends

So first either tester or programmer approaches the table. Afterwards partner joins (programmer or tester accordingly). While leaving the game they can do it in any order. This is why we’ve 4 valid sequences.

Below are two solutions. 1st one is based on mutexes and 2nd one uses separate worker which coordinates the whole process making sure everything happens according to the policy.

Solution #1

Both solutions are using data structure which queues programmers and testers before approaching the table. When there is at least one valid pair available (Dev + QA) then one pair is allowed to play ping-pong.

func tester(q *queue.Queue) {
    for {
        test()
        q.StartT()
        fmt.Println("Tester starts")
        pingPong()
        fmt.Println("Tester ends")
        q.EndT()
    }
}

func programmer(q *queue.Queue) {
    for {
        code()
        q.StartP()
        fmt.Println("Programmer starts")
        pingPong()
        fmt.Println("Programmer ends")
        q.EndP()
    }
}

func main() {
    q := queue.New()
    for i := 0; i < 10; i++ {
        go programmer(q)
    }
    for i := 0; i < 5; i++ {
        go tester(q)
    }
    select {}
}

Package queue is defined as follows:

package queue

import "sync"

type Queue struct {
    mut                   sync.Mutex
    numP, numT            int
    queueP, queueT, doneP chan int
}

func New() *Queue {
    q := Queue{
        queueP: make(chan int),
        queueT: make(chan int),
        doneP:  make(chan int),
    }
    return &q
}

func (q *Queue) StartT() {
    q.mut.Lock()
    if q.numP > 0 {
        q.numP -= 1
        q.queueP <- 1
    } else {
        q.numT += 1
        q.mut.Unlock()
        <-q.queueT
    }
}

func (q *Queue) EndT() {
    <-q.doneP
    q.mut.Unlock()
}

func (q *Queue) StartP() {
    q.mut.Lock()
    if q.numT > 0 {
        q.numT -= 1
        q.queueT <- 1
    } else {
        q.numP += 1
        q.mut.Unlock()
        <-q.queueP
    }
}

func (q *Queue) EndP() {
    q.doneP <- 1
}

Queue has mutex which serves two purposes:

• synchronizes access to shared counters (numT and numP)
• acts as a token held by playing employees which blocks others from joing the table

Programmers and testers are waiting for ping-pong parter using unbuffered channels:

<-q.queueP

or

<-q.queueT

Reading from one of these channels will block goroutine if there is no opponent available.

Let’s analyze StartT which is executed by testers:

func (q *Queue) StartT() {
    q.mut.Lock()
    if q.numP > 0 {
        q.numP -= 1
        q.queueP <- 1
    } else {
        q.numT += 1
        q.mut.Unlock()
        <-q.queueT
    }
}

If numP is greater than 0 (there is at least one programmer waiting for the game) then number of waiting programmers is decreased by one and one of waiting programmer will be allowed to join the table (q.queueP <- 1). What is interesting here is during this path mutex won’t be released so it’ll serve as a token giving exclusive access to ping-pong table.

If there is no waiting programmers then numT (number of waiting testers) is increased and goroutine blocks on <-q.queueT.

StartP is basically the same but executed by programmers.

During the play, mutex will be locked so it needs to be released by either programmer or tester. To release mutex only when both parties finished the game a barrier doneP is used:

func (q *Queue) EndT() {
    <-q.doneP
    q.mut.Unlock()
}

func (q *Queue) EndP() {
    q.doneP <- 1
}

If programmer is still playing and tester finished then tester will block on <-q.doneP. As soon as programmer reaches q.doneP <- 1 then barrier will open and mutex will be released to allow these employees to go back to work.

If tester is still playing then programmer will block on q.doneP <- 1. When tester is done then it reads from barrier <-q.doneP which will unblock programmer and mutex will be released to free the table.

What is interesting here is that mutex is always released by tester even when either tester or programmer might locked it. It’s also part of reason why this solution might not be so obvious at first glance…

Solution #2

package queue

const (
    msgPStart = iota
    msgTStart
    msgPEnd
    msgTEnd
)

type Queue struct {
    waitP, waitT   int
    playP, playT   bool
    queueP, queueT chan int
    msg            chan int
}

func New() *Queue {
    q := Queue{
        msg:    make(chan int),
        queueP: make(chan int),
        queueT: make(chan int),
    }
    go func() {
        for {
            select {
            case n := <-q.msg:
                switch n {
                case msgPStart:
                    q.waitP++
                case msgPEnd:
                    q.playP = false
                case msgTStart:
                    q.waitT++
                case msgTEnd:
                    q.playT = false
                }
                if q.waitP > 0 && q.waitT > 0 && !q.playP && !q.playT {
                    q.playP = true
                    q.playT = true
                    q.waitT--
                    q.waitP--
                    q.queueP <- 1
                    q.queueT <- 1
                }
            }
        }
    }()
    return &q
}

func (q *Queue) StartT() {
    q.msg <- msgTStart
    <-q.queueT
}

func (q *Queue) EndT() {
    q.msg <- msgTEnd
}

func (q *Queue) StartP() {
    q.msg <- msgPStart
    <-q.queueP
}

func (q *Queue) EndP() {
    q.msg <- msgPEnd
}

We’ve a central coordinator running inside separate goroutine which orchestrate the whole process. Scheduler gets information about new employee who wants to relax or if someone is done with ping-pong via msg channel. While receiving any message state of the scheduler is updated:

• number of waiting Devs or QAs is increased
• information about playing employees is updated

After receiving any of defined messages, scheduler will check if it’s allowed to start a game by another pair:

if q.waitP > 0 && q.waitT > 0 && !q.playP && !q.playT {

If so the state is updated accordingly and one tester and one programmer are unblocked.

Instead of using mutexes (as in solution#1) to manage access to shared data, we’ve now a separate goroutine which talks with outside world over the channel. This gives us more idiomatic Go program.

Don’t communicate by sharing memory, share memory by communicating.

Resources

• “The Little Book of Semaphores” by Allen B. Downey
• https://medium.com/golangspec/reusable-barriers-in-golang-156db1 f75d0b
• https://blog.golang.org/share-memory-by-communicating

If you’ve found alternative solution you would like to share then please comment beneath.

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

Synchronization queues in Golang was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

How to implement them using buffered channels

In this story we’ll examine basic synchronization problem to see how concurrency primitives in Golang like buffered channels can be used to implement concise solutions.

Problem

Let’s suppose we’ve a number of workers. To take advantage of multiple CPU core every worker runs inside separate goroutine:

for i := 0; i < workers; i++ {
    go worker()
}

Worker does a series of jobs:

func worker() {
    for i := 0; i < 3; i++ {
        job()
    }
}

Each job is preceded with bootstrap that needs to be synchronized across all workers — worker needs to wait for all other workers to do their bootstrap before starting work on its own job:

func worker() {
    for i := 0; i < 3; i++ {
        bootstrap()
        # wait for other workers to bootstrap
        job()
    }
}

There is one more thing. Bootstrap for loop n cannot be started if at least one worker still works on job from previous loop— bootstrap is used by following job so we cannot run another bootstrap if previous job is still being worked on:

func worker() {
    for i := 0; i < 3; i++ {
        # wait for all workers to finish previous loop
        bootstrap()
        # wait for other workers to bootstrap
        job()
    }
}

Our bootstrap will be incrementing shared counter and our job will be sleep for some random time and then printing value of shared counter:

type counter struct {
    c int
    sync.Mutex
}

func (c *counter) Incr() {
    c.Lock()
    c.c += 1
    c.Unlock()
}

func (c *counter) Get() (res int) {
    c.Lock()
    res = c.c
    c.Unlock()
    return
}

func worker(c *counter) {
    for i := 0; i < 3; i++ {
        # wait for all workers to finish previous loop
        c.Incr()
        # wait for other workers to do bootstrap
        time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
        fmt.Println(c.Get())
    }
}

The goal is to write a program which prints numbers in the following way:

• only n, 2*n and 3*n numbers are allowed (since each worker executes 3 loops)
• number is never less than number printed line above
• each number should be displayed exactly n times

Expected output with 3 workers:

3
3
3
6
6
6
9
9
9

Expected output with 2 workers:

2
2
4
4
6
6

Sample invalid output with 2 workers:

2
4
2
4
6
6

Think about possible solution(s). Next couple of lines are left blank intentionally to not show ready recipe right away.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Workers will be synchronized by data structure called reusable barrier. Barrier consists of 2 gates. 1st gate is placed before incrementing the counter. It’s closed at the very beginning. Closed gate means that worker will be blocked when reaching it. Once every worker gets to gate 1. then:

• gate 2. (which is placed after increment) closes
• gate 1. opens

All workers increment shared counter and will successively reach gate 2 which is blocked. Once all workers get to 2nd gate then:

• gate 1. closes
• gate 2. opens

Workers can now work on jobs and then reach 1st gate again during next loop. The whole cycle starts again. Let’s visualize the whole process:

     1st gate     2nd gate
        v             v
-w1-->  |             |
 --w2-->|
--w3--> |          
 --w4-->|             
-w5-->  |             |

 --w1-->|             |
 --w2-->|             
 --w3-->|
 --w4-->|             
 --w5-->|             |

        |      --w1-->|
               --w2-->|
            --w3-->   |
             --w4-->  |
        |      --w5-->|

        |      --w1-->|
               --w2-->|
               --w3-->|
               --w4-->|
        |      --w5-->|

--w1--> |             |
        |              --w2-->
 --w3-->|
--w4--> |             
        |             | --w5-->

Below are two solutions using above idea but their implementations are slightly different. Here is the code to test two proposed ideas:

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "time"

    // Set this import spec to point
    // to the copy of one of proposed
    // solutions.
    "path/to/package/barrier"
)

func init() {
    rand.Seed(time.Now().Unix())
}

type counter struct {
    c int
    sync.Mutex
}

func (c *counter) Incr() {
    c.Lock()
    c.c += 1
    c.Unlock()
}

func (c *counter) Get() (res int) {
    c.Lock()
    res = c.c
    c.Unlock()
    return
}

func worker(c *counter, br *barrier.Barrier, wg *sync.WaitGroup) {
    for i := 0; i < 3; i++ {
        br.Before()
        c.Incr()
        br.After()
        time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
        fmt.Println(c.Get())
    }
    wg.Done()
}

func main() {
    var wg sync.WaitGroup
    workers := 3
    br := barrier.New(workers)
    c := counter{}
    for i := 0; i < workers; i++ {
        wg.Add(1)
        go worker(&c, br, &wg)
    }
    wg.Wait()
}

Barrier must implement Before and After methods which are 1st and 2nd gates respectively.

Solution #1

Buffered channels with capacity 1 will be needed:

ch := make(chan int, 1)

Gate is implemented by receive from channel followed by sending to it:

<-ch
ch <- 1

If number of unread elements is 1 then gate is open. It’ll pass exactly one worker and then worker will enqueue new element to pass another worker which will put another element… (you see what is going on here).

If there’s no queued elements then gate is closed and worker will block on receiving from channel.

// github.com/mlowicki/barrier
package barrier 

import "sync"

type Barrier struct {
    c      int
    n      int
    m      sync.Mutex
    before chan int
    after  chan int
}

func New(n int) *Barrier {
    b := Barrier{
        n:      n,
        before: make(chan int, 1),
        after:  make(chan int, 1),
    }
    // close 1st gate
    b.after <- 1  
    return &b
}

func (b *Barrier) Before() {
    b.m.Lock()
    b.c += 1
    if b.c == b.n {
        // close 2nd gate
        <-b.after
        // open 1st gate
        b.before <- 1
    }
    b.m.Unlock()
    <-b.before
    b.before <- 1
}

func (b *Barrier) After() {
    b.m.Lock()
    b.c -= 1
    if b.c == 0 {
       // close 1st gate
       <-b.before
       // open 2st gate
       b.after <- 1
    }
    b.m.Unlock()
    <-b.after
    b.after <- 1
}

Solution #2

This one uses buffered channels with capacity equal to the number of workers — n. Instead of going through each gate one worker by another, now we’ll put into channel exactly n elements just to pass all workers within single loop:

// github.com/mlowicki/barrier2
package barrier

import "sync"

type Barrier struct {
    c      int
    n      int
    m      sync.Mutex
    before chan int
    after  chan int
}

func New(n int) *Barrier {
    b := Barrier{
        n:      n,
        before: make(chan int, n),
        after:  make(chan int, n),
    }
    return &b
}

func (b *Barrier) Before() {
    b.m.Lock()
    b.c += 1
    if b.c == b.n {
        // open 2nd gate
        for i := 0; i < b.n; i++ {
            b.before <- 1
        }
    }
    b.m.Unlock()
    <-b.before
}

func (b *Barrier) After() {
    b.m.Lock()
    b.c -= 1
    if b.c == 0 {
        // open 1st gate
        for i := 0; i < b.n; i++ {
            b.after <- 1
        }
    }
    b.m.Unlock()
    <-b.after
}

Resources

• “The Little Book of Semaphores” by Allen B. Downey

If you’ve found alternative solution please share in comments.

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.

Reusable barriers in Golang was originally published in golangspec on Medium, where people are continuing the conversation by highlighting and responding to this story.

Server

To test this change please launch simple HTTP(S) proxy server written in Golang:

HTTP(S) Proxy in Golang in less than 100 lines of code

Client

package main

import (
    "crypto/tls"
    "fmt"
    "net/http"
    "net/http/httputil"
    "net/url"
)

func main() {
    u, err := url.Parse("https://localhost:8888")
    if err != nil {
        panic(err)
    }
    tr := &http.Transport{
        Proxy: http.ProxyURL(u),
        // Disable HTTP/2.
        TLSNextProto: make(map[string]func(authority string, c *tls.Conn) http.RoundTripper),
    }
    client := &http.Client{Transport: tr}
    resp, err := client.Get("https://google.com")
    if err != nil {
        panic(err)
    }
    defer resp.Body.Close()
    dump, err := httputil.DumpResponse(resp, true)
    if err != nil {
        panic(err)
    }
    fmt.Printf("%q", dump)
}

1.9 vs 1.10

> go version
go version go1.10 darwin/amd64
> go run proxyclient.go
"HTTP/1.1 200 OK\r\nTransfer-Encoding: ...

> go version
go version go1.9 darwin/amd64
> go run proxyclient.go
panic: Get https://google.com: malformed HTTP response "\x15\x03\x01\x00\x02\x02\x16"

...

In the first output where Go 1.10 is used we’ve received correct response from https://google.com proxied by server listening on https://localhost:8888. 2nd result shows that HTTP client in Go 1.9 is confused.

👏👏👏 below to help others discover this story. Please follow me here or on Twitter if you want to get updates about new posts or boost work on future stories.