slices and GC

[Thomas Bushnell, BSG]

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

[Kamil Kisiel]

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.

[Thomas Bushnell, BSG]

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

[Patrick Mylund Nielsen]

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.

[roger peppe]

On 8 August 2012 07:37, Thomas Bushnell, BSG <tbus...@google.com> 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.

[Russ Cox]

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

Your source is mistaken. It does not.

Russ

[⚛]

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.

[Erwin]

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? 

[Rob Pike]

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

[⚛]

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.

[Dave Cheney]

> - 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

[⚛]

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.

[Dave Cheney]

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