Interesting alternative idea I thought of just now: a data structure that works like VecDeque (a circular buffer) but uses mmap to map two views onto the same pages right after one another. That would ensure that the entire array can be accessed in a consecutive fashion, no matter where it gets split, without any copying. The downside is that reallocation would be really slow, involving multiple syscalls, and the minimum size of the array would be 4kB or more, depending on the page size.
Shift-to-Middle Array: A Faster Alternative to Std:Deque?
21–30 of 121 posts
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#22You should call it Middle-Out Array for maximum Internet points /jk
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#23I 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…
> Unlike std::deque, which uses a fragmented block-based structure I always assumed deque implementations were ring buffers that double in size once full so that prepend/append operations are amortized O(1).
deque does not move elements once added, so it can’t be implemented like that.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#24Interesting alternative idea I thought of just now: a data structure that works like VecDeque (a circular buffer) but uses mmap to map two views onto the same pages right after one another. That would ensure that the entire array can be accessed in a consecutive fashion, no matter where it gets split, without any copying. The downside is that reallocation would be really slow, involving multiple syscalls, and the min…
I've seen this trick used around, where it really shines is when you want to prepare/commit a range of the ring buffer when interfacing with something that wants a contiguous chunk as an arg, using the mmap hack lets you pass any pointer into the ring buffer without needing to split it to handle the wraparound case.
There are a few blog posts out there about it, eg https://lo.calho.st/posts/black-magic-buffer/. One data structure that works around the limitations is the bip buffer: https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The.... In that article the author talks about the mmap trick.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#25Isn’t this already implemented by NSMutableArray in Apple SDKs/libraries?
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#26Earlier quoted context omitted.
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.
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.
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.)
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#27[deleted]
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#28is it just me or benchmarks report link is dead and hence there's no way to see the comparison
It’s not dead as such but it looks like OP may have left over some links they intended to add. That one and at least one other simply links to #, which means same page no anchor. And this is commonly done as a placeholder link before you have the link in place you intended to put there. Whereas a dead link for me would be one that leads elsewhere and results in 404 (page moved, file not yet created, etc) or an expire…
There’s a PDF with the results in the repo: https://github.com/attilatorda/Shift-To-Middle_Array/blob/ma...
BTW, if OP is reading this, I recommend having the baseline in your plots (e.g. std::deque) as the relative 100%, that way the performance improvement is clear.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#29I 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 ] ] ^ +…
Boost has a double ended vector with that name too. Devector
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#30Earlier quoted context omitted.
> Unlike std::deque, which uses a fragmented block-based structure I always assumed deque implementations were ring buffers that double in size once full so that prepend/append operations are amortized O(1).
deque does not move elements once added, so it can’t be implemented like that.
Is that an actual guarantee or just the current implementation? I'd expected that at the very least some functions that can operate on std::deque must require moves. erase_if immediately comes to mind.