Enque and deque deadlocks the channel

I am trying to implement a queue, dequeueing and requeueing in a single channel.

I have two questions:

• why do I obtain a deadlock? I was expecting an infinite loop (since I am requeueing even elements which generate more elements and so on). Shouldn't the range queue always listening to the channel?

• this is part of the print before the deadloks:

  enqueueing 1000
enqueueing 1001
dequeued 1001
dequeued 1001
using 1001
using 1001

Are two different goroutines dequeueing the same element? I don't understand why this data race; I thought that the range would pick one per time.

Code in Playground

func main() {

	queue := make(chan int)
	start := 10

	go func() { queue <- start }()

	for element := range queue {
		fmt.Println("dequeued ", element)
		go enqueue(element, queue)
	}
}

func enqueue(element int, queue chan int) {
	fmt.Println("using ", element)
	if element%2 == 0 {
		fmt.Println("creating new elements from ", element)
		var news = []int{element * 100, element*100 + 1}

		for _, new := range news {
			fmt.Println("enqueueing ", new)
			go func() { queue <- new }()
		}

	}
}

It's a scope problem. This happens a lot when getting started with go func() {...}; it might be more common than real problems with concurrency. There are sections in the FAQ and the Go wiki about it.

The anonymous func you create gets a reference to a variable in the outer scope, not to its value at the time the func statement runs. And that loop variable is updated each pass through the loop, so it changes between your go statement and when the goroutine actually runs.

You can work around this by declaring another variable during each iteration of the loop (i.e., inside the for braces). If your loop was for i := range arr {...} you could just add i := i. So, this bad version:

arr := make([]int, 10)
for i := range arr {
	go func() { 
		fmt.Println(i)
    }()
}

...always prints 9. A fixed version, redeclaring i inside the loop:

arr := make([]int, 10)
for i := range arr {
    i := i
	go func() { 
		fmt.Println(i)
    }()
}

...prints 0-9. A different, arguably more elegant way to redeclare i is to make it a param of the anonymous func; then it's not a weird-looking standalone statement:

arr := make([]int, 10)
for i := range arr {
	go func(i int) { 
		fmt.Println(i)
    }(i)
}

Here's that code. For all of the Playground versions, I had to add synchronization so main wouldn't exit before the goroutines run.

It's confusing that a declaration that "runs" once each time through the loop behaves differently (weird way for scope to manifest) but the way to get around it is straightforward enough.

In your case: queue <- new can run at any time, and it turns out to run after you've gone through the for _, new loop entirely. However, it uses whatever the value of new is as of when it actually runs, not as of when the go statement was executed. In this case, both the goroutines you start get the value 1001, the so second time through both values passed into enqueue are odd (you can see that as two using 1001s in your output) so nothing writes to the queue, so there is nothing for the range queue loop to consume. The channel isn't closed either, so the main can't just end, so you get a deadlock.

You want a different value to be "captured" for each execution of the goroutine. For that, you can put new := new at the top of the loop, as funny as that looks. That's enough to make the value from each iteration a "different var" from Go's perspective, so you get 1000 and 1001 inserted in the channel.

Once you've actually got it working, the Playground won't actually run your code successfully because it loops forever and there are a zillion goroutines running and I guess the Playground doesn't like that (overusing resources). If you add a limit of 100 elements dequeued before quitting, you get http://play.golang.org/p/bBM3uTnvxi . You'll also notice the numbers it outputs get weird because multiplying by 100 each time will eventually overflow the machine's int type, but that's just how it goes writing programs in lowish-level languages.

As a minor thing, you probably don't want to name a variable new because that's also the name of a built-in function. It's legal to do so, just confusing. (It can be kind of reflexive to name a length variable len, especially if nothing was wrong with that in the language you're coming from.)

> why do I obtain a deadlock? I was expecting an infinite loop (since I am requeueing even elements which generate more elements and so on). Shouldn't the range queue always listening to the channel?

When a range loop over a channel reaches the end of the channel's buffer (if the channel has one) it will block, waiting for more elements to be sent through the channel. If there are no other running or runnable goroutines then we've reached a deadlock.

Minimal example:

http://play.golang.org/p/Vb4-RFEmm3

package main

func main() {

	queue := make(chan int)

	for _ = range queue {
	}
}

> Are two different goroutines dequeueing the same element?

No. What's happening is that this line (26):

go func() { queue <- new }()

instructs Go's runtime to schedule a new goroutine, it does not necessarily execute immediately. When the goroutine effectively runs, new's value is 1001, not 1000 as printed.