Stream: t-compiler

Topic: Extremely large statics


Andreas Molzer (Jul 11 2019 at 20:54, on Zulip):

I'm trying to define a gigabyte large static via MaybeUninit::uninit() which leads to extreme memory usage and long compilation times in rustc (1GB array ~ 20GB memory) Similarly when declaring such a large static array. Somewhat understadable. But is there a way and would it be interesting to not make it do that?
Note that the resulting binary is in fact very small, at least for elf, and whatever ld gets poses no problem to it (ld finishes extremely fast). The result binary merely contains a symbol for which the program loader needs to allocate memory, it does not contain the gigabytes of zeroed/uninitialized data. I wanted to utilize this trick for tricking a bootloader into allocating static memory for a unikernel without requiring memory management in that unikernel itself (yeah, kind of dirty hack, back to doing the same with ASM/linker script).
Testable code: https://github.com/HeroicKatora/static-alloc/blob/master/tests/huuuuuge.rs
@RalfJ I was told to maybe ping you.

eddyb (Jul 12 2019 at 07:04, on Zulip):

also pinging @oli

eddyb (Jul 12 2019 at 07:05, on Zulip):

I'm pretty sure this has been brought up before, we can probably make accesses slightly more expensive by lazily allocating the data

eddyb (Jul 12 2019 at 07:13, on Zulip):

the undef bitset is 1/8 the size, but I guess that could also be lazy in the same way

oli (Jul 12 2019 at 11:49, on Zulip):

All zeros or all undef is easy, if everyone is OK with adding optimizations for these special cases I can write mentoring instructions

oli (Jul 12 2019 at 11:49, on Zulip):

I just always gave up when thinking about sparsely initialized statics

Andreas Molzer (Jul 12 2019 at 12:59, on Zulip):

All undef would be sufficient. And it's more consistently justifiable instead of all zeroes where it might be more surprising why to allow exactly that case and not other repeating constant arrays like [1; 1 << 30]. Also, would that entail being able to [(0, 0); 1 << 30]? Maybe better to stick to undef for the moment. Maybe you can give a different view with insights from the compiler implementatino?
If the mentoring instructions make it seem reasonably small and contained, I could maybe try to implement it also.

oli (Jul 12 2019 at 13:07, on Zulip):

I believe that it would suffice to move the bytes and the undefmask fields of Allocation into a custom Struct and add a field of that new type to Allocation. Then once everything compiles again, make a separate commit that makes that field an Option. This will require some changes, most notably in librustc_mir/interpret. Any writes should init the option any reads should emit an undef read error if None

Andreas Molzer (Jul 12 2019 at 13:31, on Zulip):

That sound pretty clear cut, I'll see what I can do :+1:

nikomatsakis (Jul 12 2019 at 14:04, on Zulip):

(seems like all undef and all zeroes are going to be pretty common to me, so I would be :+1: to special casing them for now)

Andreas Molzer (Jul 12 2019 at 20:11, on Zulip):

Problematically, there seem to be get calls that expect being able to access the bytes despite undef. In particlar, copy_repeatedly in memory seems to be ok with that and even has an unsafe block depending on getting a byte-slice of correct length back. And read_c_str also tries to access the bytes directly before ensuring they are defined. Not sure what would break if it were to check beforehand.

Andreas Molzer (Jul 12 2019 at 20:30, on Zulip):

My idea would be to introduce an enum BytesOrUndef<'a> { Bytes(&'a[u8]), Undef } to differentiate between these two situations where that difference is of interest. Not sure what to do with all direct accesses though. Should I post this as PR for tracking and for more comments etc?

oli (Jul 13 2019 at 06:04, on Zulip):

Oh right. read_c_str can just be changed, but copy repeatedly should just not do anything if there are no defined bytes, so get can return None imo

oli (Jul 13 2019 at 06:05, on Zulip):

Yea opening a PR is a good idea

oli (Jul 13 2019 at 06:08, on Zulip):

Or, if you wanna prep for zeroed being special, instead of using an option for get's return type and the field type, use a generic enum like you described, but make the arbitrary data field have a generic value so you can reuse the enum for the field and return type and possibly elsewhere

RalfJ (Jul 13 2019 at 07:45, on Zulip):

@Andreas Molzer @oli with the current infrastructure however, even a 1GB static shouldnt take 20GB of memory... data + undef mask should be more like <2GB, right? Doesn't this indicate we are keeping several needless copies of this data somewhere?

oli (Jul 13 2019 at 07:55, on Zulip):

Well... there may be multiple locals each reserving the needed memory

oli (Jul 13 2019 at 07:56, on Zulip):

But 20gb is excessive

Andreas Molzer (Jul 13 2019 at 12:55, on Zulip):

