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

41–50 of 121 posts

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

#41

Post by ufo »

manwe150 wrote: post #39
ufo wrote: post #16

Earlier quoted context omitted.

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

There are many situations where those little differences completely vanish because of instruction pipelining. Only way to know is to actually measure it.

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

#42

Post by dzaima »

rowanG077 wrote: post #40
dzaima wrote: post #38

Earlier quoted context omitted.

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.

Right, indeed, amluto's comment is incorrectly broad. But it's still a thing that a ring buffer cannot guarantee, but std::deque impls must.

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

#44

Post by eru »

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?

The current implementation doesn't.

You could add that functionality via 'tombstones': when you delete an element, you replace it with a 'tombstone' marker in the structure.

Whenever you clean up the structure (eg for a resize), you skip the tombstones when you copy the old contents over.

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

#45

Post by eru »

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…

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

Yet another reason fork was never a good design choice.

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

#46

Post by dzaima »

eru wrote: post #44
ntonozzi wrote: post #9

Earlier quoted context omitted.

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

The current implementation doesn't. You could add that functionality via 'tombstones': when you delete an element, you replace it with a 'tombstone' marker in the structure. Whenever you clean up the structure (eg for a resize), you skip the tombstones when you copy the old contents over.

That'd break arbitrary reads being contiguous O(1) though.

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

#47

Post by dzaima »

The ExpandingRingBuffer.h is rather bad for a representation of a ring buffer - it uses modulo for the index calculation, which is pretty damn bad and should really at the very least be masking by a power-of-two.

(it might very-slightly-but-not-really be excusable if the reason was memory utilization.. ..but the resize does "size_t new_capacity = capacity * 2;" so it does doubling anyway. Also, see reply noting that you don't even need power-of-two sizes for fast wrapping, which I managed to completely forget about)

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

#48

Post by pcwalton »

duped wrote: post #24
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…

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…

Oh, I see, it's actually on Wikipedia [1]. I figured I wasn't the first one to invent the idea :)

[1]: https://en.wikipedia.org/wiki/Circular_buffer#Optimization

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

#49

Post by kragen »

dzaima wrote: post #47

The ExpandingRingBuffer.h is rather bad for a representation of a ring buffer - it uses modulo for the index calculation, which is pretty damn bad and should really at the very least be masking by a power-of-two. (it might very-slightly-but-not-really be excusable if the reason was memory utilization.. ..but the resize does "size_t new_capacity = capacity * 2;" so it does doubling anyway. Also, see reply noting that…

Most ring buffers that aren't powers of 2 in size can still get by with i == max ? 0 : i+1 and i ? i-1 : max. On most hardware these will be almost as fast as just i+1 and i-1, while division will be much slower, even on recent hardware.

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

#50

Post by dzaima »

kragen wrote: post #49
dzaima wrote: post #47

The ExpandingRingBuffer.h is rather bad for a representation of a ring buffer - it uses modulo for the index calculation, which is pretty damn bad and should really at the very least be masking by a power-of-two. (it might very-slightly-but-not-really be excusable if the reason was memory utilization.. ..but the resize does "size_t new_capacity = capacity * 2;" so it does doubling anyway. Also, see reply noting that…

Most ring buffers that aren't powers of 2 in size can still get by with i == max ? 0 : i+1 and i ? i-1 : max. On most hardware these will be almost as fast as just i+1 and i-1, while division will be much slower, even on recent hardware.

..yep, true, completely slipped my mind. So modulo is just trivially always the bad choice.

Even for arbitrary indexing "tmp=head+index; buffer[(tmp >= capacity) ? tmp - capacity : tmp]" or so is gonna be better. (assuming the compiler compiles it to something branchless. Or, probably even if it doesn't - division might end up slower than the worst-case of 50% misprediction! And for sequential indexing it's even gonna be predictable.)

Post reply on HN