[go-nuts] implementing sequence combination causes runtime: out of memory

On Feb 24, 2016, at 9:18 PM, Tim Schindler wrote:

Hello, I fell over a memory issue caused by some bad program. See the example here: http://play.golang.org/p/2Wo9t8u7E9. My motivation was to write a sequence generator that gives me all possible combinations of sequences based including empty sets based on given parameters. So when I want to have all combinations for the character set `abc` and a sequence can be up to 3 characters long, I expect something like this.

```
a
aa
ab
ac
aaa
aab
aac
b
ba
bb
bc
bba
bbb
...
```

You get the picture. However, I can implement certain solutions but all of them break at some point with this.

```
fatal error: runtime: out of memory

runtime stack:
runtime.throw(0x51f120, 0x16)
/home/vagrant/.gvm/gos/go1.5/src/runtime/panic.go:527 +0x90
runtime.sysMap(0xc87bba0000, 0x1c040000, 0x59b800, 0x5b9438)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mem_linux.go:143 +0x9b
runtime.mHeap_SysAlloc(0x59b860, 0x1c040000, 0xc820066780)
/home/vagrant/.gvm/gos/go1.5/src/runtime/malloc.go:423 +0x160
runtime.mHeap_Grow(0x59b860, 0xe020, 0x0)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:628 +0x63
runtime.mHeap_AllocSpanLocked(0x59b860, 0xe01e, 0x100)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:532 +0x5f1
```

My idea was to make the implementation linear, because recursion will make the call stack grow. Unfortunately it still looks like the GC is not fast enough (bad guess). As in my playground example I also tried `runtime.GC`, but it did not help.

- Is the problem related to GC?
- How to achieve the task?
- What am I doing wrong?

Thanks for listening.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com For more options, visit https://groups.google.com/d/optout <https://groups.google.com/d/optout>.

On Wednesday, February 24, 2016 at 6:18:09 PM UTC-8, Tim Schindler wrote:

Hello, I fell over a memory issue caused by some bad program. See the
example here: http://play.golang.org/p/2Wo9t8u7E9. My motivation was to
write a sequence generator that gives me all possible combinations of
sequences based including empty sets based on given parameters. So when I
want to have all combinations for the character set `abc` and a sequence
can be up to 3 characters long, I expect something like this.

```
a
aa
ab
ac
aaa
aab
aac
b
ba
bb
bc
bba
bbb
...
```

You get the picture. However, I can implement certain solutions but all of
them break at some point with this.

```
fatal error: runtime: out of memory

runtime stack:
runtime.throw(0x51f120, 0x16)
/home/vagrant/.gvm/gos/go1.5/src/runtime/panic.go:527 +0x90
runtime.sysMap(0xc87bba0000, 0x1c040000, 0x59b800, 0x5b9438)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mem_linux.go:143 +0x9b
runtime.mHeap_SysAlloc(0x59b860, 0x1c040000, 0xc820066780)
/home/vagrant/.gvm/gos/go1.5/src/runtime/malloc.go:423 +0x160
runtime.mHeap_Grow(0x59b860, 0xe020, 0x0)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:628 +0x63
runtime.mHeap_AllocSpanLocked(0x59b860, 0xe01e, 0x100)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:532 +0x5f1
```

My idea was to make the implementation linear, because recursion will make
the call stack grow. Unfortunately it still looks like the GC is not fast
enough (bad guess). As in my playground example I also tried `runtime.GC`,
but it did not help.

- Is the problem related to GC?
- How to achieve the task?
- What am I doing wrong?

Thanks for listening.

On Feb 25, 2016, at 8:08 PM, keithr@alum.mit.edu wrote:

On its last gasp the runtime is asking the OS for 448MB and the OS is saying no. Sounds like you are allocating (and retaining) too much memory. It looks like you'll get at least 10^10 sequences (len(alpha)==10, N=10) for this problem. Make your problem smaller, or do it in a way where you don't need to have all the sequences in memory at once.

On Wednesday, February 24, 2016 at 6:18:09 PM UTC-8, Tim Schindler wrote:
Hello, I fell over a memory issue caused by some bad program. See the example here: http://play.golang.org/p/2Wo9t8u7E9 <http://play.golang.org/p/2Wo9t8u7E9>. My motivation was to write a sequence generator that gives me all possible combinations of sequences based including empty sets based on given parameters. So when I want to have all combinations for the character set `abc` and a sequence can be up to 3 characters long, I expect something like this.

```
a
aa
ab
ac
aaa
aab
aac
b
ba
bb
bc
bba
bbb
...
```

You get the picture. However, I can implement certain solutions but all of them break at some point with this.

```
fatal error: runtime: out of memory

runtime stack:
runtime.throw(0x51f120, 0x16)
/home/vagrant/.gvm/gos/go1.5/src/runtime/panic.go:527 +0x90
runtime.sysMap(0xc87bba0000, 0x1c040000, 0x59b800, 0x5b9438)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mem_linux.go:143 +0x9b
runtime.mHeap_SysAlloc(0x59b860, 0x1c040000, 0xc820066780)
/home/vagrant/.gvm/gos/go1.5/src/runtime/malloc.go:423 +0x160
runtime.mHeap_Grow(0x59b860, 0xe020, 0x0)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:628 +0x63
runtime.mHeap_AllocSpanLocked(0x59b860, 0xe01e, 0x100)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:532 +0x5f1
```

My idea was to make the implementation linear, because recursion will make the call stack grow. Unfortunately it still looks like the GC is not fast enough (bad guess). As in my playground example I also tried `runtime.GC`, but it did not help.

- Is the problem related to GC?
- How to achieve the task?
- What am I doing wrong?

Thanks for listening.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com For more options, visit https://groups.google.com/d/optout <https://groups.google.com/d/optout>.