In that specific initial example it's not a simple static but an uninit static that's being created as part of a wrapping struct with another member. It is running through const-eval shortly.

Andreas Molzer (Jul 13 2019 at 13:01, on Zulip):

It could also be that the usage is from llvm. Is there an existing way that creates an undef version of a complex type in the llvm interface, I only found a special code path for for integer types. Instead the allocated zeroed-bytes are copied from the Allocator directly as a const_bytes?

eddyb (Jul 13 2019 at 13:09, on Zulip):

@oli why Option and not just growing the backing Vecs as needed?

eddyb (Jul 13 2019 at 13:12, on Zulip):

or does too much rely on them being of an exact size?

Andreas Molzer (Jul 13 2019 at 13:13, on Zulip):

@eddyb If there's supposed to be another state for constants, i.e. zeroed, then some wrapper enum is necessary. I tried out both, I had started with growing as needed before the suggestion. It seems several instances index into the vector directly and may get very confused if it is not full length. However, that could be changed as well, growing might also be doable.

eddyb (Jul 13 2019 at 13:15, on Zulip):

okay

Andreas Molzer (Jul 13 2019 at 13:15, on Zulip):

I had to add another size: Size attribute either way to properly track the length of lazy allocation, so .len queries shouldn't be the problem

eddyb (Jul 13 2019 at 13:17, on Zulip):

one kinda cool thing is that you could use this to have uninitialized > 4GB arrays on 32-bit rustc

eddyb (Jul 13 2019 at 13:17, on Zulip):

(by using Size instead of usize)

Andreas Molzer (Jul 13 2019 at 13:18, on Zulip):

Didn't really think of this, but maybe? I'm not sure because even an access into uninit goes through a range check that only handles up to the host architecture length. But that might be rewritten as well.

Andreas Molzer (Jul 13 2019 at 13:19, on Zulip):

It's up here: #62655 (Do links work like that here?)

eddyb (Jul 13 2019 at 13:19, on Zulip):

yeah

Andreas Molzer (Jul 19 2019 at 16:49, on Zulip):

Patch seems to work: Down to 4gb allocated and 1.9gb residual now. The good question is how to best put this into a compile test.

Andreas Molzer (Jul 20 2019 at 00:22, on Zulip):

However, the memory usage of the raw static A: MaybeUninit<[u8; 1 << EXP]> = MaybeUninit::uninit(); is nowhere close to zero. I'm not sure why.

Tom Phinney (Jul 20 2019 at 01:47, on Zulip):

The memory usage of an array of 1 << EXP bytes should be 2<sup>EXP</sup> bytes, whether they've been initialized or not.

Andreas Molzer (Jul 20 2019 at 02:00, on Zulip):

Its about memory usage of such a static in the compiler (that is, within mir) not in the running program. Uninitialized memory has the choice of choosing any value when it is accessed, and hence it is not necessary allocate bytes for keeping track of a current value.

oli (Jul 20 2019 at 06:15, on Zulip):

@Andreas Molzer you can try panicking if an allocation is done that is larger than EXP and then compile your program and backtrace the panic

oli (Jul 20 2019 at 06:16, on Zulip):

Must be bigger than anything from libcore/libstd otherwise you can't get to your test

Andreas Molzer (Jul 20 2019 at 13:40, on Zulip):

I think the answer might just be 'somewhere in llvm'. I've tried to add a panic and it didn't trigger.

Andreas Molzer (Jul 20 2019 at 13:41, on Zulip):

Being able to compile with usage of a static MaybeUninit<[u8; 30]> (raw and in in a const function) is already a major win so I wouldn't worry too much.

Andreas Molzer (Jul 20 2019 at 14:00, on Zulip):

Running the slightly less ridiculous [u8; 1 << 34] works fine until I hit: LLVM ERROR: out of memory

Andreas Molzer (Jul 24 2019 at 07:52, on Zulip):

@oli Can I get another review? I'm done with the main work on mir and llvm, but there are apparently two target-specific workarounds that depend on the byte representation and for which I am not completely sure on how to adjust them.

oli (Jul 24 2019 at 11:18, on Zulip):

we can always default to the previous behaviour irrelevant of the memory usage and correctness of the previous behaviour for these targets

Andreas Molzer (Jul 24 2019 at 12:04, on Zulip):

The wasm code requires a pointer, probably to a region of the allocation length. Since we can't simply allocate into the &Allocation (requires mutable) I'm just unsure if an entirely new allocation (vec![0; length]) would also suffice or if it requires a lifetime beyond the pointer use.

oli (Jul 24 2019 at 12:10, on Zulip):

I don't think it requires a lifetime longer than the function call

oli (Jul 24 2019 at 12:10, on Zulip):

this is one of the places where the duplication comes from

Last update: Nov 16 2019 at 01:00UTC