Slice "shrinking"

[Jan Mercl]

A recent question[1] at SO makes me wonder how is this currently
handled by gc and gccgo - an unconditional copy or a realloc if new
size < old size? It might make for a performance / memory utilisation
difference, it seems to me.

Thanks in advance for any available enlightenment about this.

-j

[1]: http://stackoverflow.com/questions/16748330/does-go-have-no-real-way-to-shrink-a-slice-is-that-an-issue

[Rémy Oudompheng]

On 2013/5/25 Jan Mercl <0xj...@gmail.com> wrote:
> A recent question[1] at SO makes me wonder how is this currently
> handled by gc and gccgo - an unconditional copy or a realloc if new
> size < old size? It might make for a performance / memory utilisation
> difference, it seems to me.
>
> Thanks in advance for any available enlightenment about this.

What is "this" referring to in your question? The stack overflow link
doesn't make it clear.

Rémy.

>
> [1]: http://stackoverflow.com/questions/16748330/does-go-have-no-real-way-to-shrink-a-slice-is-that-an-issue

[Jan Mercl]

On Sat, May 25, 2013 at 12:54 PM, Rémy Oudompheng
<remyoud...@gmail.com> wrote:
> What is "this" referring to in your question? The stack overflow link
> doesn't make it clear.

This is: Is 'a = append([]T, a[:x]...)' a guaranteed copy or can it
use realloc(3) for x << len(a)?

Thinking about it more I (only) now realize why it is not possible to
ever user realloc in this scenario. The compiler cannot decide if
there are or there are not any other pointers to the backing array.

Sorry for the noise, I falsely thought for a moment that this could be
an optimization possible to be considered by the compiler developers,
but I was wrong.

-j

[Kevin Gillette]

On Saturday, May 25, 2013 5:11:06 AM UTC-6, Jan Mercl wrote:

Thinking about it more I (only) now realize why it is not possible to 
ever user realloc in this scenario. The compiler cannot decide if 
there are or there are not any other pointers to the backing array. 

That is actually determinable (at least for certain reasonable cases) with escape analysis, likely the same kind of escape analysis being done today. For many cases, however, it's not necessarily useful: the gc runtime (and I'd imagine the gccgo runtime too) uses a size-based arena allocator, in which any requested allocation will occupy a slot in the smallest size-class that will contain it. For example, make([]byte, 9) would be given an 16-byte reservation, and new([32769]byte) would typically reserve nine 4096-byte pages. Because of arena allocation, if that 9-byte slice were shrunk in-place to 8 bytes, there would still be nothing to occupy the second half, since any 8-byte allocation would be allocated in the 8-byte arena. Shrinking in-place allocations that span multiple pages would be useful in cases mentioned in the SO question, but only if the shrunken data wouldn't fit in a smaller size class.

I think that this kind of potential auto-optimization (shrink-in-place for large allocations) would primarily benefit just the kind of programs written without particular attention to allocations or memory use. Optimizations that could benefit just about everybody, however, include: making append transitively aware of wasted space in an arena slot, so that `append(make([]byte, 15), 0)` wouldn't require a memcpy, and making appends to large allocations look for right-adjacent free pages when reallocating, again avoiding memcpy of the source data and the creation of an additional orphaned object. Of course, both of these optimizations would need to be limited to cases in which the compiler could prove that there is no concurrent access to the backing array at the time of append, and that all pre-append references to the backing array are dead prior to any post-append access, otherwise expected semantics (that the result of the append would be a distinct copy) would be violated.