Discussion of the Go Programming Language ()

Thomas Bushnell, BSG | 8 Aug 2012 06:11

slices and GC

http://research.swtch.com/godata contains the observation that Go slices contain a reference to the whole original array, so that "the reference to the original keeps the entire original string in memory even though only a small amount is still needed."

I understand that this means that:

func foo() ([]int) {

x := [1000000]int

return x[999999:]

}

keeps the whole million integer array live as long as the return value is live, even though only one element is actually still reachable.

Finding reachability is what GC is for.

Is there any thought to changing the GC algorithm to deal with this case? It would not require the allocate-and-copy version of slicing; simply the GC would need to keep track of internal pointers to sliced arrays, and release the front portion of arrays when it can no longer be reached by live slices.

Thomas

headers

Kamil Kisiel | 8 Aug 2012 08:07

Re: slices and GC

Have a read of http://golang.org/doc/articles/slices_usage_and_internals.html

Basically you can work around this by writing your function to be:

func foo() ([]int) {

x := make([]int, 1000000)

var y []int

return append(y, x[999999:]...)

}

append and (or you could use copy) will copy the data from a slice in to a new array of the appropriate size. After the function foo() returns nothing will reference the original array x any longer so it will be garbage collected. You'll end up with a new array of len() and cap() 1 in this case.

On Tuesday, August 7, 2012 9:11:01 PM UTC-7, Thomas Bushnell, BSG wrote:

http://research.swtch.com/godata contains the observation that Go slices contain a reference to the whole original array, so that "the reference to the original keeps the entire original string in memory even though only a small amount is still needed."

I understand that this means that:

func foo() ([]int) {

x := [1000000]int

return x[999999:]

}

keeps the whole million integer array live as long as the return value is live, even though only one element is actually still reachable.

Finding reachability is what GC is for.

Is there any thought to changing the GC algorithm to deal with this case? It would not require the allocate-and-copy version of slicing; simply the GC would need to keep track of internal pointers to sliced arrays, and release the front portion of arrays when it can no longer be reached by live slices.

Thomas

headers

Thomas Bushnell, BSG | 8 Aug 2012 08:37

Re: Re: slices and GC

But then you pay the penalty for the copy. I've been told offline that the GC does do what I'm suggesting; if that's correct then perhaps the essay needs revised...

Thomas

On Aug 7, 2012 11:07 PM, "Kamil Kisiel" <kamil.kisiel-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:

Have a read of http://golang.org/doc/articles/slices_usage_and_internals.html

Basically you can work around this by writing your function to be:

func foo() ([]int) {

x := make([]int, 1000000)

var y []int

return append(y, x[999999:]...)

}

append and (or you could use copy) will copy the data from a slice in to a new array of the appropriate size. After the function foo() returns nothing will reference the original array x any longer so it will be garbage collected. You'll end up with a new array of len() and cap() 1 in this case.

On Tuesday, August 7, 2012 9:11:01 PM UTC-7, Thomas Bushnell, BSG wrote:
http://research.swtch.com/godata contains the observation that Go slices contain a reference to the whole original array, so that "the reference to the original keeps the entire original string in memory even though only a small amount is still needed."

I understand that this means that:

func foo() ([]int) {

x := [1000000]int

return x[999999:]

}

keeps the whole million integer array live as long as the return value is live, even though only one element is actually still reachable.

Finding reachability is what GC is for.

Is there any thought to changing the GC algorithm to deal with this case? It would not require the allocate-and-copy version of slicing; simply the GC would need to keep track of internal pointers to sliced arrays, and release the front portion of arrays when it can no longer be reached by live slices.

Thomas

headers

Patrick Mylund Nielsen | 8 Aug 2012 09:22

Re: Re: slices and GC

I might be thinking of Russ' post, but I could swear I read the exact same thing somewhere in the Go docs. Definitely should be revised if it's the case -- doesn't seem like such an uncommon issue.

On Wed, Aug 8, 2012 at 8:37 AM, Thomas Bushnell, BSG <tbushnell <at> google.com> wrote:

But then you pay the penalty for the copy. I've been told offline that the GC does do what I'm suggesting; if that's correct then perhaps the essay needs revised...

