Use `NonMaxU32` instead of `u32` as a length container to reduce `Option<ArrayVec>` size.

[A1-Triard]

Storing the length as NonMaxU32 would allow compiler to optimize Option<ArrayVec> size by storing None as impossible length value (u32::MAX).

[bluss]

Sounds useful. We'd like to store the length even smaller (i.e smaller type informed by the compile time size of capacity) - and that shrinkage has higher priority - but it might not yet be possible.

[c410-f3r]

ArrayVec<T, const N: usize, S: Size = u16> { ... }

trait Size {}
impl Size for u8 {}
impl Size for u16 {}
impl Size for u32 {}
impl Size for u64 {}
impl Size for usize {}

In my opinion, it is impossible to introduce such flexibility without adding yet another type.

[A1-Triard]

In my opinion, it is impossible to introduce such flexibility without adding yet another type.

I believe, it will be possible when generic constants will be allowed in constant expressions.

[c410-f3r]

In my opinion, it is impossible to introduce such flexibility without adding yet another type.

I believe, it will be possible when generic constants will be allowed in constant expressions.

Out of curiosity. How?

[A1-Triard]

Out of curiosity. How?

Using len: [u8; LEN_BYTES], and the hope that the compiler will optimize this «short long arithmetic».

[c410-f3r]

ArrayVec<T, const N: usize, const LEN_BYTES: usize> {
   data: [MaybeUninit<T>; N],
   len: [u8; LEN_BYTES],
}

Perhaps I am missing something but LEN_BYTES must also come from an user-defined type.

[A1-Triard]

Perhaps I am missing something but LEN_BYTES must also come from a user-defined type.

const fn log_2_ceiling(n_minus_one: usize) -> usize {
    let mut r = 0;
    while n_minus_one >> r != 0 {
        r += 1
    }
    r
}

struct ArrayVec<T, const N: usize> {
   data: [MaybeUninit<T>; N],
   len: [u8; { (log_2_ceiling(N) + 7) / 8 }],
}

[c410-f3r]

Perhaps I am missing something but LEN_BYTES must also come from a user-defined type.

const fn log_2_ceiling(n_minus_one: usize) -> usize {
    let mut r = 0;
    while n_minus_one >> r != 0 {
        r += 1
    }
    r
}

struct ArrayVec<T, const N: usize> {
   data: [MaybeUninit<T>; N],
   len: [u8; { (log_2_ceiling(N) + 7) / 8 }],
}

That is a really nice approach! Thank you for the explanation :)

[tbu-]

Storing the length as NonMaxU32 would allow compiler to optimize Option<ArrayVec> size by storing None as impossible length value (u32::MAX).

This type looks bad for use with ArrayVec, it xors the value with 0xffff_ffff for every operation (except those where it can be optimized out).

[A1-Triard]

it xors the value with 0xffff_ffff for every operation

It is very cheap operation, doesn't it?

[tbu-]

It is very cheap operation, doesn't it?

It's also a useless one. It'd better if Rust could use 0xffff_ffff as a niche. Alternatively, adding 1 to the length might also be better because that works with most operations.

[A1-Triard]

It'd better if Rust could use 0xffff_ffff as a niche.

It can, but using a very unstable part of the language. But I believe it will be stabilized one day,