I’ve been learning how to program in Go, and I thought it’d be interesting to try to implement a combinatorial algorithm I remember from school. I first implemented the same solution I had written in Java, and then realized it could be possible to use goroutines to add some concurrency to the solution. After the update, I was a bit surprised to see that the concurrent solution is actually much slower than the original one.

I have some ideas of what could be causing it to be slower: recursive concurrency is probably overkill for this problem, the amount of threads is too big to coordinate efficiency, or maybe the algorithm itself is sound but it’d work better on a more advanced CPU than my ‘simple’ dual-core Intel i5. But I’m not sure I fully understand concurrency and how it’s implemented so I think this could be a good opportunity to try to understand it better.

This is the problem:

```
given an initial amount of a drink (int)
and a list of possible sizes for your bottles (int slice),
you have to try to fit as much of the initial amount into your bottles.
You can use each bottle size however many times needed.
Determine what is the smallest possible wasted amount that cannot fit
into any available bottle (int).
Ideally, also return the path that allows this minimal waste,
ie the combination of bottle-sizes resulting in minimal waste.
```

My initial non-concurrent solution (pseudocode, see below for full program):

```
for each bottle-size:
subtract bottle-size from amount
call this same function with resulting amount, same list of bottle-sizes
do this until all of the bottle-sizes are bigger than the remaining amount
return the remaining wasted amount
```

My concurrent algorithm (pseudocode):

```
same basic algorithm as regular subtraction approach,
but inside of the for loop, rather than
simply calling the function recursively,
start a new goroutine. All routines from the same loop share a channel.
after starting all the goroutines,
receive from the channel until you get the minimal waste from each routine
return the minimal waste amount found
```

Here’s the code of how I’ve actually implemented both solutions:

```
package main
import (
"fmt"
"time"
)
/*
Minimal Waste of Drink Problem:
given an initial amount of a drink (int)
and a list of possible sizes for your bottles (int slice),
you have to try to fit as much of the initial amount into your bottles.
You can use each bottle size however many times needed.
Determine what is the smallest possible wasted amount that cannot fit
into any available bottle (int).
Ideally, also return the path that allows this minimal waste,
ie the combination of bottle-sizes resulting in minimal waste
*/
type resultingTree struct {
wasted int // the amount of drink we couldn't fit in any bottle
path map[int]int // key: bottle-size, value: how many times this size is used
}
func timer(name string, start time.Time) { // to time how long a function takes
fmt.Printf("n____%s took %vn", name,
time.Since(start))
}
func callIt(which int) int { // helper function to set up the test
amount := 4333
bottles := []int{5, 7, 13}
var theFunc func(bottles []int, amount int) *resultingTree
var funcName string
switch which {
case 0:
theFunc = outerSub
funcName = "outerSub"
case 1:
theFunc = outerConcur
funcName = "outerConcur"
}
fmt.Println("calling", funcName, "with amount:", amount)
fmt.Println("and bottles:", bottles)
rt := theFunc(bottles, amount)
path := rt.path
res := rt.wasted
for key, element := range path {
fmt.Print(key, " *", element, ", ")
}
fmt.Println()
fmt.Println("res:", res)
return res
}
// 'simple' subtraction approach:
// for each bottle-size:
// subtract bottle-size from amount
// call this same function with resulting amount, same list of bottle-sizes
// do this until all of the bottle-sizes are bigger than the remaining amount
// return the remaining wasted amount
func outerSub(bottles []int, amount int) *resultingTree {
defer timer("simple subtraction approach", time.Now())
rtp := subMinWaste(bottles, amount)
return rtp
}
func subMinWaste(bottles []int, amount int) *resultingTree {
min := amount
path := make(map[int]int)
rt := resultingTree{amount, path}
rtp := &rt
if amount == 0 { // speed things up
return rtp
}
for _, b := range bottles {
if amount < b {
continue
}
internal := subMinWaste(bottles, amount-b)
if (*internal).wasted < min {
min = (*internal).wasted
rtp = internal
rtp.path[b] = rtp.path[b] + 1
if min == 0 {
break // speed things up
}
}
}
return rtp
}
// CONCURRENCY approach:
// same basic algorithm as regular subtraction approach,
// but inside of the for loop, rather than
// simply calling the function recursively,
// start a new goroutine. All routines from the same loop share a channel.
// after starting all the goroutines,
// receive from the channel until you get the minimal waste from each routine
// return the minimal waste amount found
func outerConcur(bottles []int, amount int) *resultingTree {
defer timer("concur approach", time.Now())
path := make(map[int]int)
rt := resultingTree{amount, path}
rtp := &rt
c := make(chan *resultingTree)
go concurMinWaste(bottles, amount, c)
rtp = <-c
return rtp
}
func concurMinWaste(bottles []int, amount int, outerC chan *resultingTree) {
// fmt.Println("nconcurring, amount:", amount)
min := amount
path := make(map[int]int)
rt := resultingTree{amount, path}
rtp := &rt
if amount == 0 { // speed things up
outerC <- rtp
}
numRoutines := 0
c := make(chan *resultingTree)
for _, b := range bottles {
if amount < b {
continue
}
go concurMinWaste(bottles, amount-b, c)
numRoutines++
}
for i := 0; i < numRoutines; i++ {
internal := <-c
if (*internal).wasted < min {
// updating the min here
// couldn't find a way to set up the path:
// since we don't know which goroutine is sending via the channel,
// we don't know which bottle-sizes are responsible for this min
min = (*internal).wasted
rtp = internal
if min == 0 {
break // speed things up
}
}
}
outerC <- rtp
}
func main() {
fmt.Println("Welcome to MinWasteDrink")
fmt.Println("---------------------")
for i := 0; i < 2; i++ {
callIt(i)
fmt.Println("n")
}
}
```

You can check out the code on the Go playground as well. When I run it in my terminal I get these results:

```
bash-3.2$ MinWasteDrink
Welcome to MinWasteDrink
---------------------
calling outerSub with amount: 4333
and bottles: [5 7 13]
____simple subtraction approach took 832.463µs
13 *1, 5 *864,
res: 0
calling outerConcur with amount: 4333
and bottles: [5 7 13]
____concur approach took 14.105725ms
res: 0
```

The concurrent approach is orders of magnitude slower, and it’s even more noticeable with bigger amounts: for amount 4333323, the non-concurrent approach finishes in 500 ms, whereas the concurrent approach seems to take at least minutes (I’ve stopped it before I could see the result.

I hope other people find this problem as interesting as I do. I’d like some explanation of what specifically is causing the concurrent approach to be so slow: is it related to the low-level implementation of concurrency? Are there any changes I could make to my algorithm to make the concurrent solution faster?

Thanks for your help!