Pop out first element of a slice.

[Gabriel Adumitrachioaiei]

I don't understand something when I want to pop out first element of a slice and use it.

Here is my version:

s := []int{1,2,3}
first := s[0]
s = s[1:]

Here is a version that I saw in the standard library: https://golang.org/src/database/sql/sql.go#L791

first := s[0]
copy(s, s[1:])
s = s[:len(s) - 1]

I wonder, why do we need to translate the other elements to the left with a copy ? 

In the first case, I guess the first element will still be found in the underlying array, and in the second case the last element.

It's not like for avoiding a memory leak, because neither version allocates a new underlying array.

[Ian Davis]

If you append to the slice in the second version then the new element will reuse the space at the end of the backing array. In the first version Go may have to allocate to expand the backing array since there is no spare capacity.

Ian

[Gabriel Adumitrachioaiei]

Well, the capacity will be reduced by one. I don't think this makes much difference.

[Ian Davis]

On Tue, Sep 20, 2016, at 03:54 PM, Gabriel Adumitrachioaiei wrote:

Well, the capacity will be reduced by one. I don't think this makes much difference.

It makes a difference for a long running service that repeatedly pushes and pops.

Ian

[Gabriel Adumitrachioaiei]

You might be right, but I just don't realize how. Since capacity will be 2x or 1.5x as before, reallocating the slice will not happen often. Or do you think that this would still be worse than copying almost all slice everytime there is a pop ?

[Ian Davis]

On Tue, Sep 20, 2016, at 04:15 PM, Gabriel Adumitrachioaiei wrote:

You might be right, but I just don't realize how. Since capacity will be 2x or 1.5x as before, reallocating the slice will not happen often. Or do you think that this would still be worse than copying almost all slice everytime there is a pop ?

I think it depends on your use case. For the sql package I suspect the use case is a long running process with only a few members in the slice and a roughly level number over time. In that case the cost of copying will be small and offset by the savings in not needing to allocate.

However, if your use case is a a large slice that is iterated over via a pop operation, with few or no pushes then it makes more sense to simply reslice as you were doing in your original version.

Ian

[Axel Wagner]

if we assume, that the number of elements N is roughly stable (so pops and pushes are roughly balanced):

• If we append and reslice, we need to reallocate every N pops, because when space runs out, append will allocate 2N elements, so it has space for N new ones. After N pop/push sequences, it will run out of space and the capacity is again N, so it will allocate a new array with 2N elements, copy over N and continue. So every N pops, we need to allocate N elements and copy N elements, but don't incur any other costs.

• If we shift down, then we ~never need to reallocate, but need to copy N elements on each pop, so over N pops we need to shift N² elements

So, really, the question is how (N•copy(N)) compares  (alloc(N) + copy(N)). Which, as it seems to me, heavily depends on N, the memory you have, the GC pressure you have and your requirements.

The answer, as always with these kinds of question is: Benchmark both on your specific machine and your specific workload. If there is a clear winner, pick that one. Otherwise, choose either.

In general, I'd indeed assume that for somewhat filled fifo-queues the append-approach is faster. But I'd be willing to be surprised.

--
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Gabriel Adumitrachioaiei]

Very good mathematical explanation. Thanks!

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Axel Wagner]

FWIW, I whipped up a short benchmark for this and it seems to confirm my intuition. For small N (depending on the exact setup, on my machine, the threshold was around N ~ 16 to 20) the copy approach is significantly faster, but for growing N the quadratic behavior of the copy quickly makes it much worse.

http://sprunge.us/hZOj

The test-setup here mirrors my assumptions from the last mail. We allocate a fixed slice of length N and then do N pop-pushes, reflecting the conditions after the queue has been used for a while in a balanced manner and looking at long-term-ish performance characteristics to amortize the allocations.

I also looked at individual pop-push sequences (instead of doing N in a row, so this code: http://sprunge.us/UGdI) and this favors the append-way even more. Which makes sense, because then the allocations happen only very rarely for large N, so the disadvantage get's compensated.

Also, the usual caveats apply: This is a microbenchmark and benchmarking is hard and even though there is a relative difference, the absolute numbers are small enough that it likely doesn't make an actual difference in any realistic program.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.