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 < gabi.adumitrachioa...@gmail.com> wrote: > 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. >>> >>> 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 >>> 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 "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.
