Draft:Shift-To-Middle Array

• Comment: In accordance with Wikipedia's Conflict of interest policy, I disclose that I have a conflict of interest regarding the subject of this article. AthosDude (talk) 23:33, 23 March 2025 (UTC)

---

Shift-To-Middle Array

The Shift-To-Middle Array is a dynamic array data structure designed to optimize insertions and deletions at both ends while maintaining excellent cache locality. It serves as an alternative to standard array-based and linked-list-based containers such as std::deque, std::vector, and linked lists, balancing fast access times with efficient memory usage.

History

The Shift-To-Middle Array was invented in 2025 by Attila Torda as part of an effort to develop a more efficient implementation strategy for optimizing lists and deques. The motivation behind this structure was to address the performance limitations of traditional dynamic arrays and linked lists, particularly in scenarios requiring frequent insertions and deletions at both ends. Unlike linked lists, which suffer from poor memory access patterns, and std::deque, which can have fragmented memory allocations, the Shift-To-Middle Array leverages contiguous memory layouts to improve CPU efficiency through L1 cache optimizations, SIMD operations, and out-of-order execution.

Design and Implementation

The Shift-To-Middle Array differs from traditional dynamic arrays by maintaining extra buffer space at both ends of the array. Instead of always inserting elements at the beginning or end and performing costly shifts, the structure keeps elements centered within the allocated space. When the array grows, elements are repositioned toward the middle to ensure even distribution of free space at both ends. This reduces the number of required shifts compared to an std::vector, which only allows insertions at the back efficiently.

When the allocated space runs out, a resizing operation occurs, similar to std::vector, but with the additional step of shifting elements toward the middle of the new buffer. This helps maintain amortized O(1) insertions at both ends while providing fast random access.

Time Complexity

The following table compares the time complexity of Shift-To-Middle Array operations with other common data structures:

Time Complexity Comparison

Operation	ArrayList (std::vector)	Linked List	Shift-To-Middle Array
Access (by index)	O(1)	O(n)	O(1)
Insertion at head	O(n)	O(1)	O(1) amortized
Insertion at tail	O(1) amortized	O(1)	O(1) amortized
Insertion in middle	O(n)	O(n) (without iterator) / O(1) (with iterator)	O(n)
Deletion at head	O(n)	O(1)	O(1) amortized
Deletion at tail	O(1)	O(1)	O(1) amortized
Deletion in middle	O(n)	O(n) (without iterator) / O(1) (with iterator)	O(n)
Cache Locality	Excellent	Poor	Excellent

Performance and Benchmarks

Benchmarks comparing Shift-To-Middle Array vs. std::deque vs. ExpandingRingBuffer vs. std::queue demonstrate that performance improvements depend on CPU and GPU capabilities, such as multi-core parallelism, SIMD optimizations, and cache efficiency.

The benchmarks were compiled using GCC with the -O3 optimization flag, ensuring high-performance execution. Results vary based on hardware specifications and workload characteristics.

Use Cases

The Shift-To-Middle Array is particularly useful in applications requiring:

• High-performance queue-like structures that frequently modify both ends.
• Game engines and real-time systems where memory locality and speed are critical.
• Networking applications where fast buffer resizing and element access are needed.
• Dynamic sequences in computational geometry and physics simulations.

External Links

• Discussion on Hacker News about the topic – A thread discussing the topic on Hacker News.
• Shift-To-Middle Array GitHub Repository – A GitHub repository containing the implementation of the Shift-To-Middle Array algorithm.