Make It Real Elite — Week 2: Recursivity, concurrency and Goroutines

I bet you’ve heard of Sudoku before. I bet you did try to play and solve many times this famous game. If you haven’t tried yet, well here are the rules: a number from 1 to 9 can be present once and just once for each row, column and 3x3 sub-boxes. Pretty simply, right? Tell me how it goes, if you have just started to play it. :)

Well, you’ve guessed. I wouldn’t just randomly bring Sudoku up. One of the algorithms I’ve built during the last days is a Sudoku solver using recursive function calls, and backtracking technique.

The solution is very simple, but it requires a lot of computation. Here’s why. We first iterate over every incomplete position (0 = incomplete) in the board (9 x 9 matrix of integers with values from 1 to 9) defining a potential value and trying to solve the Sudoku problem for this specific value. Are you with me? Good.

Now, let’s say we use the value 3, if a solution is found during the recursive calls we did, the problem is solved and we are all happy. If not, and here comes the exciting part, we suppose a new value, let’s say 4 for this case, and repeat the process again until we arrive to the correct solution or we simply exhaust all the possible options, arriving to a “no solution found at this point”.

If you have any questions, let me know in the response section. The code is in the snippet below:

You can check the entire code here, if you have any question let me know in the responses section. The execution time is in the snippet below:

Solve calls: 19893
total time taken  0.004616523 seconds
Solve calls: 770
total time taken  0.000174626 seconds
Solve calls: 188818
total time taken  0.040048885 seconds
PASS
ok   sudoku_problem 0.051s

As you may note this looks like a bunch of effort. But, how about if we split the work, and instead of processing one possible solution at a time, we will try to find 3, 5 or 9 potential solutions at the same time. Can we change this algorithm to make it run faster?

Concurrency and Parallelism

I think this is one of the most misunderstood topics in the programming world because they are different, they are simply not the same. But, the beauty of their differences is that when one is using the other, things actually get better. So let’s try it out.

The simplest concept to explain for me is parallelism: doing lot of things at once. We leave in parallel world, let’s suppose you and I go to the store, we need cookies and ice cream, we arrive at the same time and you go for the cookies and I take my way for the ice cream, we are operating in parallel, at the same time, easy, basic, fundamental, doesn’t?.

On the other hand, concurrency, is a bit tricky. Here’s why. It represents a structure, an organization, a step by step formula of a process dealing with a lot of things at once. Let’s go back to the store example from above. This time we both arrive to the store, but now I will be waiting until you take the cookies, so I can go for the ice cream. The interesting point here is that we can scale concurrency with parallelism, thus we can invite two more friends and work with the same concurrency schema and get double the amount of cookies and ice cream, within the same interval of time. This must sound just fantastic for cookies and ice cream lovers.

Thank you so much, Rob Pike! This realization wasn’t possible without your amazing talk about “Concurrency is not parallelism”. There are tons of sources where you can learn about these concepts, so for now, let’s continue with some coding before this article gets too long.

Concurrency in Go

Go is a concurrency language which has an amazing functionality called Goroutines, defined as lightweight threads of execution. Among the Goroutines you will find: channels, buffered channels, directional channels, wait groups, worker pools, the select statement, and some other special ones to design your code concurrently and implement it fast and easily. Let’s take a look at this little example using recursion, since you can imagine what’s coming next:

Recursive function to calculate the factorial result using Goroutines and channels.

This example is really simple, but it’s a powerful illustration. Let’s dig further. First, we start with creating a new goroutine in line #24, calling the factorial function. We then send the number, the current product value, and the channel where we want to be notified when the value is computed as arguments.

The factorial function calculates the result between the given number and the current result. Next, to be considered is what’s called an “anchor” or a “recursive clause”. If the value on number is equal to 1, it means we are done. Thus, we simply write in the channel the current product value, and the return statement is coming in line 12 to stop the execution of the function, since we already found our final value. If the value of the number is different than 1, it means we are not done yet, so we skip this condition and we trigger a new goroutine with the new arguments.

Finally, in line 26 we block the sequential execution of the code, and we wait until any of our goroutines sends a message through the channel. When it’s done, we store this value in the answer variable to print it later.

Sudoku, concurrency and Go
At this point you can have a better idea about how we can improve our first algorithm using concurrency. Before showing the final version of the code I’d like to highlight some key points I found during this process. They might prove quite handy. Here they are.