Thomas

On Aug 7, 2012 11:07 PM, "Kamil Kisiel" <kamil.kisiel-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
Have a read of http://golang.org/doc/articles/slices_usage_and_internals.html

Basically you can work around this by writing your function to be:

func foo() ([]int) {

x := make([]int, 1000000)

var y []int

return append(y, x[999999:]...)

}

append and (or you could use copy) will copy the data from a slice in to a new array of the appropriate size. After the function foo() returns nothing will reference the original array x any longer so it will be garbage collected. You'll end up with a new array of len() and cap() 1 in this case.

On Tuesday, August 7, 2012 9:11:01 PM UTC-7, Thomas Bushnell, BSG wrote:
http://research.swtch.com/godata contains the observation that Go slices contain a reference to the whole original array, so that "the reference to the original keeps the entire original string in memory even though only a small amount is still needed."

I understand that this means that:

func foo() ([]int) {

x := [1000000]int

return x[999999:]

}

keeps the whole million integer array live as long as the return value is live, even though only one element is actually still reachable.

Finding reachability is what GC is for.

Is there any thought to changing the GC algorithm to deal with this case? It would not require the allocate-and-copy version of slicing; simply the GC would need to keep track of internal pointers to sliced arrays, and release the front portion of arrays when it can no longer be reached by live slices.

Thomas

headers

roger peppe | 8 Aug 2012 09:27

Re: Re: slices and GC

On 8 August 2012 07:37, Thomas Bushnell, BSG <tbushnell@...> wrote:
>  I've been told offline that the GC does do what I'm suggesting

I'd be quite surprised if it does, though it would be nice.

There's another variant that's perhaps harder:

func foo() *int {
    x := make([]int, 100000)
    return &x[0]
}

But perhaps when the GC becomes more precise this could
be done too.

headers

Russ Cox | 10 Aug 2012 02:03

Re: Re: slices and GC

On Wed, Aug 8, 2012 at 2:37 AM, Thomas Bushnell, BSG
<tbushnell@...> wrote:
> I've been told offline that the GC does do what I'm suggesting

Your source is mistaken. It does not.

Russ

headers

⚛ | 14 Aug 2012 17:29

Re: slices and GC

On Wednesday, August 8, 2012 6:11:01 AM UTC+2, Thomas Bushnell, BSG wrote:

Is there any thought to changing the GC algorithm to deal with this case? It would not require the allocate-and-copy version of slicing; simply the GC would need to keep track of internal pointers to sliced arrays, and release the front portion of arrays when it can no longer be reached by live slices.

In current implementation, it is impossible to release the front portion of an array because the memory allocator is unable to handle such a case. An allocated memory region needs to be deallocated as a whole.

headers

Erwin | 14 Aug 2012 17:55

Re: Re: slices and GC

Somehow related to this, I wonder why a slice doesn't store the start address of the underlying array. Wouldn't doing so make some things easier and faster? Less work for the garbage collector I suppose, to figure out which slices use which memory regions? Also, one could possibly copy to the front the contents of a re-sliced slice that is appended to, without re-allocation, if there is enough unused space in the underlying array?

Or will storing that additional pointer make the slice too heavy for the most common scenarios?

headers

Rob Pike | 14 Aug 2012 18:32

Re: Re: slices and GC

Storing the start address would be a fine implementation, but it would
require that the slice header be larger to store the other pointer or
that another arithmetic operation be involved in each index
calculation.

-rob

headers

⚛ | 14 Aug 2012 22:14

Re: Re: slices and GC

On Tuesday, August 14, 2012 5:55:27 PM UTC+2, notnot wrote:

Also, one could possibly copy to the front the contents of a re-sliced slice that is appended to, without re-allocation, if there is enough unused space in the underlying array?

- Anything involving shrinking or expanding the size of an allocated memory region is incompatible with Go's current memory allocator. Because changing the size isn't allowed, it implies that copying or moving data within the same region (without full re-allocation) would have a strictly negative impact on performance.

