Goroutines seem to be interrupted despite the presence of a WaitGroup

Question

I have a problem with goroutines not concluding in spite of a WaitGroup. In the code appended, you can see an implementation of Heap's algorithm for permutations. I wanted to speed it up, and so I created a goroutine for every possible first number and thereby decreased the permutations per goroutine to (n-1)!. In total, I should still have n! permutations (n*(n-1)! = n!), but my main routine seems to exit before the sub routines are finished. I then tried tracking the executed permutations. Against my belief, the number of permutations executed isn't constant, but always a bit (for low n) or very much (for large n) under n!.

For example, the permutations for n=4 is 24 every time, that is 4! and thereby all goroutines have finished. If I have a higher number like n=8, I get a value around 13500 and not the expected 40000 = 8!.

Where does this behavior come from? How can I ensure that all my goroutines have finished before the main program exits?

package main

import (
    "fmt"
    "sync"
)

var wg sync.WaitGroup
var permutations int

func main() {

    n := 9

    wg.Add(n)

    for i := 0; i < n; i++ {

        var arr []int
        for j := 0; j < n; j++ {
            if i != j {
                arr = append(arr, j+1)
            }
        }
        go threadFunction(n-1, i+1, arr)
    }

    wg.Wait()

    fmt.Println(permutations)
}

func threadFunction(k int, suffix int, arr []int) {

    defer wg.Done()

    heapPermutation(k, suffix, arr)
}

func heapPermutation(k int, prefix int, arr []int) {

    if k == 1 {
        arr = append(arr, prefix)
        // fmt.Println(arr)
        permutations++
    } else {
        heapPermutation(k-1, prefix, arr)

        for i := 0; i < k-1; i++ {
            if k%2 == 0 {
                arr[i], arr[k-1] = arr[k-1], arr[i]
            } else {
                arr[0], arr[k-1] = arr[k-1], arr[0]
            }
            heapPermutation(k-1, prefix, arr)
        }
    }
}

(The same behavior can be easily achieved, e.g. on https://go.dev/play/, thus it is very much reproducible.)

Answer 1

In your code, goroutines access permutations variable concurrently. When you increase value of n, the workload increases and it becomes the issue leading to an unexpected result.

You can use a mutex, it will ensure that only one goroutine can access the permutations at the time.

package main

import (
    "fmt"
    "sync"
)

var wg sync.WaitGroup
var permutations int
var permutationsMutex sync.Mutex

func main() {

    n := 9

    wg.Add(n)

    for i := 0; i < n; i++ {

        var arr []int
        for j := 0; j < n; j++ {
            if i != j {
                arr = append(arr, j+1)
            }
        }
        go threadFunction(n-1, i+1, arr)
    }

    wg.Wait()

    fmt.Println(permutations)
}

func threadFunction(k int, suffix int, arr []int) {

    defer wg.Done()

    heapPermutation(k, suffix, arr)
}

func heapPermutation(k int, prefix int, arr []int) {

    if k == 1 {
        arr = append(arr, prefix)
        permutationsMutex.Lock()
        permutations++
        permutationsMutex.Unlock()
    } else {
        heapPermutation(k-1, prefix, arr)

        for i := 0; i < k-1; i++ {
            if k%2 == 0 {
                arr[i], arr[k-1] = arr[k-1], arr[i]
            } else {
                arr[0], arr[k-1] = arr[k-1], arr[0]
            }
            heapPermutation(k-1, prefix, arr)
        }
    }
}