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.
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
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
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
>> 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.
>> 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.
>>> 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.
>>> 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
> email to golang-nuts+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
You received this message because you are subscribed to the Google Groups
To unsubscribe from this group and stop receiving emails from it, send an email
For more options, visit https://groups.google.com/d/optout.