# Re: [go-nuts] Pop out first element of a slice.

```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.

On Tue, Sep 20, 2016 at 11:12 PM, Gabriel Adumitrachioaiei <

> Very good mathematical explanation. Thanks!
>
> On Tuesday, September 20, 2016 at 7:24:39 PM UTC+3, Axel Wagner wrote:
>>
>> 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
>> 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.
>>
>> On Tue, Sep 20, 2016 at 6:03 PM, Ian Davis <m...@iandavis.com> wrote:
>>
>>> 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
>>>
>>>
>>> --
>>> 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
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>> --
> 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