slices: have Delete and others clear the tail

Proposal

a = slices.Delete(a, i, j) should zero the (j - i) elements after the length of the returned slice

TL;DR zeroing the elements is error-prone, it should be taken care of by the stdlib function.

Chronology

2012 Go 1.0 released. It doesn’t have generics.

2022 Go 1.18 released. It has generics.

2022 The golang.org/x/exp/slices package has Delete.

2023 Delete is promoted to the new stdlib package slices.

Current implementation

slices.Delete achieves its job in-place by

shifting M=len(a)-j tail elements to the left, by copy
returning a slice of the original slice, having smaller or equal length

See its source.

Problem: memory

If the elements have a reference type (pointer, map, slice, chan, string), or contain fields having a reference type, then (j-i) elements at the end of the original slice are left untouched and keep referencing some objects. They will not be garbage collected, and they may enjoy a lifetime far exceeding the intent of the developer.

This is a memory leak.

Impact

Slices containing only value types are not impacted. Their memory footprint is the same, regardless of any zeroing.

Some programs will have a memory leak without noticing and without serious consequences, when the objects are few and small.

Some programs will have serious memory leaks, and find it difficult to properly diagnose. The consequences are crashes (OOM), increased GC pressure, overall bad performance, higher costs associated with more memory utilization and more server instances, and higher costs associated with debugging and fixing the leak.

Indirect impact

Some developers do want to address this and write zero values themselves (see documentation recommendation below). But they risk writing incorrect code, turning a mild performance concern into a serious correctness problem.

Partial solution: documentation

The documentation of slices.Delete explicitly states:

Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those elements contain pointers you might consider zeroing those elements so that objects they reference can be garbage collected.

Problem: zeroing is difficult

In order to properly prevent a memory leak, the burden is on the developer to:

figure out that there is a risk (memory leak) that requires action on their part,
determine if they should do some zeroing before calling Delete, or after calling Delete,
properly compute the indices of the elements to be zeroed,
figure out how to properly access the elements beyond the length of the returned slice.

This is error-prone.

When dealing with pointer zeroing, the Delete API is both hard to use and easy to misuse.

Cognitive burden

Incorrect code may be written in good faith in a context where several non-trivial concepts must be properly understood by the developers.

correct utilization: the developers need to understand what a slice is and how slice headers work, in order to understand the API design “pass a slice as argument, get a slice as return value”
- this is similar to the API of append
developers are implicitly expecting the stdlib to “do the right thing” (principle of least astonishment)
- the perceived “right thing” is not universal: some want performance by default, some want correctness and safety by default
  - objects not being GCed (memory leak) feels like a correctness/safety issue, but the consequences are mostly a performance issue.
even for skilled developers, the list of conditions (listed in previous section) to properly address the problem will too often not be fully met
the need for such manual workarounds partially defeats the purpose of having a stdlib function.

Suggested implementation

// Delete removes the elements s[i:j] from s, returning the modified slice.
// Delete panics if s[i:j] is not a valid slice of s.
// Delete is O(len(s)-i), so if many items must be deleted, it is better to
// make a single call deleting them all together than to delete one at a time.
func Delete[S ~[]E, E any](s S, i, j int) S {
    _ = s[i:j] // bounds check

    s = append(s[:i], s[j:]...)
    clear(s[len(s):len(s)+j-i]) // zero/nil out the obsolete elements, for GC
    return s
}

Impacted API

Same changes to these 4 5 functions:

slices.Delete
slices.DeleteFunc
slices.Compact
slices.CompactFunc
(edit) slices.Replace

Backward compatibility

Changing the behavior of slices.Delete is backward compatible. Its current documentation does not promise to zero or not zero the obsolete elements.

Cost

Runtime overhead of having slices.Delete zero the obsolete elements, per this benchmark:

When deleting 1 element

~1% (this is a common use case)

When deleting a large range of elements

~30%

The GC work of "collecting" obsolete objects when they will become unreachable is expected to be very small, and is not specifically attributable to slices.Delete (just normal GC work).

