understand the code - Go concurrency pattern: Daisy Chain

Question

I was studying Go concurrency pattern.

One pattern I am not sure is： Daisy Chain https://talks.golang.org/2012/concurrency.slide#39

It's very hard for me to understand the control flow of the code.

Can someone explain to me ?

package main

import (
    "fmt"
)

func f(left, right chan int) {
    left <- 1 + <-right
}

func main() {
    const n = 10000

    leftmost := make(chan int)
    right := leftmost               //point B: what does these do ?
    left := leftmost

    for i := 0; i < n; i++ {
        right = make(chan int)
        go f(left, right)
        left = right                //point A
    }
    go func(c chan int) { c <- 1 }(right)  
    fmt.Println(<-leftmost)
}

Conclusion:

1. the flow of channel going from right to left. It is good practice to write func f(left chan<- int, right <-chan int) rather than original function signature as above.

2. 'chain reaction' does not start until c <- 1, when signal 1 is sent to right most channel, reaction goes all the way to left most end. Print out 10001.

The reason is go channel block 'read' until received channel receive signal.

3. @Rick-777 shows how to use array like structure for easy understanding. Since each go coroutine is just around 6k big. It's not a bad idea to make 10k channel.

4. I clean up some code around Point B, for channel initialization. Here is the source code: http://play.golang.org/p/1kFYPypr0l

Answer 1

VonC has already given a direct answer. Here are some further remarks.

A slightly tidied-up version is in the playground, the difference being that the channels passed as parameters have their direction specified explicitly, ie. <-chan and chan<-. It's good practice to do this because the compiler can catch more mistakes for you.

An alternative and equivalent program that has a daisy-chain of n goroutines can be written using an array of channels instead. This allocates the same total number of channels using fewer lines of code. See playground:

package main

import (
    "fmt"
)

func f(left chan<- int, right <-chan int) {
    left <- 1 + <-right
}

func main() {
    const n = 10000

    // first we construct an array of n+1 channels each being a 'chan int'
    var channels [n+1]chan int
    for i := range channels {
        channels[i] = make(chan int)
    }

    // now we wire n goroutines in a chain
    for i := 0; i < n; i++ {
        go f(channels[i], channels[i+1])
    }

    // insert a value into the right-hand end
    go func(c chan<- int) { c <- 1 }(channels[n])

    // pick up the value emerging from the left-hand end
    fmt.Println(<-channels[0])
}

I hope you can see now how the original program is equivalent to this program. There is one minor difference: the original program does not create any channel array, so uses just a little less memory.

Answer 2

It illustrates you can generate a large number of goroutines.

Here, each go f(left, right) blocks: left <- 1 + <-right blocks because it waits for right to get a value. See "do golang channels maintain order".
All channels created here are unbuffered channels.

All 10000 goroutines are created.

Point B: right and left are declared, using the short variable declaration.

• right is initialized to leftmost, but it doesn't matter, because it will be reassigned to a new channel in the for loop (right = make(chan int)).
  Another way to declare right would have been:

  var right chan int
  

• left is initialized with leftmost, the very first channel created.

Point A: But once that channel start waiting (left <- 1 + <-right), the for loop set left to right, and created a new right: that is how the daisy chain is build

 left <- (new) right (now left) <- (new) right (now left) <- ...

Then, one value is sent to the last right channel created: {c <- 1 }(right)

And you wait for the first leftmost channel created to receive its value (incremented 10000 time).

Since receivers always block until there is data to receive, the main() function itself doesn't exit before leftmost finally receive its value.
If main() exited too soon, the daisy chain wouldn't have time to complete.

Answer 3

I found dry-run this program could be really helpful to understand it.

At first, after executing

leftmost := make(chan int)
right := leftmost
left := leftmost

leftmost, left, and right are all referring to the same chan int

[chan int]
     |                 
left, leftmost, right

Let's run some iterations for the for-loop.

i = 0

When we just enter the for loop,

[chan int]
     |                 
left, leftmost, right

after executing right = make(chan int) and go f(left, right).

[chan int] <-(+1)- [chan int]
     |                 |
left, leftmost        right

after executing left = right

[chan int] <-(+1)- [chan int]
     |                 |
  leftmost        left, right

i = 1

When we just enter the for loop,

[chan int] <-(+1)- [chan int]
     |                 |
  leftmost        left, right

after executing right = make(chan int) and go f(left, right).

[chan int] <-(+1)- [chan int] <-(+1)- [chan int]
     |                 |                   |
  leftmost            left               right

after executing left = right

[chan int] <-(+1)- [chan int] <-(+1)- [chan int]
     |                                     |
  leftmost                            left, right

I feel like two loops are enough to see the pattern:

• Every loop we create a new chan int and append it at the end of the "linked list of chan int".
• So after n = 100000 loops, we created 100000 new chan int, and the number of chan int in the "linked list of chan int will be 100001.
• 100001 chan int means 100000 gaps between each pair of adjacent chan int, and each gap means one +1.

Before the for loop, because all chan int are acting as receivers and there is no pass-in value, so all chan int will just wait.

After the for loop, we execute go func(c chan int) { c <- 1 }(right), then the 1 is passed into the "linked list of chan int" and perform +1 on the value for 100000 times, so the final result to the leftmost will be 100001.

Things will be like when we pass 1 into the "linked list of chan int":

[chan int] <-(+1)- [chan int] <-(+1)- ...... <-(+1)- [chan int] <- 1
     |                                                   |
  leftmost                                           left, right

I created a leetcode playground holding all the code. You could try it here (https://leetcode.com/playground/gAa59fh3).