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

111–120 of 121 posts

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

#111

Post by gpderetta »

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…

IIRC libstdc++ benchmarked the golden ratio and found it worse for the loads they were interested in, so they stuck with a growth factor of 2.

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

#112

Post by gpderetta »

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…

On linux you can use remap_file_pages[1] to setup your magic ring buffer. Yes, these days it is emulated in the kernel, but here we only care about setting up the expected duplicated mapping of anon pages instead of minimizing the allocations of VMAs.

Also linux has MADV_DONTFORK, would that allay your concerns? (there is a potential race between mmap and the madvice call, but if you are forking in a multithreaded program you have worse concerns).

[1] https://man7.org/linux/man-pages/man2/remap_file_pages.2.htm...

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

#113

Post by gpderetta »

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…

This is normally called a magic ring buffer, and it is a relatively well known pattern. Very useful for queues when you need to support variable size elements and need to interoperate with code that can't handle split objects.

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

#114

Post by leiroigh »

dzaima wrote: post #107
scottlamb wrote: post #91

Earlier quoted context omitted.

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

>so unfortunately

I see a fellow enjoyer of bugs ;)

>vmap afaict only exposes push-back and pop-front for mutation

what about https://doc.rust-lang.org/nightly/std/io/trait.Write.html#ty... ?

>and critical methods aren't inlined

aren't inlined explicitly. This does not mean that they are not inlined in practice (depending on build options). Also, LLVM can look inside a noinline available method body for alias analysis :(

This is a big pain whenever one wants to do formally-UB shennenigans. I'm not a rustacean, but in julia a @noinline directive will simply tell LLVM not to inline, but won't hide the method body from LLVM's alias analysis. For that, one needs to do something similar to dynamic linking, with the implied performance impact (the equivalent of non-LTO static linking doesn't exist in julia).

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

#115

Post by dzaima »

leiroigh wrote: post #114
dzaima wrote: post #107

Earlier quoted context omitted.

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

>so unfortunately I see a fellow enjoyer of bugs ;) >vmap afaict only exposes push-back and pop-front for mutation what about https://doc.rust-lang.org/nightly/std/io/trait.Write.html#ty... ? >and critical methods aren't inlined aren't inlined explicitly. This does not mean that they are not inlined in practice (depending on build options). Also, LLVM can look inside a noinline available method body for alias analysi…

> I see a fellow enjoyer of bugs ;)

Yep! :)

I did look at the assembly on a release build and the write method was in fact not inlined (needed to get the compiler to reason about the offset aliasing); that write method is what I called "push-back" there. I could've modified the crate to force-inline, but that's, like, effort, just to make a trivially-true assertion for one HN post.

Indeed a lack of an equivalent of gcc's __attribute__((noipa)) is rather annoying with clang (there are like at least 4 issues and 2 lengthy discussions around llvm, plus one person a week ago having asked about it in the llvm discord, but so far nothing has happened); another obvious problem being trying to do benchmarking.

(for reference, what I was trying to get to happen was an equivalent of https://godbolt.org/z/jobs6M95G)

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

#116

Post by MattPalmer1086 »

gpderetta wrote: post #110
MattPalmer1086 wrote: post #65

Earlier quoted context omitted.

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.

There is a Java implementation as well with benchmarks. But yes, C++ has no JIT, although doing some warm up is also advised for benchmarking in general.

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

#117

Post by fc417fc802 »

eru wrote: post #105
fc417fc802 wrote: post #64

Earlier quoted context omitted.

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.

What would you replace fork with? I don't get it.

Isn't the desired improvement here to how the kernel handles the lifetime of mappings? It seems orthogonal to me.

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

#118

Post by scottlamb »

dzaima wrote: post #107
scottlamb wrote: post #91

Earlier quoted context omitted.

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

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

Hmm, as I think about it, I see your point about LLVM's optimizer potentially "knowing" memory hasn't changed that really has if it inlines enough even if it's never put into the same &mut [T] as the other side of the mirror (and two improperly aliased &mut [T] are never constructed).

But as an alternative to doing all the stores in a special way (and loads...don't see how doing a volatile store to one side of the mirror is even sufficient to tell it the other side of the mirror has changed)...it'd be far more practical if the caller could use a (not mirrored) &mut [T]. Couldn't you have an std::ops::IndexMut wrapper that returns a guard that has a DerefMut into &mut [T] and on Drop creates a barrier for these kinds of optimizations via `std::arch::asm!("")`? [1] Then LLVM has to assume all memory changed in that barrier.

Regarding the more specific crate issues: I found these crates a while ago and hadn't looked extensively in their implementation. Thanks for pointing these out; I will have to look more closely if/when I ever decide to actually use this approach. I was leaning toward no anyway because of the other factors I mentioned. As an alternative, I was thinking of having a ring buffer + a little extra bit at the end that is explicitly copied from the start as needed. The maximum length of one message I need a contiguous view of is far less than the total buffer size, so only a fraction of the buffer would need to be copied.

> vmcircbuf just exposes the mutable mirrored reference, resulting in [1] in release builds.

Yuck, noted, clearly wrong to give the whole thing as a `&mut [T]`.

> slice_deque has many open issues about unsoundness.

I see at least couple of those, which seem to be "just" the usual unsafe-done-wrong sorts of things (double frees) rather than anything inherent to the mirrored buffer.

[1] https://stackoverflow.com/questions/72823056/how-to-build-a-...

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

#119

Post by dzaima »

scottlamb wrote: post #118
dzaima wrote: post #107

Earlier quoted context omitted.

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

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

Yeah, an asm marked as memory-clobbering is the proper thing; not the first time I've forgotten that volatile entirely doesn't imply anything to other memory. (in fact, doing "((volatile uint8_t*)x)[0] = 0xaa;" in my godbolt link in a sibling thread still has the optimization happen). Don't know how exactly it interacts with aliasing rules; maybe you'd have to explicitly pass the mutable reference to the asm as an input, otherwise it'd be illegal for the asm to change it and so the compiler can still assume it isn't? or, I guess, not have any references live during the asm call is the proper thing.

Probably indeed possible to do it with proper guards (the pre-pooping your pants issue is probably not a problem if you also have the asm guard in drop?).

> I see at least couple of those, which seem to be "just" the usual unsafe-done-wrong sorts of things (double frees) rather than anything inherent to the mirrored buffer.

Yeah, possible. I was just saying that from the perspective of proving that all the ring buffers not taking extreme care are incorrectly implemented.

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

#120

Post by scottlamb »

dzaima wrote: post #119
scottlamb wrote: post #118

Earlier quoted context omitted.

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

Yeah, an asm marked as memory-clobbering is the proper thing; not the first time I've forgotten that volatile entirely doesn't imply anything to other memory. (in fact, doing "((volatile uint8_t*)x)[0] = 0xaa;" in my godbolt link in a sibling thread still has the optimization happen). Don't know how exactly it interacts with aliasing rules; maybe you'd have to explicitly pass the mutable reference to the asm as an in…

> Don't know how exactly it interacts with aliasing rules; maybe you'd have to explicitly pass the mutable reference to the asm as an input, otherwise it'd be illegal for the asm to change it and so the compiler can still assume it isn't? or, I guess, not have any references live during the asm call is the proper thing.

I don't know either, but really it's the opposite half of the buffer you want to tell it may have changed, so I imagine it doesn't matter even if you still have the `&mut [T]` live.

Maybe the extra guard I described isn't necessary either; the DerefMut could directly return `&mut [T]` but set a `barrier_before_next_access` on the ring, or you could just always have the barrier, whatever performs best I guess.

Post reply on HN