Sufficiently large product will hang

[relwell]

Here's an example, with go-cartesian-product code included. Note that we're just adding in this bitproduct function that uses a variadic function to give us functionality like Python's itertools.product("01", repeat=int(sys.argv[1])):

This will spin up between 6500 and 8000 goroutines, which leads me to believe that something isn't being cleaned up when there is a sufficient degree of recursion happening.

package main

import (
	"fmt"
	"os"
	"runtime"
	"strconv"
	"sync"
)

// takes interface-slices and returns a channel, receiving cartesian products
func Iter(params ...[]interface{}) chan []interface{} {
	// create channel
	c := make(chan []interface{})
	// create waitgroup
	var wg sync.WaitGroup
	// call iterator
	wg.Add(1)
	iterate(&wg, c, []interface{}{}, params...)
	// call channel-closing go-func
	go func() { wg.Wait(); close(c) }()
	// return channel
	return c
}

// private, recursive Iteration-Function
func iterate(wg *sync.WaitGroup, channel chan []interface{}, result []interface{}, params ...[]interface{}) {
	// dec WaitGroup when finished
	defer wg.Done()
	// no more params left?
	if len(params) == 0 {
		// send result to channel
		channel <- result
		return
	}
	// shift first param
	p, params := params[0], params[1:]
	// iterate over it
	for i := 0; i < len(p); i++ {
		// inc WaitGroup
		wg.Add(1)
		// call self with remaining params
		go iterate(wg, channel, append(result, p[i]), params...)
	}
}

func bitproduct(repeat int) chan []interface{} {
	arr := make([][]interface{}, repeat)
	for i := range arr {
		arr[i] = []interface{}{"0", "1"}
	}

	return Iter(arr...)
}

func main() {
	i, err := strconv.Atoi(os.Args[1])
	if err != nil {
		panic(err)
	}

	for j := range bitproduct(i) {
		fmt.Println(runtime.NumGoroutine())
		fmt.Println(fmt.Sprintf("%v", j))
	}
}

[schwarmco]

you're right, @relwell - since the products are made recursively, the deeper you go, the longer it takes (exponentially)... i've tested your case and got 10 seconds for repeat=20 and 65 seconds for repeat=30...

although i've tested some ideas - involving a worker-queue or a non-recursive solution - none gave better overall performance...

afar from that this is a problem, your specific problem may be solved a lot easier like that:

repeat := 20
format := "%0" + strconv.FormatInt(int64(repeat), 10) + "b"

// iterating from 0 to the point, where i's length matches "repeat"
for i := 0; bits.Len(uint(i)) <= repeat; i++ {
    res := fmt.Sprintf(format, i)
    fmt.Println(res)
}

[control4nothing]

One way to get a more deterministic thread count is to create a thread per column instead of per row (where the column is the number of elements in the output list and where the row is the combination of all lists). In this way, the thread count would only be as large as the number of output columns no matter how long the lists of possible values may be. Your comment above hits at this solution already, so you may have already thought of this...

Each column would be a channel, and the channel would produce the proper column combo depending on its position in the column list.

Take example ListA=[1, 2, 3, 4, 5], ListB=[a, b, c, d], ListC=[!, @, #, $, %, ^]
column1 channel => 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ....
column2 channel => a, a, a, a, a, b, b, b, b, b, ....
column3 channel => !, !, !, !, !, !, !, !, !, !, !, !, !, !, !, !, !, !, !, !, @, .....

Each thread would likely need to be passed the following:

1. The list of values for that column.
2. The product length of the list 5x4x6 (in my example above)
3. The lengths of the previous list (this is the column inheritance), which would determine a repeat count for each value in the list.

Also, this solution could allow the caller to request fewer combos than the total list of products.

NOTE: I don't know if this would be more efficient, but it is more deterministic.

Sorry I haven't provided any coding to help. I'm new to GoLang so I'm not very comfortable putting a hack out there that is full of issues.

[ramoncjs3]

Not resolved so far.....

[tabvn]

Need implement if bulk of generation reached of Go max goroutines

[soypat]

I've made a PR with a different approach- it may solve this issue?

[soypat]

This may be fixed in latest version!