Large structs constructed on stack

[mark-i-m]

I am trying to use StdRng in a no_std context where the stack is rather small. I found that the stack is overflowed when the RNG is constructed.

Basically, rand_core::SeedableRng::seed_from_u64 calls <rand::rngs::std::StdRng as rand_core::SeedableRng>::from_seed, which calls <rand_hc::hc128::Hc128Rng as rand_core::SeedableRng>::from_seed, which calls BlockRng::<Hc128Core>::from_seed ... etc

And each of these allocates a huge amount of space on the stack for the return value, which leads to a stack overflow. I imagine it is also quite slow on a normal platform too, since a lot of values will be copied on the stack.

TBH, I'm not really sure what the solution is. It seems like allocating the RNG on the heap is the right way to avoid all of this copying on the stack. On the other, perhaps marking some of the constructors #[inline(always)] would solve the problem?

[vks]

This will hopefully get better once we release Rand 0.7, which uses ChaCha20 for StdRng, requiring much less memory than HC128 (see the Rand book). For now, I have the following suggestions:

1. Try using rand_chacha::ChaChaRng.
2. Try using Box<StdRng>. However, I'm not sure whether this avoids the stack allocation.
3. Consider using a RNG that is not cryptographically secure but has a tiny state, see rand::SmallRng, rand_xoshiro and rand_pcg.

[burdges]

We should add some #[inline(always)] lines or similar, probably in BlockRng, but..

Reusing stack space tightly sounds vital CPU cache performance. Yet, Rust code often returns large structures on the stack. We've RFCs for returning DSTs and VLAs that encourage this. We'll gain const generics this year, which should make methods like fn foo<const u: usize>(...) -> [T; n] common place.

I'd therefore consider this an ABI bug or code generation bug in rustc. I'd expect the caller to pass the called method a pointer to memory where it may construct the returned type, but even if it simply returned the value on the stack, then you'd double, or quadruple in this case, you cache efficiency by doing an overlaping copy instead of the non-overlaping copy they obviously do.

Can you create an issue on https://github.com/rust-lang/rust/ ?

[dhardy]

We should add some #[inline(always)] lines or similar, probably in BlockRng, but..

Agreed; I'll add to #815.

Without testing the full application, I can only guess where these will be most effective however.

[burdges]

OT: Is there any "hot spot" analyzer for rust code? Or LLVM? You'd put tests into it and it identifies better inlining or whatever?

[dhardy]

Don't know. @burdges would you take a quick look at the last commit in #815? After I get a review I'll make the release (yes, it's largely guess-work at this point).

[burdges]

There are no BlockRngCore for .. appears in that diff, so maybe they were already marked #[inline(...)]? It's those that really need inlining I'd think, unless they're big maybe. And some inherent methods on BlockRng*. Is their already inlined then rustc ignore the directives. I've heard of that happening.

I've no idea about inlining methods from impl<R: BlockRngCore<Item=u32>> RngCore for BlockRng<R> myself.

[dhardy]

The BlockRngCore implementations tend to be the big ones; I inlined everything else (some with always and some without). Since all of these are pure or nearly-pure wrappers I think this is okay.

At any rate, benchmarks are either a little better or similar, so I think this is going in the right direction.

[mark-i-m]

Thanks all! That was a swift response!

I agree that the best solution would be some sort of language support (e.g. move elision/optimization or emplacement construction), but that doesn't seem to be a near-term thing, and I think it is already a recognized problem (e.g. there have been emplacement RFCs, and this, and others).

@vks Thanks for the suggestions

Try using rand_chacha::ChaChaRng

I will give that a try. I will also try after the release and see...

Try using Box. However, I'm not sure whether this avoids the stack allocation.

This doesn't solve the problem because the struct is created on the stack first, and then copied to the heap.

Consider using a RNG that is not cryptographically secure but has a tiny state, see rand::SmallRng, rand_xoshiro and rand_pcg

Unfortunately, I need a crypto RNG :/

[vks]

Unfortunately, I need a crypto RNG :/

ChaCha only needs 136 bytes, so it hopefully works for you. We could probably use the Gimli permutation as a RNG, which only has 48 bytes of state, but this is not yet implemented.

[burdges]

It's an interesting point that box Something::new() with Something large enough should be optimized to allocate before invoking new, but then box Something::new()? gets tricky, so maybe new(..) -> Something should be optimized to new<F>(.., f: F) -> Result<Something,..> where F: unsafe FnOnce(..) -> *mut Something.. tricky. And those DST discussion you link would basically turn fns into Generators.. very tricky.

[dhardy]

Good point @burdges but somewhat off-topic. #[inline] on constructors should help work around this.

I'll make those releases...