Concurrency : leaks in Equivalent trees solution

[Ripounet]

Hi Matt
As stated in PR #38, we still have a problem of goroutine leak and channel leak. Some Walk invocations will never return because they are stuck writing in a channel that is not read anymore. I revealed the leaks on my computer by calling Same a large number of times on different trees : the memory footprint of the program, as shown by top, kept growing and growing.

Below I will suggest two possible fixes.

My feeling about concurrency in Go is :

• it makes writing correct concurrent code easier than in other languages ;
• it doesn't prevent from shooting oneself in the foot ;
• it doesn't change the fact that concurrent design in general is difficult and subtle ;
• goroutines and channels have their own subtlety, that we must be aware of ;
• we should stick to the convention that "the writer closes the channel when it's done writing" (and not "the reader closes the channel when it's done reading").

Possible fix 1 : "drain" the channels after use, i.e. loop to read all the potential unused values in ch1 and ch2. So we ensure recWalk will finish and Walk will close the channel, so the goroutines can properly end and the channels will be garbage collected.
Advantage : it is short and straightforward to implement.
Drawback : completing the Walk of a big tree is an undesirable amount of work when the tree comparison returns false early : we should not have to process the remainder of the tree.

Possible fix 2 : create a quit channel for each tree, as described in this slide.
Advantage : no more leaks, no useless work.
Drawback : the code is lengthier and more difficult to write and read.

What do you think?
I can make a pull request for (fix 1) or (fix 2) of the go code, and the paragraph would need to be updated to explain the plumbing.

Cheers

[Ripounet]

I can't attach files but here are the suggested codes for :

• Fix 1
• Fix 2

[rin01]

@Ripounet I am pretty sure that your 2nd solution can block indefinitely if one tree contains one less element than the other :
https://play.golang.org/p/iz5IwT9mZU

To fix your solution, you can buffer quit1 and quit2 channels

quit1 := make(chan Void, 1)
quit2 := make(chan Void, 1)

but the switchlogic remains hard to grasp.

To easily notify a unlimited number of goroutines, the simplest way is to pass them the same quit channel, and just close it when needed. A closed channel unblocks all reads and assigns always the zero value to the receiving variable.
Besides, closing a channel to notify goroutines is the solution proposed in the slide you mentioned:
https://talks.golang.org/2013/bestpractices.slide#33

So, a simpler solution would be:
https://play.golang.org/p/krW3fP9oU2