Please help me understand concurrency in Go: why is this approach slower than a typical (non-concurrent) one?

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!

Leave a Comment