1. Data access: In our first version of the code all the methods belonged to a Sudoku structure. Since we were executing only one “Solve” function called at a time, we didn’t have any problems to read/write in the matrix. However, this is not the case for our concurrency approach, where we want to bring independence to our goroutines, and to avoid any collision or data inconsistency. For this reason, we removed the structure and the current state of the grid was passed as a parameter to every method in the code.
2. Non return values: The execution of a goroutine depends on the state of our computer at the moment when we triggered the function. Thus, we can’t know when the computation is done. However, we can block and wait until a several amount of Goroutines are finished, but you should keep in mind that it’s not the most optimal way as our goal is to have our Goroutines running as free as possible. For this reason, we will not use return values, therefore our Goroutines will communicate between then using channels.
3. Faster execution: “Go select statement” is an helpful concept when we assign different goroutines to run for the same result. We just don’t care about who’s arriving with the result value first, as we only want the value, and when the first solution is found we stop the execution and return the value to the user. “Channels” are a great tool since they help us to simplify the communication between “threads”, but keep in mind that communication is one of the most complex matters when you are working with concurrency and parallelism.
4. Anchor or recursive clause: Among pass the matrix as a parameter for every function call, we need to check if the current state of the board is correct when there aren’t more pending values to guess. It implies writing the logic to confirm every position in the Sudoku board to be valid in the row, column and 3x3 sub-box, but discarding the value of its current position. I have called this section quality assurance and you can check it here.

I think we are ready, so let’s check our code:

Solve() function. Entry point to start with the Sudoku computation.

The Solve() function is the starting point to solve the Sudoku problem. Whitin this function we create the channel where we will receive the final solution. Then, we find a pending position. If there are not pending positions, it means the Sudoku is already solved so we return true and the current state of the board. Otherwise, we dispatch a goroutine with the value for each valid potential solution in the pending position. Finally, we declare a “select statement” which means: “When there is a final solution sent to this channel, then read the grid from the channel, store its value in the solution, and return it”.

Now let’s check the recursiveSolution() function:

recursiveSolution() function makes recursive goroutines until a new solution is found it and sent it to the channel.

The code here is a quite different, first we try to find the next pending position. If there aren’t anymore pending positions, and the board — after passes through quality assurance, it proves valid-, It means we found our solution and we are done. Thus, we write in the channel and we closes the channel since we are not more interested in find more results. Otherwise if we still have work to be computed, we trigger a new recursiveSolution() goroutine for each hypothetical solution, and we wait until one of them if what we are looking for. If we find it, we then notify the channel.

At this point you might be wondering about the execution time, but before talking about this point, we need to clarify that the execution and the number of calls to the “recursive” function depend on the current state of our processor, and one thes tasks it has to processes in that moment. Here I will run three times the test suite, let’s see what happens:

1. Execution #1

Solve calls: 18463
total time taken  0.008581368 seconds
Solve calls: 10464
total time taken  0.003643741 seconds
Solve calls: 39235
total time taken  0.016856554 seconds
PASS
ok   concurrent_sudoku 0.039s

2. Execution #2

Solve calls: 25862
total time taken  0.010786207 seconds
Solve calls: 3189
total time taken  0.001334907 seconds
Solve calls: 225616
total time taken  0.094413676 seconds
PASS
ok   concurrent_sudoku 0.114s

3. Execution #3

Solve calls: 13325
total time taken  0.006723603 seconds
Solve calls: 11469
total time taken  0.004197734 seconds
Solve calls: 90705
total time taken  0.040145053 seconds
PASS
ok   concurrent_sudoku 0.058s

As you can see from the results above, the amount of time and the number of execution calls can change drastically. This is related to what we mentioned before about our CPU conditions. Sometimes we can run faster than the pure sequential and recursive approach. On the other hand, we can run it slowly, for a few milliseconds, and then we can spend double the time processing all the board, since there is no standardized way to know the resources in our CPU. ( By the time we execute the code, we can’t define a fixed amount of time. Interestingly, by using concurrency, I think we added more load, more operations and steps to reach our final solution. We are really close to the same value or execution time, when we compare it to the first approach.

If you want to check more about algorithms using Go, you can visit the repository. Don’t forget to check the readme file also. I would appreciate any comment, feedback or contribution. Till next time, cheers!

Mardiniii/go-algorithms

If you want to learn more about Go and concurrency, you can visit the next links:

1. Concurrency Section by Naveen Ramanathan— https://golangbot.com/learn-golang-series/
2. Expressive concurrency: Go Sudoku solver by Andrew Gerrand — https://nf.id.au/posts/2010/07/expressive-concurrency-a-go-sudoku-solver-pt.html
3. Recursion and tails with Go by William Kennedy — https://www.ardanlabs.com/blog/2013/09/recursion-and-tail-calls-in-go_26.html
4. Visualizing Concurrency in Go by Ivan Daniluk — http://divan.github.io/posts/go_concurrency_visualize/
5. Visualizing Concurrency in Go Talk by Ivan Daniluk — https://www.youtube.com/watch?v=KyuFeiG3Y60
6. Concurrency Is Not Parallelism by Rob Pike — https://www.youtube.com/watch?v=cN_DpYBzKso&t=151s