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

81–90 of 121 posts

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

#81

Post by pclmulqdq »

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…

The C++ std::deque usually uses blocks that are big enough not to worry about memory concerns. The linked list has bad performance because you have tiny blocks of memory, but blocks of 256 objects are usually big enough that they are contiguous for all practical purposes (paging, allocation, and caching). Libc++, the library associated with clang and the LLVM project, uses a block of 4096 objects in its deque.

This is an alternative that has been shown in the literature many times before, and it works well for certain access patterns, but is a major waste of resources for others. Yours in particular is great when you are pushing/popping both sides equally. The C++ standard deque is made for unknown but unequal directions of push/pop (while still having ~O(1) random access) with 50/50 ratio of push and pop.

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

#82

Post by mystified5016 »

severino wrote: post #71
actionfromafar wrote: post #66

Earlier quoted context omitted.

Well the code should not be duplicated, only method signatures, but yes. It’s very common. Edit: after a while you don't even think about it (and of course, there are reasons for it) but sometimes I pause and think. It didn't have to be this way. Some C++ libraries are what's called "header only" which makes them very easy to integrate into your own code. Downside is that it may take longer to compiler your code. (An…

Thanks, what you explain in your comment is the idea I had, too, although I've little experience in C++. But I was confused after taking a look at this project's source and seeing all the duplicated code between ShiftToMiddleArray.h and ShiftToMiddleArray.cpp, and not only signatures. I wasn't sure if that was done for some purpose.

Typically you declare a member in the header and define it in the CPP. But you can also freely write definitions in your header.

You cannot define the same member twice, tough.

In an ideal universe, your header contains only declarations for functions which are defined elsewhere. If you define something in your header, it should be something intended to be accessed without the CPP. Say, a utility function to give you a string describing an error code.

In reality, because there are no hard rules, people do anything. You get definitions mixed into headers and such.

Look at it this way, each CPP file is intended to be an isolated compiled object. The header defines the ABI you use to talk to that object. And members defined in your header get copied into other CPP files and also compiled there. You want all reusable code to go into a separate compilation so it's not duplicated all over your binary.

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

#83

Post by actionfromafar »

mystified5016 wrote: post #82
severino wrote: post #71

Earlier quoted context omitted.

Thanks, what you explain in your comment is the idea I had, too, although I've little experience in C++. But I was confused after taking a look at this project's source and seeing all the duplicated code between ShiftToMiddleArray.h and ShiftToMiddleArray.cpp, and not only signatures. I wasn't sure if that was done for some purpose.

Typically you declare a member in the header and define it in the CPP. But you can also freely write definitions in your header. You cannot define the same member twice, tough. In an ideal universe, your header contains only declarations for functions which are defined elsewhere. If you define something in your header, it should be something intended to be accessed without the CPP. Say, a utility function to give you…

Just want to add the tiny nitpick that there's no C++ "law" that the end result must be code duplicated in the binary. It's just that it may require link time optimizations and untangling which in practice is not done, so you'd end up with duplicates, after all.

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

#84

Post by scottlamb »

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…

I don't think the bip buffer solves a real problem. Let's say I'm using it as a read buffer.

> The upshot of all of this is that on average, the buffer always has the maximal amount of free space available to be used, while not requiring any data copying or reallocation to free up space at the end of the buffer. ... Another possibility which was brought up in the bulletin board (and the person who brought it up shall remain nameless, if just because they... erm... are nameless) was that of just splitting the calls across wraps. Well, this is one way of working around the wrapping problem, but it has the unfortunate side-effect that as your buffer fills, the amount of free space which you pass out to any calls always decreases to 1 byte at the minimum - even if you've got another 128kb of free space at the beginning of your buffer, at the end of it, you're still going to have to deal with ever shrinking block sizes.

So it maximizes the contiguous free bytes. I feel like the author just never knew about readv? Passing a couple iovecs completely solves this problem in a much better way.

What seems far more valuable for the used space to be contiguous, as parsing APIs often expect this. bip buffers don't offer that, right?

Now let's say I'm using it as a write buffer. I've never had the problem of needing it to be contiguous on either side. On the input side, I could imagine some application API that really wants to write into a contiguous buffer, but it hasn't been my experience. On the output side, there's writev.

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

#85

Post by bogwog »

actionfromafar wrote: post #66
severino wrote: post #63

Earlier quoted context omitted.

A little off-topic, but is it usual in C++ to have a header (.h) and a source (.cpp) where the attributes and most of the methods are identical in both files, but with some more methods in the header file?