Pointers vs. Values

The proposal is mostly useful for slices whose elements are pointers, or contain pointers.

Should we try to keep the existing behaviour for slices of value elements (e.g. int, or a struct of values)?

Probably not, for 2 reasons:

Principle of least astonishment: if we zero the pointers, we should zero the values as well.
It is not possible to express in Go generic code “do this operation, but only if the type parameter E is a pointer or contains pointer”

List ownership

We could argue that any use of a subslice s[i:j] always leaves elements not set to zero, before i and after j.

If slicing doesn’t do any zeroing, should Delete have to do it?

One major difference is that it makes sense to have various parts of a program use various slices (“views”, “windows”) on the same backing array. The parts need to be careful, as changes made by one may affect the other parts. Using append in such a context is subtle, with reallocation happening transparently. The ownership and responsibility are shared. An arbitrary number of agents only reading and slicing is always fine, not mutating the backing array contents.

Delete is different because it is destructive by nature. No part of the program is supposed to make sense of “a slice where some elements were shifted, and some obsolete elements were left in place” by some other code. Only the slice returned by Delete makes sense, and any other slice of the same backing array can be regarded as obsolete. The caller of Delete gets de facto the ownership of the backing array.

What other languages do

Java

ArrayList.remove() nulls out the tail element: src
ArrayList.removeRange() nulls out the tail elements: src

C#

List<T>.RemoveAt() nulls out the tail element src
List<T>.RemoveRange() nulls out the tail elements: src

C++

Vector.erase() does not null out the tail element: demo

Edit: precision about `a[len(a):cap(a)]`

It is out of scope of the current proposal to write anything to the original tail (the elements v17, v18, v19 in the diagram).

We must not assume ownership of the elements beyond the original length, and we must not zero them out. They might be used for legit purpose by other parts of the program, in theory.

from my engine room: it's exactly the lack of zeroing behavior why I still need to keep my own code in many places, when I really would like to migrate to stdlib here.

I think this would be kind of weird because it returns a slice instead of taking a pointer, so it would be weird to do stuff out of band. Why not just add a new slices.ClearTail?

func ClearTail[E any, S ~[]E](s S) {
   clear(s[len(s):cap(s)])
}

Not really out of band, as Delete is expected to be destructive in-place. IMO the important consideration is that the tail is now "garbage for everyone", other slice headers pointing to the same memory should be regarded as invalidated.

ClearTail is nice to have but has 2 drawbacks in the context of Delete:

the burden of explicitly calling ClearTail falls on the user
ClearTail is clearing up to cap(s) instead of old len(s), that's too many. Most often, this is a mild performance penalty. In some rare cases (where the elements beyond len(s) are actually used elsewhere), this is a serious bug.

That's persuasive. It's probably fine to change the behavior here since, anything relying on the old behavior was broken.

could this proposal please also applied to the exp/slices version, so that code that follows the N and N-1 support strategy will benefit as early as possible?

Dropping an element is equivalent to nil-ing a pointer under the circumstance that memory (de-)allocation performed by the runtime and GC are precisely equivalent to the behavior needed to correctly drop the element and associated resources. This is the straightforward thing and often the case, but in every situation where this isn't true, would the proposed behavior of slices.Delete be destructively incorrect?

With the current behavior (and suggested by the current documentation, really) problems can be resolved by dropping elements following slices.Delete, with a local understanding of the correct semantics of dropping.

For clarification, std::vector<T, Alloc>::erase does not zero the content but it does destroy the objects, leaving the trailing elements as uninitialised memory.

This means that, while a std::vector<char>::erase does not zero the elements, std::vector<std::unique_ptr<T>>::erase will release the memory associated with those pointers.

Same problem for slices.Replace.

@go101 thanks, I'll add Replace to the section "impacted API"

I think this only really make sense if you are not expecting to reuse the space cleared out.
If I delete an element but then append, the zeroing is slowing down my program for no reason.

