"array lengths can't depend on generic parameters" with const generics... bug or expected behavior?

MaybeUninit::<[T; N]>::uninit().assume_init()

MaybeUninit::<[MaybeUninit<T>; N]>::uninit().assume_init()

The first claims to construct N values of type T. Uninitialized data might not be valid for T.

The second claims to construct N values of type MaybeUninit<T>. This type is obviously allowed to be uninitialized.

Because of niches. Niches are values where T is not defined. For example, references (&_) are never null. MaybeUninit<_> is a niche killer, it has none of the niches as T. This means that MaybeUninit<&_> can be null! Moreover, all references &_ are marked dereferenceable by Rust in LLVM. This means that LLVM is allowed to add in reads to all references, even if there were no reads in the source code.

In particular,

let x = &[] as &[_];

llvm is allowed to insert a read like so if it thinks it will improve performance.

let x = &[] as &[_];

&*x;

Now given that &[_] implements Default (gives you a slice of size 0), and &[_] is Copy, because all shared references are Copy, it can be used with your type. But if you do MaybeUninit::assume_init(MaybeUninit::<[T; N]>::uninit()) you have constructed a uninitialized value of type &[_]. Now, if LLVM decides that it wants to read that reference, it will insert a read. Now because your reference is uninitialized it could be null, LLVM has just inserted a dereference to a possibly null pointer!

Compare this to my version,

let mut data: [MaybeUninit<T>; N] = unsafe {
    MaybeUninit::uninit().assume_init()
};

LLVM then sees that MaybeUninit and knows that it can't just dereference the references inside, because they may not yet be initialized. So it won't add these spurious reads.


Now, I have used spurious reads as an example, but I will stress, this is just an example and even types that don't have niches like u8 should never be uninitialized on it's own. If you are going to deal with uninitialized memory, the only safe and stable way to do so is through MaybeUninit.

2 Likes

Well, I'd rather not deal with it honestly. Thanks for the info, however.

That said, looking at your version again made me realize I can actually do something much closer to what I originally wanted, even if it doesn't work directly in the initializer right now:

impl<T: Copy + Default, const N: usize> StaticVec<T, {N}> {
    fn new() -> Self {
        let def = T::default();
        let mut _data: [T; N] = [def; N];
        Self {
            data: _data,
            length: 0,
        }
    }
}

Edit: Forgot the Default bounds.

Huh, that doesn't work on playground, strange

Dang it, you're right, that still doesn't work. I'm curious as to whether this is a technical limitation or an artificial one from before const generics existed, though. Time to go looking at the compiler sources I guess.

Miri isn't perfect yet, so it will miss some UB. Also, you clearly didn't read what I said about uninitialized niches being instant UB. f32 doesn't have any niches. If you use references you will see MIRI complain even with the loop.

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=4efa68331ab8d8fd35d6e5eefbcc83f3

The best thing would be to have std::mem::transmute work with const-generics, but it doesn't. You could also usestd::mem::transmute_copy, but that is frowned upon with pointer casts being seen as the better alternative. This is why I used pointer casts.

Dealing with uninitialized memory is hard, and a source of bugs in C and C++, so Rust tries to provide a safe abstraction. This is hard to do and should not be taken lightly. If you do not want to deal with this directly, then you can use my crate that I linked earlier, array-vec, and I will take care of the uninitialized memory for you.


MaybeUninit is a round about way to do the obvious thing, but it serves as a way to turn off optimizations that would otherwise be invalid. In the very same way that UnsafeCell is a roundabout way to do shared mutation, trying to do the obvious thing (transmuting a &T to a &mut T) is instant UB, so you must go through an UnsafeCell to turn off optimizations and do the right thing without UB. But even with UnsafeCell you can still cause UB if used incorrectly (creating aliasing unique references (&mut T)). But in order to cause UB, you must go through unsafe somewhere along the way.

In the same way, if you try and do the obvious thing (std::mem::uninitialized() or similar) you may cause instant UB (using uninitialized niches, like null references). So you must go through MaybeUninit to turn off such optimizations and to do the right thing without UB. But even with MaybeUninit you can still cause UB if used incorrectly (creating an uninitialized T from a MaybeUninit<T> esp. if T has niches). But in order to cause UB, you must go through unsafe somewhere along the way.


You can't always have safety, ease of programming and speed at the same time. In this case Rust chose to sacrifice ease of programming to achieve the other two.

2 Likes

So I've been continuing to play around with a bunch of different ways to implement my StaticVec struct, and it's going ok (despite definitely unavoidably requiring more unsafe than I originally anticipated / wanted).

However, one thing that's stumping me is that there does not seem to be an existing way to access an element of a [MaybeUninit<T>; N] (which is what I'm using now) that both avoids the runtime bounds check (which I don't want as I'm already checking the specific values I care about in my own code) and also avoids Miri evaluation errors when I run it (which I've been told is the best way to check for UB.)

Here's a playground link that simplifies the issue.

Any additional advice anyone has would be very appreciated!

The playground link isn't a permalink.

Woops, thanks, fixed it.

I'll note that you're initializing the wrong element, though that doesn't seem to be the issue.

Here's the methods you want to use:

a.get_unchecked_mut(11).write(&12.3);
println!("{}", a.get_unchecked(11).assume_init());

Documentation

1 Like

I initialized element 11 with the first one and element 10 with the second one on purpose, just for the sake of showing that both validly display "12.3" afterwards.

D'oh! Of course.

Just checked your version and yep, no Miri complaints! I feel silly for not realizing static arrays actually had direct access to all of the "slice" functions (for some reason I thought they weren't quite the same thing.)

Thanks so much!

Huh, it is kind of weird, come to think of it. Arrays don't implement Deref so this can't be explained by auto-deref. And even though [T; n] implements Unsize<[T]>, that usually only permits coercions, not method access. I think it's just built into the language.

I opened this issue to see if they can be added to the docs like they are for types like Vec.

(though even if you couldn't do this, there's plenty of ways to get a slice from an array; &arr[..], or let slice: &[T] = arr.as_ref(), or even let slice: &[T] = &arr due to unsizing coercions)

2 Likes

Great idea! Would certainly probably save dummies like myself some time in the future, haha.

Random unrelated question: Is there anything like an "official benchmark suite" for normal Vec that you're aware of? I'm looking for basically the fairest / most thorough way I can find to compare the performance to what I have so far for my StaticVec.

I'm definitely very impressed by the assembler output I'm seeing for it from rustc regardless, though... the whole thing is consistently inlined "out of existence" in release mode (i.e. there's no actual function calls or direct references to the type, just a long unbroken block of instructions) despite the fact I haven't explicitly marked anything "inline" at all!

#[inline] is mostly a cross-crate concern. LLVM will happily inline things without it if it thinks it worthwhile, and will happily ignore it if it thinks it unnecessary.

Forgot to mention here that I'd "gone public" with this (note: it's not on crates.io yet, but I'll add it there too sometime soon.)

Thanks again to everyone who helped me out with it! (Not that it's "done" by any means, haha.)

My rule of thumb is "work with raw pointers when using uninitialized data". Don't take any references or call "assume_init" until all data has definitely been initialized.

Are you referring to something specific, or just speaking generally? I never actually call assume_init on anything except in one place (on the backing array of MaybeUninit<T> instances in my new() function.)