Change type of ArrayVec's len to u8/u16

[Soveu]

pub struct ArrayVec<A: Array> {
  len: usize,
  pub(crate) data: A,
}

I think that usize here is a bit of overkill, because

• stack space is very limited (few megabytes)
• moving these huge arrays is costly anyway

Changing it to u16 or u8 could make this structure a bit smaller
(btw why is ArrayVec repr(C)?)

[Lokathor]

I can easily imagine wanting an arrayvec bigger than 256 elements, so u8 is out, but u16 might be a sane option.

However, I don't know that saving 2 bytes is a big deal.

[Soveu]

Not only 2 bytes, also it can change the alignment
EDIT: 2 bytes on 32bit platforms, 6 bytes on 64bit

[Soveu]

slaps the roof
ArrayVec with u16 len can fit so many bytes in it
rust playground link

[Shnatsel]

I was initially skeptical as well, but accounting for alignment it does appear to be worthwhile. Those 48 bytes vs 32 bytes cases do look impressive.

[Lokathor]

I'm convinced enough.

This is technically an ever so slight break.

I'd be willing to make this change in the transition from 0.4 to 1.0. That's August 27th (next rust release).

One important detail is that len operations should still take place in the usize type as much as possible. It sounds dumb but it's slightly more efficient to have ops be done using the CPU's native register size.

[Shnatsel]

Let's do a fuzzing run before releasing 1.0 so that we catch the overflows such as rust-lang/rust#72237

[Lokathor]

yeah we can fuzz main

[Lokathor]

@Soveu I'm declaring that you've got until the 13th to have it all set. That's 2 weeks for code changes, and then 2 weeks for fuzzing and finalization.

[Soveu]

With the current implementation we can manually limit the max array size to u16::MAX, but on const generics we can't declare N as u16

struct ArrayVec<T, const N: u16> {
  len: u16,
  data: [T; N], // <- N must be usize, [T; N as usize] does not work
}

Maybe it is worth filing an issue on rustc github

[Soveu]

Even checks like this don't work :/

[Lokathor]

big oof

[Lokathor]

I'll ask on zulip if this will be in the min_const_generics.

in general, i think that 1.0 will be minimum rust 1.34 and basically not support const generics that well, if at all, and then once const generics are properly stable, we'll do a 2.0 version some day with a sufficiently higher minimum rust version.