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 > <javascript:>> 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 <javascript:>. >> 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.
