Does reducing capacity of a slice return memory?

[robfig]

I was curious if reducing the capacity of slice makes that memory available to be reclaimed?

(1) Reducing capacity using a three-index:

var s = make([]int64, 1e9)
... add data to s, keeping a count ..
s = s[:n:n] // reduce length and capacity to number of items read

(2) Reducing capacity by slicing off the front, as happens when using slice as a queue

var s []int64
s = append(s, 1, 2, 3, 4, 5)
s = s[5:]

Should I be careful to allocate a new slice and copy over, if I want to avoid that memory being pinned until the original slice goes out of scope?

Thank you,
Rob

[Ian Lance Taylor]

In the current implementations, reducing the capacity of the slice
does not cause the trailing memory to be released. Basically, it's
hard to be sure that there isn't any other slice somewhere that might
permit references to that trailing memory.

There has been some discussion of changing the garbage collector to
support this, but it's not simple.

Ian

[Andrey Tcherepanov]

> Basically, it's hard to be sure that there isn't any other slice somewhere that might permit references to that trailing memory

Ian, I am kind of curious about this case. I understand that "hard" is not "impossible", but still - if I copy the needed part to a smaller array, how does the GC knows that there are no more slices pointing to a part of an old allocation?

Andrey

[Ian Lance Taylor]

On Thu, Jul 18, 2019 at 8:35 AM Andrey Tcherepanov
<xnow4f...@sneakemail.com> wrote:
>
> > Basically, it's hard to be sure that there isn't any other slice somewhere that might permit references to that trailing memory
>
> Ian, I am kind of curious about this case. I understand that "hard" is not "impossible", but still - if I copy the needed part to a smaller array, how does the GC knows that there are no more slices pointing to a part of an old allocation?

I'm not sure precisely what you are asking. Conceptually, the GC
starts with global variables and goroutine stacks and traces all
pointers to find all reachable memory. Unreachable memory is
discarded.

What makes this case harder is that we need to not only track
pointers, we need to also look at the slice information to turn the
pointer to the backing array into a sort of bounded pointer: a pointer
to only part of the object, not all of it. That means that the GC has
to understand slice structures, which are more complex than pointers.
It means that the compiler has to build slice structures in a way that
the GC can understand, which it currently does not do. That may sound
simple, but currently the compiler splits up local slices into three
independent local variables, and that would either become impossible
or would require significantly more data to be recorded for the GC.

Another wrinkle is that the current memory allocator does not support
shrinking memory allocations at all, since that currently never
happens. The allocator is based on storing objects of the same size
together, so it's not easy to split an existing object into smaller
sizes. That said, very large objects do have to be handled
differently and it might be more feasible to shrink those objects; I'm
not sure.

So those are some of the reasons why it is hard.

Ian

[Andrey Tcherepanov]

Thank you Ian, you reply is very much appreciated.

... what if a compiler would do a bit of helping "magic"? I would suspect it does know that you return a subslice of an allocated array (something that compiler still sees up the call stack). Would it be possible to put a code for "This big alloc is going out of scope. If resulting (surviving) slice is less than a X% of that original thing, copy needed part, and point a new slice there".

Simple cases only - ints, strings, bytes. Struct of anything with pointers are no-go (pardon the pun) - they might point to another item in the same array.

For cases of huge allocs, running-close-to-mem-limits, X will have to be smaller, so you would not OOM right there. 

Unless I miss something big and obvious - which is very highly possible - that sounds like a possible way to drop wasted space, keeping small part required on a side. 

Again, thank you very much for the answer.

Andrey

[Michel Levieux]

Hello everyone,

I might be saying something stupid but I found this topic really interesting and I was wondering:

Instead of trying to get the notion of "slice" to replace that of "pointer" in the compiler/runtime reference frame, wouldn't it be possible / less complex to keep track of the largest subslice of a slice that is currently used? Again this is not applicable for slices of elements of complex type. But at least with native basic Go types, it would become possible to say:

I have a slice S that is shared by N goroutines / different parts of the program, the largest subslice of S referenced right now is T, and T is less than X% of the length of S, so we can retrieve the remaining memory to the OS.

Michel,

--
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/6160bc33-1ec0-4c17-ae50-e817e822fd3a%40googlegroups.com.

[Ian Lance Taylor]

I'm not sure what to say. If someone wants to write up and work on a
detailed implementation proposal, that is fine. Go for it. As I said
earlier, I think it would be hard. I'll add that I don't think that
the difficulty would pay off in terms of the amount of real code that
it would help. There is a lot of other hard work that could be done
in the compiler that would, I think, help many more programs.

Ian

[Michael Jones]

There is a difference in the meanings of terms in this discussion, maybe that’s confusing to some. (That is, Ian went right to the heart of the matter but maybe a simpler fact needs to be made plain to others.)

When you think of the memory used by a slice and of maybe using less of it and “returning” the rest, like putting uneaten food away for tomorrow, you’re making several big demands. 

You demand severabity, that half a TV set is a reasonable thing to discuss, like half a pie. In fact that backing array was created by the allocator as “256 bytes you can use, with other info you don’t know about somewhere.” To chop off half and “give it back” is not part of the contract. The contract is: use it until you’re done with it. (The whole TV, because of wires and glass bits).

One alternative is to make 256 allocations of the small parts, then allocate an array as pointers to each little part. Then you can reshape the array and free the extra parts. This freedom pays a tax in many ways, and always pays it in the normal case. 

