Implementing my own Vec, what is alignment (and coveriance)

help
1

For my own understanding, I'm implementing a fixed-size ring buffer (the one from exercism) using raw pointers. My questions:

  1. Can I use NonNull? It mentions covariance, but I don't really know what that means.
  2. How do I create my Layout? Do I use size.next_power_of_two() and leave padding between my elements, or do I set the alignment to something else and just use ptr::write_unaligned et. al.? What is alignment?
  3. Ok 'what is alignment?' is my third question :slight_smile:

I've looked at the nomicron, but it uses unstable apis rather than std::alloc (in its Vec example).

2

What is the advantage over VecDeque?

https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/vec_deque.rs#L1269
https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/vec_deque.rs#L1223

3

Covariant, Contravariant, and Invariant are defined as follows:

  • Covariant with respect to a type T, U, and V means if U : V then T<U> : T<V>. In other words, if type U is a sub-type/extends a type V then, the type T<U> constructed from the Generic type T is a sub-type/extends T<V>. Mnemonic: CO-variant, means it varies in COordination with the contained type.
  • Contravariant with respect to type T, U, and V means if U : V then T<V> : T<U>. In other words, uf type U is a sub-type/extends type V, then the type T<V> is a sub-type of/extends the type T<U>. CONTRAvariant means the sub-type relationship between T<U> and T<V> is CONTRAry (opposite) to the sub-type/extends relationship of the types U and V.
  • Invariant means that just because U : V neither T<U> : T<V> nor does T<V> : T<U>. This means that no matter the sub-type/extends relationship between the contained types, the types T<V> and T<U> do not extend/sub-type each other in any way.

Alignment refers to the requirement that certain types (like i32 or i16) be aligned along certain memory intervals on a particular CPU. For example, i16 must be aligned on and address where the least significant byte is 0. Each type in Rust has a particular required alignment on a particular CPU architecture. The alignment is part of the type. You can't guess it. You have to use the alignment for the particular type you are attempting to layout into an array or otherwise in memory.

5 Likes
4

Vec should be covariant.

The short of it is that 99% of types should be covariant, assuming they hold data of type T. The major exception is that types which allow writing (&mut and types with interior mutability) should be invariant. See Subtyping and Variance - The Rustonomicon.

When uncertain, however, invariance is the safest choice. (I.e. it is never a dangerous choice)

4 Likes
5

To get the alignment for a type T, you can use mem::align_of::<T>().

3 Likes
6

The above will give you the layout for the T you intend to store - that’ll have the size and alignment, as well. Be careful with ZSTs - depending on how you write the (unsafe) code, you may need to handle them specially. Studying Vec’s impl probably wouldn’t hurt :slight_smile:

3 Likes
7

This is a learning exercise.

1 Like
8

Great answer, thankyou!

What does it mean for a type U to extend a type V? Does it mean, for example,

  1. &'a str extends &'static str because a the 'static lifetime contains the lifetime 'a?
  2. An enum with #[repr(u8)] extends u8 since all valid variants are u8, but not all u8s are enum variants?

So I'm asking is a subtype a more specific type? Or is it something else?

I'm now reading the nomicron on subtyping - don't know why I missed it before.

2 Likes
9

I feel like I really am getting a feel for both these concepts having read the nomicron. I have one more question:

There are other places in the rust language that could use the concept of variance. For example (as in the bit I crossed out), a #[repr(u8)] enum could be used in place of a u8, as it is a more specific type. Was it just decided that it would be confusing to allow this?

1 Like
10

For a type to be a sub-type it must fulfill the Lishkov Substitution Principle which means that if T is a sub-type of U then anywhere I need a U if you give me a T that will suffice. Now, let's apply this principle to your #[repr(u8)] enum. If I say I need a u8, will a your enum suffice? If your enum only defines the values: 0, 1, 2, 3? A u8 can hold any value 0-255, right? But the enum only encocdes validly 0, 1, 2, 3? Does that honor the LSP? No. That is why.

1 Like