3 ms·

It starts by adding the first element to the middle of the allocation and then the head and tail grow outwards as more elements are added at either end. Once t

It starts by adding the first element to the middle of the allocation and then the head and tail grow outwards as more elements are added at either end. Once the head reaches the front of the allocation or the tail reaches the rear of the allocation, it triggers a resize. The resize creates a new allocation with double the size and copies the original elements to the middle of this new allocation.

kragen 2y ago
That can't be correct, because then just adding elements at the front and removing them at the rear while maintaining a constant queue size such as 5 elements would trigger an infinite number of resizes. Maybe it only resizes under some circumstances, otherwise copying the live elements back to the middle? It still seems like that involves copying that a straightforward ring buffer avoids.
- akoboldfrying 2y ago
  I think the "resizes" occurring in this scenario would be to same-size buffers, meaning that the very same buffer could actually be reused. Provided that's in fact what is happening, then yes, this scenario would cause infinite resizes, all of which would be avoided by a ring buffer. But those resizes would still happen rarely enough to meet the amortised complexity claim, namely, 1 resize (copying of n elements) per n elements inserted. (I'm not at all certain that this is how it actually does work -- the README is light on details. But this is how it might work.)
  - kragen 2y ago
    You don't want to always resize to same-size buffers in that situation; consider a size-1024 buffer containing 1023 elements and a free space on the right. Pushing another item on the left can be done in the very same buffer, but requires copying all 1023 items one space to the right. If you then pop another item off the right end you are back to the starting state, so by repeating the process you need 511.5 element copies (in general, O(N) copies) per push or pop. There are obvious ways to resolve problems like this, but there are tradeoffs among them, and I would like to know which way the author chose and what the resulting complexity is without having to analyze (and debug) 270 lines of C++. Hmm, there's a PDF at https://github.com/attilatorda/Shift-To-Middle_Array/blob/main/ShiftToMiddleArray.pdf https://github.com/attilatorda/Shift-To-Middle_Array/blob/ma...... but it also doesn't explain things like this. It makes assertions about big-O performance, but doesn't explain the algorithm in enough detail to know whether they are correct.
    - senderista 2y ago
      I implemented the "2-level rotated array" structure a few years ago, which isn't designed to be used as a deque, but is at least less pathological than this (O(1) push_back/pop_back, O(sqrt(n) push_front/pop_front/insert/delete). https://github.com/senderista/rotated-vec https://github.com/senderista/rotated-vec
      - kragen 2y ago
        Oh, fantastic!
- Arnavion 2y ago
  I read the code before I made my comment. It does exactly what I described.
  - kragen 2y ago
    That sounds like pathologically bad behavior, using an amortized-linearly growing amount of memory to hold a constant amount of data? (Moreover, this is perhaps the most common use case for a queue.) It may be a correct description of the code, but it can't be a correct algorithm.
    - Arnavion 2y ago
      Yes.

kragen 2y ago

That can't be correct, because then just adding elements at the front and removing them at the rear while maintaining a constant queue size such as 5 elements would trigger an infinite number of resizes. Maybe it only resizes under some circumstances, otherwise copying the live elements back to the middle? It still seems like that involves copying that a straightforward ring buffer avoids.

akoboldfrying 2y ago
I think the "resizes" occurring in this scenario would be to same-size buffers, meaning that the very same buffer could actually be reused. Provided that's in fact what is happening, then yes, this scenario would cause infinite resizes, all of which would be avoided by a ring buffer. But those resizes would still happen rarely enough to meet the amortised complexity claim, namely, 1 resize (copying of n elements) per n elements inserted. (I'm not at all certain that this is how it actually does work -- the README is light on details. But this is how it might work.)
- kragen 2y ago
  You don't want to always resize to same-size buffers in that situation; consider a size-1024 buffer containing 1023 elements and a free space on the right. Pushing another item on the left can be done in the very same buffer, but requires copying all 1023 items one space to the right. If you then pop another item off the right end you are back to the starting state, so by repeating the process you need 511.5 element copies (in general, O(N) copies) per push or pop. There are obvious ways to resolve problems like this, but there are tradeoffs among them, and I would like to know which way the author chose and what the resulting complexity is without having to analyze (and debug) 270 lines of C++. Hmm, there's a PDF at https://github.com/attilatorda/Shift-To-Middle_Array/blob/main/ShiftToMiddleArray.pdf https://github.com/attilatorda/Shift-To-Middle_Array/blob/ma...... but it also doesn't explain things like this. It makes assertions about big-O performance, but doesn't explain the algorithm in enough detail to know whether they are correct.
  - senderista 2y ago
    I implemented the "2-level rotated array" structure a few years ago, which isn't designed to be used as a deque, but is at least less pathological than this (O(1) push_back/pop_back, O(sqrt(n) push_front/pop_front/insert/delete). https://github.com/senderista/rotated-vec https://github.com/senderista/rotated-vec
    - kragen 2y ago
      Oh, fantastic!
Arnavion 2y ago
I read the code before I made my comment. It does exactly what I described.
- kragen 2y ago
  That sounds like pathologically bad behavior, using an amortized-linearly growing amount of memory to hold a constant amount of data? (Moreover, this is perhaps the most common use case for a queue.) It may be a correct description of the code, but it can't be a correct algorithm.
  - Arnavion 2y ago
    Yes.