Skip to content

Better memory layout by moving len before xs #254

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
JakkuSakura opened this issue Dec 19, 2023 · 3 comments · Fixed by #255
Closed

Better memory layout by moving len before xs #254

JakkuSakura opened this issue Dec 19, 2023 · 3 comments · Fixed by #255

Comments

@JakkuSakura
Copy link
Contributor

Hi, I noticed that len is arranged after xs

pub struct ArrayVec<T, const CAP: usize> {
    // the `len` first elements of the array are initialized
    xs: [MaybeUninit<T>; CAP],
    len: LenUint,
}

In C's world, it's a convention to move length before an array, like

#[repr(C)]
pub struct ArrayVec<T, const CAP: usize> {
    len: LenUint,
    // the `len` first elements of the array are initialized
    xs: [MaybeUninit<T>; CAP]
}

This provides a few nice features:

  • better locality. First, read the length, then read the element one by one. This should be trivial though
  • Easier to implement tail arrays if were to put on the heap
  • https://github.com/antirez/sds Simply Dynamic String uses a similar layout
@Dushistov
Copy link

It would be also nice, if LenUnit will be generic parameters,
so for CAP < 256 it would be possible to use LenUnit = u8.
The memory layout would be even better.

@JakkuSakura
Copy link
Contributor Author

sure, I'll make len type a generic parameter with default type

I'll also add a reference type to ArrayVec

@YuhanLiin
Copy link
Contributor

The ordering of fields in the default representation (repr(rust)) is unspecified, so the length field might already be ordered before the data. Of course this depends on the compiler's discretion.

@bluss bluss closed this as completed in #255 Mar 7, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants