Large BTreeMap key or value types cause avoidable stack overflow

[ssomers]

I tried this code:

use std::collections::BTreeSet;

fn main() {
    let mut s = BTreeSet::new();
    s.insert([0u8; 19580]);
}

built with plain rustc on 64 bit Windows (it happens in release code too but not with this example).
I expected to see the program finishing silently.

Instead, this happened:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted

This becomes sporadic if you decrease the size of the key and disappears below 19540 bytes (on my system).

On my Linux box, and on playground, the size can be increased to somewhere between 160_000 and 170_000 bytes before the stack overflows.

rustc --version --verbose:

rustc 1.51.0-nightly (d1aed50ab 2021-01-26)
binary: rustc
commit-hash: d1aed50ab81df3140977c610c5a7d00f36dc519f
commit-date: 2021-01-26
host: x86_64-unknown-linux-gnu
release: 1.51.0-nightly
LLVM version: 11.0.1

This is not necessarily a bug, since there has to be some system-dependent limit. And it's not smart to inline big chunks of data as key or value, because usually about half of the key-value space allocated by BTreeMap remains unused. But the limit on Windows is much lower than I expected (and before #81494 can apparently easily be lifted improved by using box instead of Box::new for the construction of btree nodes).

[ssomers]

That was for the key type, the value type has a little more leeway. With slightly modified code to avoid the missing Ord requirement on the key in previous versions of Rust:

use std::collections::BTreeMap;

fn main() {
    let mut s = BTreeMap::new();
    s.insert((), [0u8; 37600]);
}

the limit for the value type in Rust 1.30, 1.32 and 1.33 is somewhere between 37,600 and 37,700. Since Rust 1.34, it has dropped to somewhere between 20,700 and 20,800.

[ssomers]

can apparently easily be lifted by using box instead of Box::new for the construction of btree nodes.

Not to the Rust 1.33 level. It merely increases the size limit from about 20,700 to about 26,600.

[cuviper]

This seems like a specific instance of the general "placement new" problem, #27779. Semantically, the values are created locally on the stack and then moved into the map node. Sometimes optimization could be smart enough to skip the local, but there's no guarantee of this, and debug builds are out of luck.

The creation of the node is more directly concerning though, being a multiple of the key-value size. We have more control to avoid that ever hitting the stack if they would use Box::new_uninit and initialize it in place.

[ilyvion]

I'm a bit confused. This code overflows the stack on stable, but not beta or nightly on the playground:

use std::collections::BTreeMap;

fn main() {
    let x: [u16; 32768 * 4] = [0; 32768 * 4];
    let mut bm = BTreeMap::new();
    bm.insert(0, x);
}

Not overflowing on beta means that whatever fixes this will be in the next stable release, right? But I'm not seeing any activity on this issue since May of last year, so I'm confused.

[ssomers]

I don't actually see that behaviour on your playground example; instead, all release builds succeed and all debug builds overflow. Maybe playground assigns different platforms depending on karma.

I do see it with my value example on my own Windows machine: maximum value size has increased from about 37600 26000 to about 63500, way past the 37600 limit that Rust 1.33 upheld. Zooming in on nightly builds, this improvement happened in nightly-2022-03-21, i.e. in one of the auto merges c84f39e 4767cce 9bd5371 c7ce69f 3b84829 499d4a5 183090f f2661cf.

Which includes the very much related #92962, but I'm stumped whether and how this would have reduced stack usage. Sure, the allocation on the heap is postponed a little, but why would the stack care? If the BTreeMap::entry function would not get inlined, there's one less call stack frame when the heap allocation happens. That stack frame contains an Entry return value, with space for a few small, fixed size pointers and indices, and the key! …but the key is zero-sized in my value example.

[ilyvion]

I don't know what to tell you except I'm finding this to be very reproducible.

[ssomers]

You're right, I must have bungled up the first time.

I was also focusing on release builds but my command-line tests are debug too. Let's make sure of one thing: in release builds, in my example, the same nightly-2022-03-21 increased the value type size limit from about 150k to 350k.

I put the same example as a test in frank's branch, e,g.

#[test]
fn pain() {
    let mut s = std::collections::BTreeMap::new();
    s.insert((), [0u8; 500_000]);
}

That confirms that it's really #92962 that somehow resolved the stack issue. Besides the question how, another mystery is that the numbers are considerably higher than 350k, whether the example is internal or external (built inside or outside the alloc module). I'm classifying that as if x.py test --stage 0 builds or runs things differently than cargo run --release does.

[ssomers]

#92962 obviously made all the above examples special: they insert into a fresh, treeless map. If we let them insert a second time, into a then "genuine" map, then instead of improving matters, we have the original regression problem: something works fine in stable (playground) but fails on beta and nightly.