Well the code should not be duplicated, only method signatures, but yes. It’s very common. Edit: after a while you don't even think about it (and of course, there are reasons for it) but sometimes I pause and think. It didn't have to be this way. Some C++ libraries are what's called "header only" which makes them very easy to integrate into your own code. Downside is that it may take longer to compiler your code. (An…

Modules 100% solve this problem, but broad compiler support is still (frustratingly) lacking.

Some day, a class like in the OP will be implementable in a single file. The compiler will compile that once, and users can 'import' it infinitely without worrying about the usual header inclusion pitfalls, and without incurring any compile time overhead. The amount of electricity saved from the reduced compilation work will save us from the current climate disaster, and we'll become a maximally productive society unburdened by slow C++ compilers.

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

#86

Post by [deleted] »

IshKebab wrote: post #68
TylerGlaiel wrote: post #59

This implementation grows indefinitely if you repeatedly push to the head and remove from the tail, even if the max number of elements in the array is small

Does it definitely do that? You could easily avoid it by making the "resize" really a move if you don't actually need more space. I feel like they're over-selling it anyway by comparing to `std::deque` (which is not hard to beat). The only advantage this has over a standard ring buffer (like Rust's VecDeque) is that the data is completely contiguous, but you'll pay a small performance cost for that (regular memmove's…

[deleted]

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

#87

Post by usefulcat »

ksherlock wrote: post #11

A couple notes looking at the c++ implementation - this is going to have problems with non-trivial types. (Think about destructors or move constructors like std::unique_ptr). If you don't want to deal with them, at least add a static_assert(std::is_trivially_copyable ::value == true); - front() doesn't return a reference and it doesn't even return the front - adding iterators (begin()/end()) will let it play nice wit…

Note that this implementation (I looked at the c++ code) will repeatedly double the amount of allocated memory, even if the usage of the queue is such that it never contains more than one item at a time. It's not much different from a memory leak.

    void insert_head(const T& value) {
        if (head == 0) resize(); //
It looks like there is a fix for this behavior in resize() (to avoid repeated reallocation when the queue size is small relative to capacity), but it is currently commented out..

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

#88

Post by sumtechguy »

mystified5016 wrote: post #82
severino wrote: post #71

Earlier quoted context omitted.

Thanks, what you explain in your comment is the idea I had, too, although I've little experience in C++. But I was confused after taking a look at this project's source and seeing all the duplicated code between ShiftToMiddleArray.h and ShiftToMiddleArray.cpp, and not only signatures. I wasn't sure if that was done for some purpose.

Typically you declare a member in the header and define it in the CPP. But you can also freely write definitions in your header. You cannot define the same member twice, tough. In an ideal universe, your header contains only declarations for functions which are defined elsewhere. If you define something in your header, it should be something intended to be accessed without the CPP. Say, a utility function to give you…

> In reality, because there are no hard rules, people do anything. You get definitions mixed into headers and such.

All of that is done so forward declaration works.

The problem is #include does just what it says on the tin. It includes whatever is in the file into the file the #include is in. By convention that is .h/.hpp for headers. But there is nothing saying it can not be something like #include or even another .cpp file (seen it). Now that probably will not compile. But the pre-processor will include it at the spot you say. Then promptly barf on it because it does not parse.

The compiler says anything you declare though needs to be defined. Usually a built in type, or class, or struct, or typedef. Basically defined before use. So technically I can glom all of my stuff together and if I get it in the right order I could have one giant file and zero new headers. But we like our class/function files to be semi organized so forward declaring items is the norm.

C++ adds a bit of a twist on all of this. In that a class file does not have to be all in one spot. It can be in a header or smeared across 20 other files. The one rule the linker needs is hey is this declared before you use it. That way the linker can eventually find the right code to call.

To understand the 'why' you have to understand the linker and preprocessor work together to make it happen.

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

#89

Post by mythmon_ »

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

That's what I learned in my university data structures course. I don't know anything about C++'s std::deque though.

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

#90

Post by scottlamb »

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…

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

I notice you do not include ring buffers in this headline alternatives list. To me ring buffers seem the most natural comparison. I'd expect them to perform strictly better (no movement, no amortized constant time). But parsing APIs often can't handle the discontinuity where they wrap around, so I think this or something like it has value.

I do see you included this `ExpandingRingBuffer` in your benchmarks, and wrote the following:

> ExpandingRingBuffer performs well for small to medium container sizes but becomes less efficient for larger sizes, where Shift-To-Middle Array and std::deque maintain better performance.

Why do you think ExpandingRingBuffer's performance suffers? Is this about frequent expansion? Otherwise, as mentioned above, I'd expect a well-implemented ring buffer to be hard to beat.

Post reply on HN