I think I found a bug?

[John Olson]

I have a recursive function that seems to be reusing memory it shouldn't. I'm developing in Goland 2021.1.1 with go version 1.16.2.

I've written a function to generate the partitions of an integer. The partitions of n are all the sets of integers that add up to n, so the partitions of 3 are {3}, {2,1} and {1,1,1}. As n grows, the number of partitions grows exponentially (to be precise, as e^(n^½)). I wrote a recursive function, which works great up to n=7. At n=8, one of the partitions is {2,2,2,1}, which is obviously wrong; and since the function is recursive, every subsequent n is wrong, too.

I just spent quite a long time stepping through the code, and I found that what seems to be happening is that a slice declared in my recursive function is being reused in two different recursions. Specifically, my function declares

var temp [][]int

to build up the list of partitions. When I compute Partitions(8), I have to compute Partitions(4), 5, 6 and 7. I memoize each set of partitions so I only have to compute them once.

It all goes wrong when I'm working on Partitions(7). At this point, Partitions(8) has already added 6 cases, the last of which is {2,2,2,2}. This is stored in temp[5], the temp corresponding to n=8, of course. Then I compute Partitions(7), which should create a new temp [][]int; I'll call this temp//7. temp[6]//7 gets {2,2,2,1}, and at that point temp[5]//8 changes from {2,2,2,2} to {2,2,2,1}. The addresses of temp[6]//7 and temp[5]//8 are different, but the addresses of the elements of these slices are the same.

This has to be wrong.

I suspect a bug in go, but I suppose it's possible there's a bug in goland. I'm running on macOS 11.3.1, just in case that's relevant.

I'm happy to share the source code if anyone is interested.

Thanks,

J

[Martin Schnabel]

Could you send a https://play.golang.org/ link showing a short example?

Without much information it sounds like a you update the same slice at
two different indices. It would be interesting to know how you populate
the temp slice.

> /elements/ of these slices are the same.

>
> This has to be wrong.
>
> I suspect a bug in go, but I suppose it's possible there's a bug in
> goland. I'm running on macOS 11.3.1, just in case that's relevant.
>
> I'm happy to share the source code if anyone is interested.
>
> Thanks,
>
> J
>

> --
> 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
> <mailto:golang-nuts...@googlegroups.com>.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/fb9031ba-bfa0-4c92-9cb7-6ad3a8781184n%40googlegroups.com
> <https://groups.google.com/d/msgid/golang-nuts/fb9031ba-bfa0-4c92-9cb7-6ad3a8781184n%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Kurtis Rader]

It's more likely you've misunderstood how slices work. From https://golang.org/ref/spec#Slice_types:

> A slice is a descriptor for a contiguous segment of an underlying array and provides access to a numbered sequence of elements from that array.

If you still believe you've found a bug we'll need the smallest reproducer you can provide.

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/fb9031ba-bfa0-4c92-9cb7-6ad3a8781184n%40googlegroups.com.

--

Kurtis Rader

Caretaker of the exceptional canines Junior and Hank

[Robert Engels]

A slice is not an array. Words to live by. 

On May 26, 2021, at 7:37 PM, Kurtis Rader <kra...@skepticism.us> wrote:



To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD-vkk_aOtNk%3D4woXcwDRy8_-pyeRu9NnRKF9beuOFSYTw%40mail.gmail.com.

[John Olson]

Here’s the code. It might be possible to come up with a shorter reproducer, but I’m not sure where to start. The recursion takes place in line 21. The code works for 7 or smaller, and fails for 8 and larger.

J

[Jamil Djadala]

minimally changed code that works:

https://play.golang.org/p/Tcfw_EC8jMp

[John Olson]

Thank you!

So it seems I misunderstood what append() does. I expected that all of the slices I had created with append() would have just enough capacity, such that every use of append() would allocate new memory and copy. It surprises me that my code worked as well as it did.

J 

You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/MPQWVYruhlU/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/de91d8a7-63eb-40aa-bf20-b1a18897fa84n%40googlegroups.com.