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

51–60 of 121 posts

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

#51

Post by HeliumHydride »

o11c wrote: post #35
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 pra…

C++26 is getting a trait called "trivial relocatability", which allows you to communicate that a type can be memcpy'd around without fear.

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

#52

Post by senderista »

kragen wrote: post #33
akoboldfrying wrote: post #26

Earlier quoted context omitted.

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…

I implemented the "2-level rotated array" structure a few years ago, which isn't designed to be used as a deque, but is at least less pathological than this (O(1) push_back/pop_back, O(sqrt(n) push_front/pop_front/insert/delete).

https://github.com/senderista/rotated-vec

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

#53

Post by oasisaimlessly »

ntonozzi wrote: post #9
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…

Sounds very cool! How do you implement efficient random deletes?

std::vector doesn't support efficient random deletes, so this (a generalization of std::vector along one specific axis) won't either.

Efficient random deletes and contiguous hole-free storage are completely at odds with each other.

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

#54

Post by nurettin »

Try to turn everything into arrays. Maps, hashmaps are convenient, but if possible, sort your data and use parallel arrays. Deques of fixed size turn into ring buffers. At work we have invented several data structures over the years with weird names and they all make use of some trick to shave off memory allocation times when working with time series.

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

#56

Post by evjohnst »

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…

This is pretty cool, thanks for sharing!

It looks like your benchmarks only cover average operation time. Have you thought about benchmarking p99 latency as well? I would expect insertions that cause reallocations to be slow enough that it might be an issue for some usecases.

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

#57

Post by yxhuvud »

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…

So essentially pushing the work to the TLB? Well, if there are people building moving GCs that manage to retain stable pointers that way, why not use it for a circular buffer as well.

> The downside is that reallocation would be really slow, involving multiple syscalls,

Scaling ring buffers up and down in size is not very performant anyhow, as a bunch of the elements in it tend to need to be copied.

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

#58

Post by bogdan-lab »

The main benefit list gives you comparing to vector is a stable memory. This is often an important property. But lists are slow with an element access. This problem is solved by deque.

Therefore, I argue that alternative to deque has to have a stable memory property. Otherwise, you can just use a vector.

This implementation is trying to do so, btw, but for some reasons it operates with a raw memory under the hood instead of just holding a vector and rotating it here and there. Such approach is unnecessary complicated and error-prone

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

#60

Post by TeMPOraL »

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

IDK, I thought the whole point of a deque was to string vectors into a linked list, so you get benefits of both, the most important ones being 1) cheap random access, and 2) insertion doesn't move stuff around in memory. I.e. that the deque's "vectors connected by pointers" is not an implementation detail, but the very nature of the beast.

Maybe I just took the boxes-and-arrows diagrams from C++ books too seriously.

Post reply on HN