Shift-to-Middle Array: A Faster Alternative to Std:Deque?
1–10 of 121 posts
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#2I recently developed a new data structure called the Shift-To-Middle Array, designed as an alternative to std::deque, std::vector, and linked lists. My goal was to optimize insertion and deletion at both ends, while also improving cache locality and performance compared to traditional implementations.
What is the Shift-To-Middle Array? Unlike std::deque, which uses a fragmented block-based structure, the Shift-To-Middle Array maintains a contiguous memory layout. Instead of shifting elements inefficiently (like std::vector), it dynamically redistributes free space toward the middle, reducing unnecessary data movement.
Key Features: Fast insertions & deletions at both ends (amortized O(1)) Efficient cache utilization (better than linked lists) Supports fast random access (O(1)) No pointer chasing (unlike linked lists) Parallelization & SIMD optimizations possible
Performance Benchmarks I benchmarked Shift-To-Middle Array vs. std::deque vs. ExpandingRingBuffer vs. std::queue across different workloads. Some highlights:
Push-heavy workload → Shift-To-Middle Array showed improved insertion performance over std::deque.
Pop-heavy workload → Showed improvements in memory access and removal operations.
Random insert/remove workloads → Demonstrated better cache efficiency compared to linked lists.
(Full benchmarks and source code available below.)
When Should You Use It? High-performance queue-like structures
Game engines (handling real-time events efficiently)
Networking applications (handling packet buffers)
Dynamic sequences (e.g., computational geometry, physics sims)
Would love to hear thoughts and feedback from the community! Have you encountered similar performance bottlenecks with std::deque or other dynamic structures?
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#3I made something similar to this ~10 years ago: https://github.com/orlp/devector. I never finished it (writing proper containers in C++ is a nightmare [1] [2] [3]), although I did start a similar project in Rust a year or two ago... which I also haven't finished yet (the repo is still private). The double-ended vector is very similar to a regular vector, it can just have free space on both ends:
[ [ elements ] ]
^
+--- ptr
---
I don't think you always want to shift to the middle. Rather, I propose the following strategy (which I do in the Rust crate, unsure if I did the same in C++ implementation):
1. When a request is made for more free space on one side, check if there is already enough free space, and if not,
2. Compute an amortized growing capacity (e.g. double the current capacity), and take the maximum of that with the requested capacity. While doing this ensure you only take into account the capacity of the side you want more space on (e.g. cap_back in the above picture when growing the back),
3. Check if halving the free space on the other side is sufficient to satisfy the amortized request, if yes, do not reallocate and just shift the values internally, otherwise,
4. Allocate a new buffer with the computed capacity, plus the same amount of free space on the other side and copy over the values.
The above strategy ensures you will not exceed 3N space (with doubling space on grow) even when the double-ended vector is used in a LIFO pattern. For example a regular Vec which doubles its size has a 2N total space worst-case.
[1] https://stackoverflow.com/questions/26902006/may-the-element... [2] https://stackoverflow.com/questions/27453230/is-there-any-wa... [3] https://stackoverflow.com/questions/26744589/what-is-a-prope...
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#4What benefits does this have over a standard VecDeque?
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#5What benefits does this have over a standard VecDeque?
The elements are completely contiguous, which can be nice for passing off (subslices) to other APIs, maximum speed iteration, etc.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#6is it just me or benchmarks report link is dead and hence there's no way to see the comparison
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#7What benefits does this have over a standard VecDeque?
For context: a VecDeque is a ring buffer backed by an array.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#8What benefits does this have over a standard VecDeque?
The elements are completely contiguous, which can be nice for passing off (subslices) to other APIs, maximum speed iteration, etc.
Does it have to move or resize when one of the sides reaches the end of the array? I presume that would be slower than a ring buffer that only grows when it's completely filled?
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#9I recently developed a new data structure called the Shift-To-Middle Array, designed as an alternative to std::deque, std::vector, and linked lists. My goal was to optimize insertion and deletion at both ends, while also improving cache locality and performance compared to traditional implementations. What is the Shift-To-Middle Array? Unlike std::deque, which uses a fragmented block-based structure, the Shift-To-Mid…
Sounds very cool! How do you implement efficient random deletes?
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#10Interesting! This is the kind of thing I like.
I'm having a hard time understanding the description. If I understand right, it's kind of like an inside-out gap buffer, or a hybrid of a gap buffer and a ring buffer? Is the free space in the array always contiguous? If not, is the non-free space? How is it different from ExpandingRingBuffer?