Shift-to-Middle Array: A Faster Alternative to Std:Deque?

Overview & Relation to Existing Structures

• Many commenters recognize this as a known pattern: “array deque” / double-ended vector / inside‑out gap buffer variant.
• Similar ideas exist in Boost’s devector, various Rust crates, Apple’s CFArray/NSMutableArray, JavaScriptCore’s array storage, etc.
• Distinctive property: fully contiguous storage while supporting push/pop at both ends; this is the main advantage over ring buffers / VecDeque (which are circular and discontinuous).

Functionality & Limitations

• Current implementation does not support efficient random deletion.
  • Tombstones are suggested, but that breaks the “contiguous, sliceable” property.
  • Thread debates whether efficient random deletes and contiguous hole‑free storage are fundamentally at odds; maps/dense structures are mentioned but don’t provide true sliceable arrays.
• Some argue that without stable memory addresses (like std::deque guarantees for end operations), it’s closer to a specialized std::vector than a real deque replacement.

Complexity, Pathologies & Performance

• Claimed amortized O(1) end operations are questioned:
  • Sliding-window pattern (push_front, pop_back at steady size) appears to cause repeated shifts or same‑size “resizes”, leading to excessive copying or unbounded capacity growth.
  • Several comments describe this behavior as almost a memory leak for small queues.
• For classic FIFO queues, a plain ring buffer requires no copying and is expected to be faster; this structure trades extra copying for contiguity.
• Benchmarks:
  • Links in the README are partially placeholders; a PDF in the repo shows small, workload‑dependent differences vs std::deque/std::queue.
  • Differences are generally interpreted as constant‑factor, not asymptotic, and sometimes only a few percent.
  • Suggestions: include std::deque as the explicit baseline, add p99 latency, medians, stddev, and better warmup (especially for the Java version).

Implementation Quality (C++ and Benchmarks)

• Multiple concrete issues noted in the C++ code:
  • Use of int instead of size_t, incorrect front(), mixing malloc/delete[], missing rule‑of‑five, commented‑out resizing fixes, poor std::bad_alloc handling, unnecessary inline hints.
• ExpandingRingBuffer baseline is also criticized for slow modulo indexing and non‑power‑of‑two optimization.
• General advice: lean on tooling (sanitizers, warnings, microbenchmark frameworks) and possibly LLMs for finding obvious API and UB bugs.

Alternative Designs & Growth Strategies

• Alternative “double-ended vector” strategy proposed: grow only the side that needs space, rebalance by shifting if possible, and only allocate larger buffers when necessary, with bounded 3N memory overhead.
• Debate around growth factor: 2 vs ~1.5 (golden-ratio‑like); real allocators, power‑of‑two sizes, and cache effects can reverse theoretical preferences.
• “Magic ring buffers” using mmap double‑mapping are discussed as a way to get contiguous views without copying, but with portability, TLB, aliasing, and fork complications.

Adoption & Use Cases

• Many find the idea interesting and educational, especially for understanding deque/ring‑buffer tradeoffs.
• Skepticism remains about practical advantage over well‑implemented std::deque/VecDeque, given:
  • Small measured gains,
  • Implementation bugs, and
  • Pathological behavior for common queue patterns.