Skip to content
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

Vec: add const-erased "view" #424

Closed
wants to merge 2 commits into from

Conversation

sosthene-nitrokey
Copy link
Contributor

@sosthene-nitrokey sosthene-nitrokey commented Dec 15, 2023

Fix #371

This PR adds a VecView<T> struct that is !Sized and wraps a Vec<T, N>, providing the same functionality (except those that require taking the vec by-value). It also makes the implementation for all methods on Vec<T, N> delegate to the VecView implementation, reducing the need for monomorphised code for each value of N used.

Example:

let mut v: Vec::<u8, 10> = [1,2,3,4].into_iter().collect();
let view: &mut VecView<u8> = v.as_mut_view();
view.push(5);

This change should brings the following benefits:

Better binaries

  • Faster compile times: since less functions are monomorphized less code needs to be optimized and the compile time should be faster (not yet benchmarked)
  • Smaller binaries: similarly, less monomorphized code should also lead to less code overall. On the Nitrokey 3 firmware we observed a small benefit (0.2%), by just using this patch, but I believe there are more gains to be had if we start explicitly using this pattern in our own code, for example in heapless-bytes too and then everywhere else.

Better ergonomics

Since Vec always requires the N to be specified, this makes generic code much less convenient.
For example a lot of our firmware write responses to buffers passed by the caller. To make that code generic implies having functions like:

fn respond<const R: usize>(&mut self, request: &[u8], reply: &mut Vec<u8; N>)

With this PR it could instead become:

fn respond(&mut self, request: &[u8], reply: &mut VecView<u8>)

Which is much simpler to use.

This also allows using this method in a trait with sacrificing object safety. This is the main driver for this feature, before the binary/compile-time improvements.

TODO

  • Implement missing traits for VecVIew
  • Document VecView
  • De-duplicate the documentation between VecView and Vec. In the PR all methods are documented twice, this could lead to the docs getting out of sync. Soluctions could be to implement the functionality on VecInner and use a macro to generate the method for both Vec and VecView, or having one of the documentation refer to the other.
  • Implement this pattern for other data structures. Nitrokey only uses the Vec of heapless, but it is certain that other consumers of this crate could benefit from the same gains for other structures in heapless.
  • Make sure that the current approach can be adapted in the future with the CoerceUnsized traits.
    I'm not sure about this one because the traits are unstable, but I would aim for the possibility of coercing a Vec into a VecView with the same ease as it is to convert a &[T; N] to a &[T]. I don't really know where the language is going with this and whether the #[repr(transparent)] wrapper could turn out to be a blocker for that functionality.

Comment on lines -32 to -35
// NOTE order is important for optimizations. the `len` first layout lets the compiler optimize
// `new` to: reserve stack space and zero the first word. With the fields in the reverse order
// the compiler optimizes `new` to `memclr`-ing the *entire* stack space, including the `buffer`
// field which should be left uninitialized. Optimizations were last checked with Rust 1.60
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this is not relevant anymore. The unsized type is always necessarily the last so the optimization should take place.

@sosthene-nitrokey
Copy link
Contributor Author

Make sure that the current approach can be adapted in the future with the CoerceUnsized traits.
I'm not sure about this one because the traits are unstable, but I would aim for the possibility of coercing a Vec into a VecView with the same ease as it is to convert a &[T; N] to a &[T]. I don't really know where the language is going with this and whether the #[repr(transparent)] wrapper could turn out to be a blocker for that functionality.

From what I've seen there is no current plan to stabilize a manual way to implement Unsize<VecView> for Vec. This means that to get that feature, the Vec and VecView must be directly the VecInner struct. This can be achieved with a reasonable API by having:

  • VecInner be pub but no use in the lib.rs so that it is public but not nameabled (aka sealed).
  • Vec and VecView be aliases to VecInner.

This works in providing all the API as we want, but it comes at the cost of having the documentation be completely lost because it is generated on the VecInner and not on Vec and VecView, but there has been recently some work to get it to work, and the latest nightly already shows some trait implementations that the latest stable does not. I think this API would be better, if rustdoc could handle it properly.

@sosthene-nitrokey
Copy link
Contributor Author

The build error happens on main for me too.

sosthene-nitrokey added a commit to Nitrokey/heapless that referenced this pull request Dec 21, 2023
@sosthene-nitrokey
Copy link
Contributor Author

I believe that #425 provides a better implementation than this PR, and the main issue I had with it (documentation) has a decent workaround, I believe that #425 should be considered instead of this PR.

sosthene-nitrokey added a commit to Nitrokey/heapless that referenced this pull request Jan 2, 2024
sosthene-nitrokey added a commit to Nitrokey/heapless that referenced this pull request Jan 21, 2024
sosthene-nitrokey added a commit to Nitrokey/heapless that referenced this pull request Feb 7, 2024
sosthene-nitrokey added a commit to Nitrokey/heapless that referenced this pull request Feb 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 this pull request may close these issues.

Add const-erased versions of the various containers
1 participant