Goroutines appear to be interrupted despite the existence of WaitGroup

Question content

I have a problem with goroutine not ending despite the existence of waitgroup. In the attached code you can see the implementation of the heap permutation algorithm. I wanted to speed things up, so I created a goroutine for each possible first number, thus reducing the permutations of each goroutine to (n-1)!. Overall, I should still have n! permutations (n*(n-1)!= n!), but my main routine seems to finish before the subroutine Exit before. Then I try to keep track of the permutations performed. Contrary to my belief, the number of permutations performed is not constant, but always somewhat (for low n) or very much (for large n#) under n! ##).

For example

n=4 Each time the permutation is 24, that is 4!, so all goroutines are finished. If I had a higher number, say n=8, I would get a value around 13500 instead of the expected 40000 = 8!.

Where does this behavior come from? How to ensure that all goroutines have completed 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/, so it's very reproducible.)

Correct answer

In your code, the goroutine also accesses

permutations variables. As you increase the value of n, the amount of work increases, which can become a problem leading to unexpected results.

You can use

mutex, which will ensure that only one goroutine has access to 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)
        }
    }
}

The above is the detailed content of Goroutines appear to be interrupted despite the existence of WaitGroup. For more information, please follow other related articles on the PHP Chinese website!