On Feb 25, 2016, at 10:17 PM, Michael Jones wrote:

Tim,

I wrote a simple example for you.
http://play.golang.org/p/INL5gE8qFP <http://play.golang.org/p/INL5gE8qFP>

You can run it at the Go Playground. If you’ll copy this to your computer and change the symbol set size to 10 (comments), and take out the printing of each combination, you will get a result like this:

MichaelMacBook:combine mtj$ go install
MichaelMacBook:combine mtj$ time combine
total combinations = 11111111110

real 1m15.479s
user 1m15.452s
sys 0m0.064s

This is your set of ten symbols in all unordered combinations. The total sums the number of length 1, length 2, …, length 10 solutions. it is 11 billion solutions in 105 seconds on my MacBookPro notebook, so that’s about 100 million per second.

Michael

P.S. you can also change from unordered (“aab”, “aba”, and “baa" to the ordered solution style (“aab” only) if you look further down in the comments.

—
Michael Jones, CEO • michael@wearality.com • +1 650 656-6989
Wearality Corporation • 289 S. San Antonio Road • Los Altos, CA 94022

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com For more options, visit https://groups.google.com/d/optout <https://groups.google.com/d/optout>.

On Friday, February 26, 2016 at 5:01:19 AM UTC-3, Bakul Shah wrote:

I think Tim wants all combinations of length 1..n (order doesn’t matter),
not permutations, given n symbols.
Your program generates strings like aab, baa. May be something like the
following do the trick?

http://play.golang.org/p/QXFtWddeTO

For 10 symbols it should yield 184755 strings. This is sequence A030662
<https://oeis.org/A030662> on OEIS.

On Feb 25, 2016, at 10:17 PM, Michael Jones <m...@wearality.com
<javascript:>> wrote:

Tim,

I wrote a simple example for you.
http://play.golang.org/p/INL5gE8qFP

You can run it at the Go Playground. If you’ll copy this to your computer
and change the symbol set size to 10 (comments), and take out the printing
of each combination, you will get a result like this:

*MichaelMacBook:combine mtj$ go install*
*MichaelMacBook:combine mtj$ time combine*
*total combinations = 11111111110*

*real 1m15.479s*
*user 1m15.452s*
*sys 0m0.064s*

This is your set of ten symbols in all unordered combinations. The total
sums the number of length 1, length 2, …, length 10 solutions. it is 11
billion solutions in 105 seconds on my MacBookPro notebook, so that’s about
100 million per second.

Michael

P.S. you can also change from unordered (“aab”, “aba”, and “baa" to the
ordered solution style (“aab” only) if you look further down in the
comments.

—
Michael Jones, CEO • mic...@wearality.com <javascript:> • +1 650
656-6989
Wearality Corporation • 289 S. San Antonio Road • Los Altos, CA 94022

On Feb 25, 2016, at 8:08 PM, kei...@alum.mit.edu <javascript:> wrote:

On its last gasp the runtime is asking the OS for 448MB and the OS is
saying no. Sounds like you are allocating (and retaining) too much memory.
It looks like you'll get at least 10^10 sequences (len(alpha)==10, N=10)
for this problem. Make your problem smaller, or do it in a way where you
don't need to have all the sequences in memory at once.
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to golang-nuts...@googlegroups.com <javascript:>.
For more options, visit https://groups.google.com/d/optout.



--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an
email to golang-nuts...@googlegroups.com <javascript:>.
For more options, visit https://groups.google.com/d/optout.

On Feb 26, 2016, at 3:00 AM, Bakul Shah wrote:

I think Tim wants all combinations of length 1..n (order doesn’t matter), not permutations, given n symbols.
Your program generates strings like aab, baa. May be something like the following do the trick?

http://play.golang.org/p/QXFtWddeTO <http://play.golang.org/p/QXFtWddeTO>

For 10 symbols it should yield 184755 strings. This is sequence A030662 <https://oeis.org/A030662> on OEIS.

On Wednesday, February 24, 2016 at 11:18:09 PM UTC-3, Tim Schindler wrote:

Hello, I fell over a memory issue caused by some bad program. See the
example here: http://play.golang.org/p/2Wo9t8u7E9. My motivation was to
write a sequence generator that gives me all possible combinations of
sequences based including empty sets based on given parameters. So when I
want to have all combinations for the character set `abc` and a sequence
can be up to 3 characters long, I expect something like this.

```
a
aa
ab
ac
aaa
aab
aac
b
ba
bb
bc
bba
bbb
...
```

You get the picture. However, I can implement certain solutions but all of
them break at some point with this.

```
fatal error: runtime: out of memory

runtime stack:
runtime.throw(0x51f120, 0x16)
/home/vagrant/.gvm/gos/go1.5/src/runtime/panic.go:527 +0x90
runtime.sysMap(0xc87bba0000, 0x1c040000, 0x59b800, 0x5b9438)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mem_linux.go:143 +0x9b
runtime.mHeap_SysAlloc(0x59b860, 0x1c040000, 0xc820066780)
/home/vagrant/.gvm/gos/go1.5/src/runtime/malloc.go:423 +0x160
runtime.mHeap_Grow(0x59b860, 0xe020, 0x0)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:628 +0x63
runtime.mHeap_AllocSpanLocked(0x59b860, 0xe01e, 0x100)
/home/vagrant/.gvm/gos/go1.5/src/runtime/mheap.go:532 +0x5f1
```

My idea was to make the implementation linear, because recursion will make
the call stack grow. Unfortunately it still looks like the GC is not fast
enough (bad guess). As in my playground example I also tried `runtime.GC`,
but it did not help.

- Is the problem related to GC?
- How to achieve the task?
- What am I doing wrong?

Thanks for listening.