But in the efficient single group allocation style (Go, C, C++, ...) the desire to return part of a monolithic allocation is a major burden. Ian went right to the elements of that burden. But since the follow ups still wanted the burden I thought maybe a reminder of why it is hard would help. 

--
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/CAOyqgcVvDz1kRzpoKNtw5MDH%2BrFpsW6fLSqrT%3DS83JGhM_Y-%2BA%40mail.gmail.com.

--

Michael T. Jones
michae...@gmail.com

[Andrey Tcherepanov]

My suggestion was not to make "the kitchen" work harder by marking parts of the hamburger to be good for the consumption, no. My suggestion was to recycle bitten hamburger out and put just the bitten piece aside in a doggy bag, sorry.

A.

On Friday, July 19, 2019 at 1:08:51 PM UTC-6, Michael Jones wrote:

There is a difference in the meanings of terms in this discussion, maybe that’s confusing to some. (That is, Ian went right to the heart of the matter but maybe a simpler fact needs to be made plain to others.)

When you think of the memory used by a slice and of maybe using less of it and “returning” the rest, like putting uneaten food away for tomorrow, you’re making several big demands. 

You demand severabity, that half a TV set is a reasonable thing to discuss, like half a pie. In fact that backing array was created by the allocator as “256 bytes you can use, with other info you don’t know about somewhere.” To chop off half and “give it back” is not part of the contract. The contract is: use it until you’re done with it. (The whole TV, because of wires and glass bits).

One alternative is to make 256 allocations of the small parts, then allocate an array as pointers to each little part. Then you can reshape the array and free the extra parts. This freedom pays a tax in many ways, and always pays it in the normal case. 

But in the efficient single group allocation style (Go, C, C++, ...) the desire to return part of a monolithic allocation is a major burden. Ian went right to the elements of that burden. But since the follow ups still wanted the burden I thought maybe a reminder of why it is hard would help. 

On Fri, Jul 19, 2019 at 7:36 AM Ian Lance Taylor <ia...@golang.org> wrote:

I'm not sure what to say.  If someone wants to write up and work on a
detailed implementation proposal, that is fine.  Go for it.  As I said
earlier, I think it would be hard.  I'll add that I don't think that
the difficulty would pay off in terms of the amount of real code that
it would help.  There is a lot of other hard work that could be done
in the compiler that would, I think, help many more programs.

Ian

--
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 golan...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAOyqgcVvDz1kRzpoKNtw5MDH%2BrFpsW6fLSqrT%3DS83JGhM_Y-%2BA%40mail.gmail.com.

[Michael Jones]

Yes! That always works at the application level. Write an “inspector” that examines things, duplicating and copying the live parts. 

I do that in several of my long running math apps, where my pool of big.Ints end up with 50-100 thousand digit allocations in a big because of one giant multiply...I examine them as I recycle and manage this. Makes a big difference. 

But doing it when you know the situation is easy. It’s having the compiler “just know” that is so challenging. (Unless you box everything like Java...and that’s an expensive path)

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/d371646c-1f7c-4df1-8077-14e40c25ae04%40googlegroups.com.

[Andrey Tcherepanov]

I understand that it is very easy on application level... if programmer even thought about it. But my assumption is that compiler has some sort of liveness analysis, and it could be utilized here just to help with disposal of a bitten part.

Andrey

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/d371646c-1f7c-4df1-8077-14e40c25ae04%40googlegroups.com.

[Ian Lance Taylor]

On Fri, Jul 19, 2019 at 5:17 PM Andrey Tcherepanov
<xnow4f...@sneakemail.com> wrote:
>
> I understand that it is very easy on application level... if programmer even thought about it. But my assumption is that compiler has some sort of liveness analysis, and it could be utilized here just to help with disposal of a bitten part.

The kind of liveness analysis done by the compiler is only helpful in
extremely limited circumstances: when the compiler can track the slice
from creation to destruction and when the slice never escapes in any
way. I'm skeptical that such a case happens often enough to be worth
implementing.

(And even if we did implement it we would still have the
above-mentioned problem that the allocator doesn't support discarding
part of an allocation.)

Ian

[Andrey Tcherepanov]

Thanks Ian, 

But just to be clear - I do not want to discard _a part_. I want to discard a _whole big one_, copying a small needed part that is still "alive" aside. Allocator perform it's duties as usual -  allocate a new small array, and discard an old one. It is just that compiler invokes this code on defer it if knows that there is only one reference to the remaining part, and that part is "small"

A.

[Robert Engels]

You are beginning to touch on why modern compacting collectors are beneficial in a large class of applications. Not all application profiles benefit from this and it comes at a cost, but it is far simpler than rolling your own. 

--

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/b69f101c-0705-466c-96d3-7f1ef0adea74%40googlegroups.com.

[Wojciech S. Czarnecki]

On Fri, 19 Jul 2019 18:47:36 -0700 (PDT)
Andrey Tcherepanov <xnow4f...@sneakemail.com> wrote:

> knows that there is only one reference to the remaining part,
> and that part is "small"

This "is it small"? is a check that would be performed for all, while
only tiny percent would benefit off it.

>>> I understand that it is very easy on application level...

And thats why it belongs there, IMO :)

>>> if programmer even thought about it.

She certainly should, because only she does know meaning of
"big" and "small" in context.

> A.

Hope this helps,

--
Wojciech S. Czarnecki
<< ^oo^ >> OHIR-RIPE