- The run-time cannot move memory from one location to another because it does not have enough information about what is going on outside of Go. Go interacts via memory with the OS and with C. Passing []byte to os.Read sends a memory address to the OS and the run-time does not know what the OS will do with the memory region nor when the OS will stop using the memory region. If there exists a []T, and it has been passed to OS or C, the memory cannot be moved to a different address until it is garbage collected. Also, any pointer reachable from a pointer passed to OS or C is also unmovable. The run-time is not tracking the pointers passed to OS or C.

Or will storing that additional pointer make the slice too heavy for the most common scenarios?

headers

Dave Cheney | 15 Aug 2012 03:16

Re: Re: slices and GC

> - Anything involving shrinking or expanding the size of an allocated memory
> region is incompatible with Go's current memory allocator. Because changing
> the size isn't allowed, it implies that copying or moving data within the
> same region (without full re-allocation) would have a strictly negative
> impact on performance.

Hello,

Why is this so? As I understand it, there are two types of allocation,
ones taken from the SLAB like allocator for small objects (less than a
page), obviously these can't be resliced as they would be a different
size from their siblings, but as they are small (relative to other
slices) the waste is minimal.

However I was lead to believe that for large (multi page allocations),
slices are allocated directly to the heap. In that case, is it not
possible to free the front portion of the slice if the unreferenced
region is measured in pages ?

Cheers

Dave

headers

⚛ | 15 Aug 2012 17:55

Re: Re: slices and GC

On Wednesday, August 15, 2012 3:16:34 AM UTC+2, Dave Cheney wrote:

> - Anything involving shrinking or expanding the size of an allocated memory
> region is incompatible with Go's current memory allocator. Because changing
> the size isn't allowed, it implies that copying or moving data within the
> same region (without full re-allocation) would have a strictly negative
> impact on performance.

Hello,

Why is this so? As I understand it, there are two types of allocation,
ones taken from the SLAB like allocator for small objects (less than a
page), obviously these can't be resliced as they would be a different
size from their siblings, but as they are small (relative to other
slices) the waste is minimal.

However I was lead to believe that for large (multi page allocations),
slices are allocated directly to the heap. In that case, is it not
possible to free the front portion of the slice if the unreferenced
region is measured in pages ?

That is right. But the maximum size of a "small" object is 32 KB and this maximum size is fairly large (in my opinion). The probability of allocating a slice which is larger than 32 KB, and using the slice in the specific way we are discussing here, seems small. I would need to see an actual Go application where freeing the front part of large slices would lead to lower memory consumption of the Linux process.

headers

Dave Cheney | 16 Aug 2012 03:35

Re: Re: slices and GC

Right. I did not realise the minimum allocation was that large. It is
unlikely this would ever occur frequently enough naturally to return a
measurable benefit.

Cheers

Dave

On Thu, Aug 16, 2012 at 1:55 AM, ⚛ <0xe2.0x9a.0x9b@...> wrote:
> On Wednesday, August 15, 2012 3:16:34 AM UTC+2, Dave Cheney wrote:
>>
>> > - Anything involving shrinking or expanding the size of an allocated
>> > memory
>> > region is incompatible with Go's current memory allocator. Because
>> > changing
>> > the size isn't allowed, it implies that copying or moving data within
>> > the
>> > same region (without full re-allocation) would have a strictly negative
>> > impact on performance.
>>
>> Hello,
>>
>> Why is this so? As I understand it, there are two types of allocation,
>> ones taken from the SLAB like allocator for small objects (less than a
>> page), obviously these can't be resliced as they would be a different
>> size from their siblings, but as they are small (relative to other
>> slices) the waste is minimal.
>>
>> However I was lead to believe that for large (multi page allocations),
>> slices are allocated directly to the heap. In that case, is it not
>> possible to free the front portion of the slice if the unreferenced
>> region is measured in pages ?
>
>
> That is right. But the maximum size of a "small" object is 32 KB and this
> maximum size is fairly large (in my opinion). The probability of allocating
> a slice which is larger than 32 KB, and using the slice in the specific way
> we are discussing here, seems small. I would need to see an actual Go
> application where freeing the front part of large slices would lead to lower
> memory consumption of the Linux process.