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

101–110 of 121 posts

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

#101

Post by SkiFire13 »

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…

The better memory usage argument is not as one sided as it may appear. The issue related to using a growth factor of 2 appear when you have a single very big array, but for many smaller ones it's not really an issue. Meanwhile allocators generally tend to like power of 2 sizes, and non-2 growth factors produce non-power of 2 sizes. Some data structures are also easier to implement when the size is a power of 2 because you can efficiently wrap around by using bitwise operations rather than an expensive remainer.

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

#102

Post by jzwinck »

theamk wrote: post #99

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…

You say deque uses large-ish blocks but you provide documentation that it uses 512 byte blocks on GCC and MSVC is even worse. So if you're on Windows the blocks are so small the container degenerates into something like a std::list, and on non-Windows it only works well if your objects are a few bytes each.

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

#103

Post by dzaima »

threeducks wrote: post #97
fearthetelomere wrote: post #95

Earlier quoted context omitted.

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

That theoretical result of the golden ratio is completely entirely useless for any practical scenario, and, even for its extremely-contrived scenario where the only allocations ever happening are from a single array being expanded, and using an extremely dumb allocator, it's just optimizing memory usage, not performance.

Amusingly, it looks at Java, which typically uses pointer bumping for the allocator and can do compacting GC, making the argument entirely meaningless.

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

#104

Post by theamk »

jzwinck wrote: post #102
theamk wrote: post #99

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…

You say deque uses large-ish blocks but you provide documentation that it uses 512 byte blocks on GCC and MSVC is even worse. So if you're on Windows the blocks are so small the container degenerates into something like a std::list, and on non-Windows it only works well if your objects are a few bytes each.

The gcc's 512 byte block is actually not that bad.

For cache locality, you want block size that is bigger that cache line size - and those are 64 to 128 byte range. And as for overhead, it seems like 1 pointer per block, or 1.5% for deque of pointers/integers - not a very big value. So yeah, while linked lists are bad, gcc's deque is pretty OK.

For MSVC, I agree, their std::deque is pretty bad. But the title of the post isn't "a faster deque MSVC", it makes no distinction between OSes.

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

#105

Post by eru »

fc417fc802 wrote: post #64
eru wrote: post #45

Earlier quoted context omitted.

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

Is fork really the problem in this scenario?

I don't think it's the main problem here, but it's just another point where the fork/exec model shows its problems.

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

#106

Post by dzaima »

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…

Volatile stores would fix that issue. But it does mean that it'd be unsafe to lend out mutable references to objects. (maybe you'd need to do volatile loads too, depending on model of volatility)

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

#107

Post by dzaima »

scottlamb wrote: post #91
leiroigh wrote: post #74

Earlier quoted context omitted.

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

Rust doesn't help here; you necessarily must do all stores in potentially-mirrored memory as volatile (and possibly loads too), else you can have arbitrary spooky-action-at-a-distance issues, as, regardless of &[T] vs &mut [T] or whatever language-level aliasing features, if the compiler can see that two addresses are different (which they "definitely" are if the compiler, for one reason or another, knows that they're exactly 4096 bytes apart) it can arbitrarily reorder them, messing your ring buffer up. (and yes it can do so moving ops out of language-level lifetimes as the compiler knows that that should be safe)

vmcircbuf just exposes the mutable mirrored reference, resulting in [1] in release builds. Obvious issue, but, as my example never uses multiple references with overlapping lifetimes of any form, the issue would not be fixed by any form of more proper reference exposing; it's just simply the general issue of referencing to the same data in multiple ways.

vmap afaict only exposes push-back and pop-front for mutation, so unfortunately I think the distance to cross to achieve spooky action in practice is too far (need to do a whole lap around the buffer to write to the same byte twice; and critical methods aren't inlined so nothing to get the optimizer to mess with), but it still should technically be UB.

slice_deque has many open issues about unsoundness. magic-ring-buffer doesn't build on modern rust.

[1]: https://dzaima.github.io/paste/#0TVDBTsQgFLz3K56XbptsWlo1MWz...

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

#108

Post by masklinn »

SkiFire13 wrote: post #101
fearthetelomere wrote: post #95

Earlier quoted context omitted.

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

The better memory usage argument is not as one sided as it may appear. The issue related to using a growth factor of 2 appear when you have a single very big array, but for many smaller ones it's not really an issue. Meanwhile allocators generally tend to like power of 2 sizes, and non-2 growth factors produce non-power of 2 sizes. Some data structures are also easier to implement when the size is a power of 2 becaus…

> The issue related to using a growth factor of 2 appear when you have a single very big array

And a linear coalescing allocator of which that collection is essentially the only user.

That is, the allocator needs to be a single bytes array, and it needs to be able to reuse and merge freed allocations, and there can’t be other objects being allocated between your collection’s allocations (or they need to be freed before your collection needs to realloc).

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

#109

Post by gpderetta »

tialaramex wrote: post #31
dehrmann wrote: post #17

Earlier quoted context omitted.

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

> the C++ std::deque is something which you wouldn't invent today,

Why is that?

My major issue with std::deque is that the standard implementation doesn't provide a) a way to define the block size, b) a way to access the single blocks for optimizations. The deque in boost.container provides the former. I don't know if any widely available implementation provides the latter (segmented iterators were first proposed around the original C++ standardization, but it seems that were never picked up).

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

#110

Post by gpderetta »

MattPalmer1086 wrote: post #65
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…

Really interesting, I love new ideas for data structures. One little note about benchmarking though. It's hard to get good benchmark data, particularly in Java due to the JIT compiler. At the very least, you should perform a large number of warmups (e.g. 10000 calls to the code) before actually benchmarking to ensure all code is fully compiled by the JIT. That's only one of the gotchas though. Even better, use a dedi…

There is no JIT in a typical C++ implementation. The first run might be an outlier due to warming up multiple caches, but it can be obviated with a large enough run. Runtime should be relatively stable for synthetic benchmarks.
Post reply on HN