Deleting an item from a slice: append or copy?

[Ibrahim M. Ghazal]

Should I use append or copy to delete an item from a slice? Which is
more efficient (speed- and memory-wise)? Or is there possibly a third
better way?

For example, to delete the i'th item from slice s using append:
s = append(s[:i], s[i+1:]...)

Using copy:
copy(s[i:], s[i+1:])
s = s[:len(s)-1]

To me, append feels more natural (and shorter), but I'm wondering if
it's making unnecessary allocations.

[roger peppe]

if you don't mind about the order of items in your
slice, you can do:
s[i] = s[len(s)-1]
s = s[0:len(s)-1]

[bflm]

On Dec 20, 5:35 pm, "Ibrahim M. Ghazal" <img...@gmail.com> wrote:
> Should I use append or copy to delete an item from a slice? Which is
> more efficient (speed- and memory-wise)?

Best is to benchmark it. "Measurement beats speculations."

[GoogleFans]

to be consistent.

I think it should act like maps

s[i] = some, false

[jimmy frasche]

That would only be superficially consistient and miss the wider
consistiency of not doing magic behind your back. Removing something
from a map is fundamentally different than removing from a sequential,
contiguous list.

[Ibrahim M. Ghazal]

On Dec 20, 7:40 pm, roger peppe <rogpe...@gmail.com> wrote:
> if you don't mind about the order of items in your
> slice, you can do:
>   s[i] = s[len(s)-1]
>   s = s[0:len(s)-1]
>

Thanks. The order of items does matter in my current case, but that
could be useful elsewhere.

[Ibrahim M. Ghazal]

You're right. I wrote a benchmark that creates a slice of (b.N+1)
items then deletes the second (i.e., s[1]) item b.N times.

package foo

import (
"rand"
"testing"
)

func BenchmarkAppend(b *testing.B) {
b.StopTimer()
s := make([]interface{}, b.N+1)
for i := 0; i < b.N+1; i++ {
s[i] = rand.Int()
}
b.StartTimer()
for i := 0; i < b.N; i++ {
s = append(s[:1], s[2:]...)
}
}

func BenchmarkCopy(b *testing.B) {
b.StopTimer()
s := make([]interface{}, b.N+1)
for i := 0; i < b.N+1; i++ {
s[i] = rand.Int()
}
b.StartTimer()
for i := 0; i < b.N; i++ {
copy(s[1:], s[2:])
s = s[:len(s)-1]
}
}

And the results:
foo.BenchmarkAppend 100000 315823 ns/op
foo.BenchmarkCopy 100000 310980 ns/op

It looks like append is only slightly slower, and I'm guessing it
doesn't allocate any unnecessary memory since it's not much slower
than copy. But still, a more concrete evidence of append's memory
usage would be better. I'll try playing with the profiler later and
see for myself.

[Ibrahim M. Ghazal]

On Dec 21, 6:38 am, "Ibrahim M. Ghazal" <img...@gmail.com> wrote:
> It looks like append is only slightly slower, and I'm guessing it
> doesn't allocate any unnecessary memory since it's not much slower
> than copy. But still, a more concrete evidence of append's memory
> usage would be better. I'll try playing with the profiler later and
> see for myself.

I didn't need the profiler after all. The following program shows that
append does reuse the underlying array when deleting an item.

package main

import "fmt"

func main() {
arr := [...]int{0,1,2,3}
s := arr[:]

s = append(s[:1], s[2:]...)

fmt.Println(arr) // Output: [0 2 3 3]
}

[Steven]

If that's what your were looking for, the spec could have told you:

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

If you're decreasing the length of a slice, then it follows that the array has sufficient capacity for the new length, and thus would not be reallocated.

I thought you wanted to know if memory was allocated, which there's a good chance for, since the operation has to be safe when copying between intersecting slices. The same is true of copy.

[⚛]

"... good chance for ..."? Programming is *not* about taking chances.

You may want to look at the C source code "src/pkg/runtime/slice.c",
function "appendslice1".

[Steven]

No. Good for you. I hope your superiority complex has had a decent stroking.

Unfortunately, it only occured as a result of your inability to read
rather than just recognize isolated phrases that you have some
objection to.

What I said was that I thought they were asking a more difficult
question, "does the function allocate memory?" rather than the one
they ended up making a test case for, which is a non-question since
the answer is in the spec. I pointed out that there is a strong
possibility that memory is in fact allocated in order to indicate that
there is still something to investigate if you need to know, not as a
final answer.

> You may want to look at the C source code "src/pkg/runtime/slice.c",
> function "appendslice1".

A perfect place to find an answer, yes.

[Ibrahim M. Ghazal]

On Dec 22, 6:59 pm, Steven <steven...@gmail.com> wrote:
> What I said was that I thought they were asking a more difficult
> question, "does the function allocate memory?" rather than the one
> they ended up making a test case for, which is a non-question since
> the answer is in the spec. I pointed out that there is a strong
> possibility that memory is in fact allocated in order to indicate that
> there is still something to investigate if you need to know, not as a
> final answer.
>

Well, yes, that's what I was thinking about when I asked, the
possibility of allocating some temporary memory didn't occur to me
until you pointed it out.

> > You may want to look at the C source code "src/pkg/runtime/slice.c",
> > function "appendslice1".
>
> A perfect place to find an answer, yes.

I took a look at the source code, if the underlying array is big
enough (which is always the case when deleting an item), append is
just a memmove[1]. slicecopy (in the same file) is also just a
memmove, but it does fewer checks since it will stop when the
destination slice is full instead of allocating a new underlying
array. That explains why copy is marginally faster than append.

I'll continue to use append for deleting items, the difference isn't
big enough to make a difference, and I find it more readable. Thanks
for your help (also thanks to ⚛ for pointing me to the relevant
runtime source code).

[1] runtime·memmove is an ordinary C memmove, right?