I think that in the cases trailing values are a valid concern something like #60136 or #63393 (comment) is a better solution.
The expected pattern would be:

s = slices.DeleteFunc(s, filter)
s = append(s, stuff...)
slices.ClearTail(s)

Or

slices.ClearTail(slices.DeleteFunc(s, filter))

Assuming Go2, IMO a better solution would be for reslicing a slice beyond it's length to zero the "new" elements, then we could not zero things when slicing down, the GC would instead be able to inspect the len fields of the slice header to determine how many elements it should scan (or single shot elements for pointers to elements).
The point of having the zeroing on extension is that if you are extending in an append, or extending quickly followed by a write, it would be easy for a compiler to figure out the zeroing is not necessary.
This would be at least two big breaking changes tho (how reslicing works and how the GC view liftetime of variably sized objects). 😞

@changkun

@changkun: All the changes you mention here are intended, or at least expected.
Could you be more specific about your production code? The examples you cite here don't look like production code.

@randall77

@randall77 It would be harder to paste the relevant production code here, but the idea is well demonstrated in the above example code. We see more than one case where production services crashed due to this behavior change. The len(x) shrinks to 5, but len(y) remains 6 seem to be the root cause.

@changkun

@changkun I think we need to see some realistic code to decide whether this is a serious issue or not. Generally it is not a great idea to have two slices to the same backing store and modify through one without any expectations of modification by the other.

For instance, in the first case you cite, instead of y ending in 5 5 it now ends in 5 0. It seems to me that it is just as likely to be buggy to have a repeated value than to have a zeroed value. What does your code look like for which the former is ok but the latter is bad?

The len(x) shrinks to 5, but len(y) remains 6 seem to be the root cause.

That's just how slices work. There's no way len(y) is going to change by doing any conceivable operation on x.

@changkun

@changkun indeed some tests were passing in Go 1.21 and will now fail in Go 1.22. This is expected and intended. We observed this internally at Google as well. A full blog post about this will be published this week in the Go blog.

While it is certainly not "funny" to break user code, I do believe that only incorrect code will be broken and need fixing. I tried to articulate this in the section "List ownership" above: keeping using old slice values is mostly a mistake in the first place.

To clarify, nothing was stated to object this change; the previous examples just put the consequence of this change on the table.

It is another discussion and judgment on whether the code produced by an engineer is buggy or not; at least, there is nothing that warns them to not do so. Users should continuously improve their testing infrastructure to prevent such an outage from happening at an early stage but also require Go release to spend additional effort to communicate and inform users of the potential consequences.

I believe I read about this proposal months back and failed to anticipate how it will impact user code as well.

@randall77

To clarify, nothing was stated to object this change; the previous examples just put the consequence of this change on the table.

It is another discussion and judgment on whether the code produced by an engineer is buggy or not; at least, there is nothing that warns them to not do so. Users should continuously improve their testing infrastructure to prevent such an outage from happening at an early stage but also require Go release to spend additional effort to communicate and inform users of the potential consequences.

I believe I read about this proposal months back and failed to anticipate how it will impact user code as well.

You are right that this a user-visible change, and strictly speaking a backward incompatible one. But as @randall77 pointed out, it's difficult to imagine an algorithm that would intentionally rely on the tail of the array being unmodified after a call to Delete, since this implies a very intimate and fragile coupling between the caller of Delete and the logic assuming the tail is unchanged. If I was to see such code during review, I would almost certainly call it out as a likely mistake or at least an opportunity for clarification.

Could you post a reduced example of code that actually does this?

The most likely circumstance I can think of is code that is working with subslices in a transparent manner such that it doesn't know that they're subslices of a larger slice. Thus is still inherently dangerous, though, as an incorrect append() could also affect other code unexpectedly. The correct thing to do in those cases would be to 3-slice the subslices to remove the excess capacity before passing it down. That prevents both types of potential problems.

I wonder if it would be possible to rig up a vet check to catch some cases of that.

@DeedleFake

