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

91–100 of 121 posts

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

#91

Post by scottlamb »

leiroigh wrote: post #74
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…

The main problem with that is that it doesn't play nice with most languages. Consider int foo(int* ptr) { int x = ptr[1 Compilers/languages/specs tend to decide that `ptr` and `ptr + (1 foo(int*): mov eax, dword ptr [rdi + 262144] inc dword ptr [rdi] add eax, eax ret which gives undesired results if `ptr` and `ptr + (1<<16)` happen to be mapped to the same physical address. This is also pretty shit to debug/test -- s…

I don't think that's a fundamental problem. In say Rust (with its famously strict aliasing requirements), you obviously need some level of unsafe. You certainly want to ensure you don't hand out `&mut [T]` references that alias each other or any `&[T]` references according to either virtual or physical addresses, but that seems totally possible. I would represent the ring buffer with a raw pointer and length. Then for callers I'd construct `&[T]` and `&mut [T]` regions as needed that are never more than the full (unmirrored) length and thus never include the same byte twice. There are several existing Rust crates for the mirrored buffer that (though I haven't looked into their implementations recently to verify) presumably do this: slice-deque, vmcircbuf, magic-ring-buffer, vmap.

I do think though there are some downsides to this approach that may or may not be deal-breakers:

* Platform dependence. Each of the crates I mention has a fair bit of platform-specific `unsafe` code that only supports userspace on a few fixed OSs. They fundamentally can't work on microcontrollers with no MMU; I don't think WASM has this kind of flexibility either.

* Either setting up each buffer is a bit expensive (several system calls + faulting each page) or you have to do some free-listing on your own to mitigate. You can't just rely on the standard memory allocator to do it for you. Coincidentally just like last week I was saying freelisting is super easy for video frames where you have a nice bound on number of things in the list and a fixed size, but if you're freelisting these at the library level or something you might need to be more general.

* Buffer size constraints. Needs to be a multiple of the page size; some applications might want smaller buffers.

* Relatedly, extra TLB pressure, which is significant in many applications' performance. Not just because you have the same region mapped twice. Also that the buffer size constraints mentioned above make it likely you won't use huge pages, so on e.g. x86-64 you might use 4 KiB pages rather than 2 MiB (additional factor of 512x) or 1 GiB (additional factor of 262144x) as the memory allocator would help you do if they could be stuffed into the same huge page as other allocations.

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

#92

Post by pklausler »

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 like the opposite of a gap buffer.

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

#93

Post by kragen »

senderista wrote: post #52
kragen wrote: post #33

Earlier quoted context omitted.

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

Oh, fantastic!

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

#94

Post by pizlonator »

JavaScriptCore uses this technique for JavaScript arrays that are used as deques, like if you unshift/shift.

Here's the core data structure: https://github.com/WebKit/WebKit/blob/main/Source/JavaScript...

The logic that makes it work is in JSArray.cpp and other files in that directory.

Shift-to-middle is surprisingly performant and also surprisingly hard to get right.

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

#95

Post by fearthetelomere »

threeducks wrote: post #69
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 Congratulations, you have discovered the array deque! https://en.wikipedia.org/wiki/Double-ended_queue#Implementat... I'd like to point out a performance optimization. On resize, you create a new array with double the size and copy all the old elements to the middle of the new array with more space at the beginning AND at the end: https://github.com/attilatorda/Shift-To-Mid…

>- 2 is not the best growth factor because it makes it harder for the memory allocator to reuse memory. More modern implementations use smaller growth factors: https://en.wikipedia.org/wiki/Dynamic_array#Growth_factor

I've often wondered about this, so I'm curious to learn more. I agree in principle we should be more clever to ensure we have better memory use. However, half the implementations in the list you've linked use a growth factor of 2, so I'm confused about your point.

If it's not the best, what is? Do you know why these implementations opt for 2 if it's not the best choice?

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

#96

Post by epcoa »

sumtechguy wrote: post #88
mystified5016 wrote: post #82

Earlier quoted context omitted.

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…

> The compiler says anything you declare though needs to be defined.

No it doesn’t. If that were true dynamic linking would not be a thing, but it’s not even true in the most basic way either.

> Basically defined before use.

Also not true. But this is “not even wrong” since “before use” isn’t defined here, however if it is meant to be appears before in the input, then that is wrong.

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

Because of the way C++ is defined this is somewhat true (not so much for incomplete types), but also a tortured avoidance of the compiler role (Translation phase 7) in the process, and really the meat of what is going on. I’d recommend someone just read cppreference first.

https://stackoverflow.com/questions/1410563/what-is-the-diff...

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

#97

Post by threeducks »

fearthetelomere wrote: post #95
threeducks wrote: post #69

Earlier quoted context omitted.

> I recently developed a new data structure Congratulations, you have discovered the array deque! https://en.wikipedia.org/wiki/Double-ended_queue#Implementat... I'd like to point out a performance optimization. On resize, you create a new array with double the size and copy all the old elements to the middle of the new array with more space at the beginning AND at the end: https://github.com/attilatorda/Shift-To-Mid…

>- 2 is not the best growth factor because it makes it harder for the memory allocator to reuse memory. More modern implementations use smaller growth factors: https://en.wikipedia.org/wiki/Dynamic_array#Growth_factor I've often wondered about this, so I'm curious to learn more. I agree in principle we should be more clever to ensure we have better memory use. However, half the implementations in the list you've link…

> Do you know why these implementations opt for 2 if it's not the best choice?

Probably a mix of simplicity, not knowing or not caring. Most software is not optimal.

> If it's not the best, what is?

In theory, the best value is a bit less than the golden ratio, so 1.5 is quite good.

https://archive.li/Z2R8w#selection-119.7-135.119

In practice, unknown factors can influence the result, so it is best to benchmark your code and try a bunch of values until you find the fastest configuration.

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

#99

Post by theamk »

I don't see why I would use it over `std::deque`. It has all the same complexity properties, but better tested, included in stdlib, and supports complex objects. It even has OK cache locality, given it allocates data in large-ish blocks.

You should really include this in you summary table, because it'd have all the same values compared to shift-to-middle array.

And your benchmark confirm this: figure 3 does not show the raw data, but it looks like std::queue may be 8-10% slower on smaller data sizes, and 1-2% slower on larger data sizes. Such small and inconsistent differences do not indicate different O()-complexity, and likely very dependent on specific benchmark design.

Related: std::deque implementation details for various compilers: https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=10...

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

#100

Post by jtrueb »

Since I often use a sliding window, I made a Rust implementation and was surprised with how performant the VecDeque implementation was.

The MidVec was only faster than VecDeque when doing batch inserts and removals with my implementation.

https://gist.github.com/trueb2/9c0a23aa012f56d4c3d50afe8acf6...

Post reply on HN