search

StephenCleary / Deque

Double-ended queue
MIT License
118 stars 25 forks source link

Smarter reallocation #7

Closed pchilds-cordel closed 9 months ago

pchilds-cordel commented 1 year ago

Currently growth of the deque operates by doubling in size. unfortunately this means that its old memory is never a sufficient size to be reallocated by the growing deque. See: https://gist.github.com/jemmanuel/b8277e7922e9b9947e2f171cc85f1d01 for a more thorough explanation. a smaller growth rate of ~1.3 to 1.5 would allow for better memory reallocation.

StephenCleary commented 1 year ago

Interesting read, but I'm not sure how well its assumptions work with the mark-and-sweep GC used by .NET.

It also assumes arrays are (or can be) reallocated in place, which is doable with a deque, but it's not as straightforward as with a list/vector type; a basic implementation would end up having to re-copy some subset of elements.

I also have a concern that this causes a performance characteristic change away from O(1) amortized allocations to O(N). The resulting O(N) may have a low enough constant, though, that it may work anyway.

I'd be willing to consider it if both of the following are true:

  1. The .NET BCL team adopts the same pattern for List<T>.
  2. There's broad performance analysis showing no pathological slowdowns and sufficiently beneficial improvements to warrant the additional complexity.
StephenCleary commented 9 months ago

Closing this for now; if the BCL team adopts it then I will too.