@DeedleFake could you make a small playground snippet about this?

This may not 100% address your suggestion, but 2 positive notes:

Delete(s, i, j) does write zeros before len(s), but leaves s[len(s):cap(s)] intact. "Clearing the tail" does not extend up to the whole capacity. It is possible, and maybe legit, to have other slice variables own and use the portion beyond len(s).
There will be a vet check (cmd/vet: warn when ignoring the return value of slices.Delete and friends #62729) in Go 1.23, when ignoring the return value of Delete

Delete(s, i, j) does write zeros before len(s), but leaves s[len(s):cap(s)] intact. "Clearing the tail" does not extend up to the whole capacity. It is possible, and maybe legit, to have other slice variables own and use the portion beyond len(s).

Oh, so it does. For some reason, I was under the impression that it cleared the remaining capacity, though now that I think about it that really doesn't make sense. Never mind, then, and yeah, anything adversely affected by this behavior is almost definitely a bug anyways.

Could you post a reduced example of code that actually does this?

Without digging into the exact business/product goal the relevant cases want to achieve, I don't directly see it being buggy, as it met the expectation for a long period, even if the code itself might be an unexpected use.

The relevant code holds part of a slice, say B, and iterates it without knowing the original slice A being modified. However, as such, a slice may hold a struct, and it could contain ID and other fields to identify desired elements. When iterating B, it finds the target element based on the information inside a struct and does not necessarily have to find the element on its first attempt. Still, the overall process will retry until all target elements are found and processed eventually because there could be a final iteration that will only have one element to iterate and delete.

Met the expectation doesn't exclude being buggy. Your vague description looks to me like desaster waiting to happen all the time. Getting away with shoplifting also meets the business expectation, but still is unlawful.

The code before must not have cared about the slice being sorted or even having particular elements in it. Maybe it's just doing best effort background processing of some kind. So then in that case, wouldn't a simple if s[i] == nil { return } be a sufficient fix in this case?

Navigation Menu

Repository navigation

slices: have Delete and others clear the tail #63393

Proposal

Chronology

Current implementation

Problem: memory

Impact

Indirect impact

Partial solution: documentation

Problem: zeroing is difficult

Cognitive burden

Suggested implementation

Impacted API

Backward compatibility

Cost

When deleting 1 element

When deleting a large range of elements

Pointers vs. Values

List ownership

What other languages do

Java

C#

C++

Edit: precision about `a[len(a):cap(a)]`

32 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

slices: have Delete and others clear the tail #63393

Description

Proposal

Chronology

Current implementation

Problem: memory

Impact

Indirect impact

Partial solution: documentation

Problem: zeroing is difficult

Cognitive burden

Suggested implementation

Impacted API

Backward compatibility

Cost

When deleting 1 element

When deleting a large range of elements

Pointers vs. Values

List ownership

What other languages do

Java

C#

C++

Edit: precision about a[len(a):cap(a)]

Activity

thediveo commented on Oct 5, 2023

earthboundkid commented on Oct 5, 2023

Deleplace commented on Oct 5, 2023

earthboundkid commented on Oct 5, 2023

thediveo commented on Oct 5, 2023

AndrewHarrisSPU commented on Oct 5, 2023

merykitty commented on Oct 6, 2023

zigo101 commented on Oct 6, 2023

Deleplace commented on Oct 6, 2023

Jorropo commented on Oct 6, 2023

32 remaining items

randall77 commented on Feb 20, 2024

changkun commented on Feb 20, 2024

randall77 commented on Feb 20, 2024

Deleplace commented on Feb 20, 2024

changkun commented on Feb 20, 2024

adonovan commented on Feb 20, 2024

DeedleFake commented on Feb 21, 2024

Deleplace commented on Feb 21, 2024

DeedleFake commented on Feb 21, 2024

changkun commented on Feb 25, 2024

thediveo commented on Feb 25, 2024

earthboundkid commented on Feb 25, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Edit: precision about `a[len(a):cap(a)]`