Garbage collector not releasing memory in recursive function?

[Jack Valmadre]

I'm writing a simple recursive function which operates on a list, splitting it in two and recursing on each half in turn, then combining the results. The function returns a large object (~500MB).

Holding the result from the left branch in memory while I recurse down the right branch requires O(log n) memory. I can't afford this, so I save the left result to disk (and have any variables referencing it fall out of scope) before recursing down the right branch. However, my memory requirement still seems to grow according to O(log n). I've identified a simple program below which replicates this behaviour.

package main

func main() {

    size := 256 << 20

    n := 65536

    f(n, size)

}

func f(n, size int) []byte {

    switch {

    case n < 1:

        return nil

    case n == 1:

        return make([]byte, size)

    default:

        m := n / 2

        f(m, size)

        right := f(n-m, size)

        return right

    }

}

Note that in this toy example, I simply discard the result from the left branch rather than save to disk.

I've tried adding runtime.GC() calls after each recursive call to f(), but it only reduces the memory footprint by a constant factor (about half). The program ends up using roughly 4GB of memory (256MB * log2(65536)).

Have I made an error in logic? Is this an issue with how things get garbage collected?

Thanks.

[Dave Cheney]

Can you please provide some details. 

Go version ?

Operating system

You mention that your process grows to 4G, so it's unlikely that you are using 386. Can you please run your program with gc tracing in, GOGCTRACE=1.

--
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.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Dmitry Vyukov]

Yes, this is an issue with GC.
When GC will be fully precise, which includes liveness information for
stack vars, then it will work as expected.

Now you can do this dirty workaround:
http://play.golang.org/p/vnAFr6d_V_
The clear function zeroizes any possible pointers on stack.
Note that it may be fragile and require tuning for particular code.

[Jack Valmadre]

Thanks Dmitry! That seems to have fixed it for now, or at least improved it a lot. Is the return type of clear() significant? Does the number 64 depend on my program?

Dave, I have go version go1.1 linux/amd64. Fedora 15. I've attached the output with GOGCTRACE=1 for the original program, except I set n := 1024.

[Dmitry Vyukov]

Unfortunately, yes. It needs to "match" return type of f(), in the
sense that return value from clear() needs to contain nil's in all
positions where return value from f() contains pointer. Probably you
better return struct { foo [16]*byte } will all nil's.

> Does the number 64 depend
> on my program?

Unfortunately, yes. It needs to "cover" at least frame of one call to f().

That's why I said it is fragile.

> Dave, I have go version go1.1 linux/amd64. Fedora 15. I've attached the
> output with GOGCTRACE=1 for the original program, except I set n := 1024.
>

[Jack Valmadre]

I ended up using a workaround with different properties. It removes the need to guess at the stack frame size but the syntax is not so nice and it might not be possible if you need to call functions that you didn't write. There might be other disadvantages that I haven't foreseen. Here's the modified example.

package main

func main() {

    size := 256 << 20

    n := 65536

    var x []byte

    f(n, size, &x)

}

func f(n, size int, result *[]byte) {

    switch {

    case n < 1:

        return

    case n == 1:

        *result = make([]byte, size)

    default:

        m := n / 2

        var left []byte

        f(m, size, &left)

        left = nil

        f(n-m, size, result)

    }

}

This way, the pointer within the returned slice header from the right branch is not present in the top stack frame at return. I could also have

var right []byte

f(n-m, size, &right)

*result = right

right = nil

Note that I'm not re-using the same storage, only using a pointer to pass back the slice header instead of a return value.

Thanks again, Dmitry.

[Jack Valmadre]

Quick question: Does this mean that Go's garbage collector doesn't know where the end of the stack is?

[Ian Lance Taylor]

On Mon, Jun 24, 2013 at 5:11 PM, Jack Valmadre <jack.v...@gmail.com> wrote:
>
>
> On Tuesday, June 25, 2013 12:34:26 AM UTC+10, Dmitry Vyukov wrote:
>>
>> On Mon, Jun 24, 2013 at 6:21 PM, Jack Valmadre <jack.v...@gmail.com>
>> wrote:
>> >
>> > Does the number 64 depend
>> > on my program?
>>
>> Unfortunately, yes. It needs to "cover" at least frame of one call to
>> f().
>
>
> Quick question: Does this mean that Go's garbage collector doesn't know
> where the end of the stack is?

No. I'm not sure what leads you to think that it doesn't know, so I'm
not sure what to say to reassure you. This new function call is not
the GC.

Ian

[Jack Valmadre]

Sorry.

I thought that the purpose of Dmitry's clear() function was to zero out the stack past the current frame, so that there would be no lingering bits which point at the slice's array. Is that much correct?

[Ian Lance Taylor]

On Mon, Jun 24, 2013 at 5:40 PM, Jack Valmadre <jack.v...@gmail.com> wrote:
>
> I thought that the purpose of Dmitry's clear() function was to zero out the
> stack past the current frame, so that there would be no lingering bits which
> point at the slice's array. Is that much correct?

I see. You're right, but the issue arises when the function is
called, because Go doesn't by default zero out the frame when it
enters a function. That is, preclearing the stack avoids confusion
after entering the function.

Ian

[David DENG]

So this should be considered as a bug of the compiler? It's not easy to be found.

David

[Jack Valmadre]

Thanks, Ian. I was making the assumption that all variables on the stack would be initialized to zero, but I guess that's not necessarily true under the hood.

For anyone who's interested, I have another workaround, replacing

f(m, size)

return f(n-m, size)

with

f(m, size)

right := f(n-m, size)

defer func() { right = nil }()

return right

so that I have a named slice header which I can zero out after returning.

[Ian Lance Taylor]

On Mon, Jun 24, 2013 at 6:22 PM, David DENG <david...@gmail.com> wrote:
> So this should be considered as a bug of the compiler? It's not easy to be
> found.

As people have said upthread, the bug is that the GC is not precise.
People are actively working on that.

Because the GC is not precise, the contents of the stack are treated
as pointers even when they are not live. That causes the GC to retain
memory blocks that it should not.

Ian

> On Tuesday, June 25, 2013 9:02:15 AM UTC+8, Ian Lance Taylor wrote:
>>
>> On Mon, Jun 24, 2013 at 5:40 PM, Jack Valmadre <jack.v...@gmail.com>
>> wrote:
>> >
>> > I thought that the purpose of Dmitry's clear() function was to zero out
>> > the
>> > stack past the current frame, so that there would be no lingering bits
>> > which
>> > point at the slice's array. Is that much correct?
>>
>> I see. You're right, but the issue arises when the function is
>> called, because Go doesn't by default zero out the frame when it
>> enters a function. That is, preclearing the stack avoids confusion
>> after entering the function.
>>
>> Ian
>

[David DENG]

You are right, but before we can do the precise GC, the compiler can fill some zeros for pointer type return values.

David

[Ian Lance Taylor]

On Mon, Jun 24, 2013 at 9:05 PM, David DENG <david...@gmail.com> wrote:
> You are right, but before we can do the precise GC, the compiler can fill
> some zeros for pointer type return values.

We will have precise GC sooner rather than later.

[Dmitry Vyukov]

This solution is better than mine.