Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

31–40 of 121 posts

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

#31

Post by tialaramex »

dehrmann wrote: post #17
AttilaT wrote: post #2

I 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).

No, that's what Rust's VecDeque is, the C++ std::deque is something which you wouldn't invent today, but alas C++ is wedded to how things were done in the 1990s sometimes before.

std::deque does have practical uses, but they're rare and many implementations aren't well suited even to those uses. Unlike VecDeque most people should just ignore it.

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

#32

Post by acmj »

dehrmann wrote: post #17
AttilaT wrote: post #2

I 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).

std::deque typically uses chunked arrays. It is more complex but tends to be faster than a ring buffer based implementation.

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

#33

Post by kragen »

akoboldfrying wrote: post #26
kragen wrote: post #20

Earlier quoted context omitted.

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…

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/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.

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

#34

Post by Arnavion »

kragen wrote: post #20
Arnavion wrote: post #18

Earlier 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 read the code before I made my comment. It does exactly what I described.

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

#35

Post by o11c »

pcwalton wrote: post #21

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 min…

For C++, that's only valid for some subset of types, which currently can't be expressed with type traits. "Address-free" has a close enough definition in the context of atomics.

Trivially moveable types are probably sufficient (at least, I can't construct a case where being trivially copyable is needed), but not necessary; there are many things a special member function can do without caring about the address.

In practice, the main problem is that you can't use private mappings (which are the default and for good reason); you have to use shared mapping, which are very finicky to set up and cause infelicities with `fork`. [This does make me wonder how reflinks/`copy_file_range` interact with `mmap` and the page cache.]

Really, you should just fix all your APIs to take an `iovec` array.

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

#36

Post by kragen »

Arnavion wrote: post #34
kragen wrote: post #20

Earlier quoted context omitted.

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 read the code before I made my comment. It does exactly what I described.

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.

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

#37

Post by Arnavion »

kragen wrote: post #36
Arnavion wrote: post #34

Earlier quoted context omitted.

I read the code before I made my comment. It does exactly what I described.

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.

Yes.

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

#38

Post by dzaima »

rowanG077 wrote: post #30
amluto wrote: post #23

Earlier quoted context omitted.

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.

https://en.cppreference.com/w/cpp/container/deque:

> When inserting at either end of the deque, references are not invalidated by insert and emplace.

> push_front, push_back, emplace_front and emplace_back do not invalidate any references to elements of the deque.

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

#39

Post by manwe150 »

ufo wrote: post #16
manwe150 wrote: post #13

Earlier quoted context omitted.

Both are O(1) datastructures, but indexing a ring buffer is slightly more costly compared to this and insertion is slightly more costly for this than a ring. Probably usually works out in favor of this design though for net performance usually?

I'd love to see performance numbers for this, if they're available. My hunch is that indexing cost would be about the same.

They both have an offset, but ring buffers aren’t contiguous so they also need a branch or modulus to handle wrap around. Either can be cheap, but clearly that is strictly more costly than not having the extra operation (even if very little). Only matters for random indexing also, since for mutation the situation is swapped

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

#40

Post by rowanG077 »

dzaima wrote: post #38
rowanG077 wrote: post #30

Earlier quoted context omitted.

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.

https://en.cppreference.com/w/cpp/container/deque : > When inserting at either end of the deque, references are not invalidated by insert and emplace. > push_front, push_back, emplace_front and emplace_back do not invalidate any references to elements of the deque.

That's a guarantee of some specific operations on deque not a general requirement on the entirety of deque. I looked at your link and erase_if does not have that requirement. So I'd imagine that can and does invalidate references aka move elements.
Post reply on HN