jam1garner
Remove the 'static requirement from the BinRead Vec implementation by delegating to a new trait method.
Fixes #298.
The core new API here is BinRead::read_options_count, where the implementation for Vec<T> will delegate to T::read_options_count. While I was implementing it, I noticed an inconsistency with the count_with helper, which can be fixed separately in another PR if this approach is rejected (or is taking a long time to solidify).
While I was at it, I decided to try applying the optimization to arrays, and got what is likely a functional result, but I'm not a big fan of it. Are there any tweaks we can make to the read_options_count signature to make the array implementation nicer? Do we want to keep the optimization for arrays, or do we want to keep it as it currently is?
Alternatives
Secondary Trait
Use another trait for this (bikeshed: BinReadMulti) which has the same default impl as read_options_count, and which the derive macro automatically implements using the default impl. i.e.
pub trait BinReadMulti: BinRead {
fn read_options_count(/* ... */) -> /* ... */ { /*...*/ }
}
struct A;
// derive macro:
impl BinReadMulti for A {}
Alongside with an attribute to disable the automatic trait generation, would allow someone to use the derive macro and manually write the multiple item implementation. I don't this this will happen very often, though.
Use dtolnay's typeid crate
https://github.com/dtolnay/typeid allows for obtaining a typeid without 'static. However, it would require us to write some unsafe code within this crate, or get downcast implemented in that crate. (There's also a safety requirement that I'm a little dubious on, but we probably woudn't trip over for this library.
Status Quo: Wait for specialization
Whether specialization or something like this is preferred depends on what type you consider the optimization to be a property of, I guess. Is "you can read integers fast" a property of the integer, or the container(s) of that integer? This PR takes the former viewpoint: we can read u8 fast as a property of u8, not as a property of Vec<u8>, although Vec<u8> benefits as a result.
aaaand i forgot to run tests after adding the array impl. why doesn't rust like this. sigh
~~I'm assuming the tests in CI were failing before this PR? they look mostly unrelated at quick glance~~
Nm kinda just looks like you broke some no_std stuff
AH. Yeah no_std won't like that Vec sneaking into the core implementation either. That's... ugh, i'm not sure what the best way to handle that is, but if we figure it out it probably makes the array impls nicer as well.
nightly has slightly different output for a couple ui tests. go figure. everything's fine on latest stable though, and I'm trying to get CI to tell me what 1.66 looks like, but it's looking fine there too.
in other news, i have potentially over complicated the implementation, but it handles both arrays and vecs nicely.
There's plenty of names here to bikeshed (i have no particular attachment to any of the current names), and proper documentation for the container trait still needs to be written.
Sorry, I started this review yesterday and didn’t see the self-review so some of my questions are redundant :-)
Haven't touched it in a bit, needs to be rebased. There's a non-committed (half-finished?) version that uses iterators instead of a "container" abstraction floating around on my laptop which might improve things for collections in general, but can't specialize for Vec specifically. That might not be too big of an issue, I'm not sure.
I'm considering splitting this into seperate PRs for each design just to make them easier to compare.
Can take a look at it after I sleep.
Having difficulty applying focus to the task right now. Dumping the potentially useful part here:
// only if we decide this should be a separate trait instead of a method with a default implementation.
pub(crate) trait BinReadSlice: BinRead {
fn read_options_slice<'a, R>(
reader: &mut R,
endian: Endian,
args: Self::Args<'a>,
buf: &mut [Self],
) -> BinResult<()>
where
R: Read + Seek,
Self::Args<'a>: Clone;
}
pub(crate) struct ChunkedRead<'args, 'reader, T: BinRead, R, const N: usize> {
remaining_to_read: usize,
next_buf_idx: usize,
buf: [T; N],
reader: &'reader mut R,
endian: Endian,
args: T::Args<'args>,
}
impl<'args, 'reader, T, R, const N: usize> ChunkedRead<'args, 'reader, T, R, N>
where
T: BinRead + Default,
{
fn new(reader: &'reader mut R, endian: Endian, args: T::Args<'args>, count: usize) -> Self {
Self {
remaining_to_read: count,
next_buf_idx: N, // point one past the end
buf: core::array::from_fn(|_| T::default()),
reader,
endian,
args,
}
}
}
impl<'args, 'reader, T, R, const N: usize> Iterator for ChunkedRead<'args, 'reader, T, R, N>
where
T: Clone + BinReadSlice,
T::Args<'args>: Clone,
R: Read + Seek,
{
type Item = BinResult<T>;
fn next(&mut self) -> Option<Self::Item> {
// consider ::uninit::out_ref::Out
if self.next_buf_idx < N - 1 {
let idx = self.next_buf_idx;
self.next_buf_idx += 1;
Some(Ok(self.buf[idx].clone()))
} else if self.remaining_to_read != 0 {
let read_count = self.remaining_to_read.min(N);
let extra = N - read_count;
let buf = &mut self.buf[extra..];
match T::read_options_slice(self.reader, self.endian, self.args.clone(), buf) {
Ok(_) => {
self.remaining_to_read -= read_count;
self.next_buf_idx = extra;
self.next() // reuse the first branch
}
Err(e) => {
// TODO: fuse the iterator into an error state?
Some(Err(e))
}
}
} else {
// buf has been emptied, and there is nothing remaining to read.
None
}
}
}
I toyed around with the idea of an API where you would first get a token/factory type, that you could then create an iterator from. You could then get the current Vec behavior by calling a method on the factory type, instead of creating an iterator.
Unfortunately, for that to work in our actual Vec impl, it'd require specialization :upside_down_face:. So it's unclear if that idea is actually useful in the long run.
As-is, this chunked iterator approach is going to have to balance not using buffers that are too large (for small reads) and not using buffers that are too small (for large reads). maybe should use a dynamic allocation instead of an array?
Having difficulty applying focus to the task right now.
Extremely relatable comment.
Is this approach a third path that is used only by the count helper, or is it a replacement for T::read_options_count, or is the idea that T::read_options_count routes through T::read_options_slice now, or how does this all wire together exactly?
I am not thinking very clearly today but it seems like a larger problem with this is not the balancing of buffer size but the Default requirement? I can’t think of how to get rid of that without unsafe or some inefficient &mut [Option<T>].
If my brain decides to cooperate I may be able to think through this more myself later but I am starting to feel more like the path of least resistance is the way to go as the clever attempts keep terminating at “but we need specialisation for that” and I do think that the 'static requirement issue needs to be fixed before specialisation will land upstream.
In this case, the path of least resistance would probably be to just make the count helper always slow, since I’m pretty sure the only reason to use it instead of the default Vec implementation would be to build into a collection that isn’t a Vec, and already today the specialisation does not apply in that case. Does this make sense?
Would be a replacement for read_options_count. Idea would be read_options_iter -> wraps an opaque(-ish) iterator of some kind -> optionally wraps read_options_slice (either on same trait or different.)
read_options_iter on a type that doesn't support default or doesn't have an optimized read_slice can return a naive iterator that doesn't require them.
read_options_iter on a type that does support default/has an optimized slice read can return an optimized iterator that uses them.