Skip to content
This repository has been archived by the owner on Sep 12, 2024. It is now read-only.

Tiny Box optimization #20

Open
burdges opened this issue Nov 20, 2020 · 7 comments
Open

Tiny Box optimization #20

burdges opened this issue Nov 20, 2020 · 7 comments

Comments

@burdges
Copy link

burdges commented Nov 20, 2020

It'd help nostd crates if..

There was a TinyBox<T: Sized> type with two functions:

  • Always store T inside its data pointer if size_of::<T>() <= size_of::<usize>() and align_of::<T>() <= align_of::<usize>() but otherwise acts like Box by using the pointer for an allocation if alloc exists, or panics if alloc does not exist.
  • After creation, always determines whether its data pointer is the data or a pointer to an allocation by invoking roughly size_of_val(self) <= size_of::<usize>() and align_of_val(self) <= align_of::<usize>().

In this way, TinyBox<dyn Trait> should works fine without alloc, provided the original type T occupies less than size_of::<usize>() bytes.

Afaik, we do not need rustc modification or std support for this because rustc already requires that size_of_val(self) and align_of_val(self) never deference the self data pointer, and only reads fat pointer metadata like size or vtable. I'm unsure if TinyBox<T: !Sized> makes sense, but initial experiments ran into hiccups there.

After this, one could create a SimpleError trait for error types that avoid allocations, so then some alias type TinyError = TinyBox<dyn SimpleError>; provides almost zero cost dynamically typed errors without alloc. In particular TinyError sounds useful inside Read and Write like trait, which helps #7, but..

We'd want a clean story for promoting TinyError to larger generic error types with backtrace, etc.

@yaahc
Copy link
Member

yaahc commented Dec 3, 2020

Would it be possible to implement TinyBox in a 3rd party library similar to smallvec? Also I'm very apprehensive about adding a new error trait, this was a huge problem with the Fail trait. Adding a new trait will bring back error incompatibility issues all over again, though it might be avoidable if it can be a subtrait of std::error::Error.

I'm unsure if TinyBox<T: !Sized> makes sense, but initial experiments ran into hiccups there.

This seems like it might be pretty important, since otherwise it wouldn't be possible to create a TinyBox<dyn Trait>.

Also, what does the SimpleError trait do in this scenario? I'm not sure how it changes things beyond what TinyBox is doing.

@burdges
Copy link
Author

burdges commented Dec 3, 2020

Would it be possible to implement TinyBox in a 3rd party library similar to smallvec?

Yes. It depends upon dyn Trait fat pointer layout stability, but afaik they'll never changed even if they're not technically stable.

Also I'm very apprehensive about adding a new error trait, this was a huge problem with the Fail trait. Adding a new trait will bring back error incompatibility issues all over again, though it might be avoidable if it can be a subtrait of std::error::Error.

I donno enough about this. We discussed alloc-based gates for Backtrace elsewhere, some options existed, but not confident about their suitability across the board.

I'm unsure if TinyBox<T: !Sized> makes sense, but initial experiments ran into hiccups there.

This seems like it might be pretty important, since otherwise it wouldn't be possible to create a TinyBox<dyn Trait>.

I missspoke.. TinyBox<dyn Trait> makes sense. There also exist TinyBox<T> formulations that make sense when fat pointers to T contain a size, not a vtable, ala TinyBox<[T]>. I encountered preliminary hiccup with a doing a formulation compatible with both use cases however, but so maybe TinyBox::<T>::new requires a T: Sized bound.

We'd need T: Sized for the conversion from TinyBox<T> to TinyBox<dyn Trait> no matter what, so this has zero impact upon error handing. It's just mildly annoying to tell people "oh here is your small box type for rust that does not wast space like the smallbox crate does", and then have it not work for slices.

Also, what does the SimpleError trait do in this scenario? I'm not sure how it changes things beyond what TinyBox is doing.

In my mind, the TinyError aka SimpleError trait would serve mostly to make this work entirely outside core/std.

I probably need to take some time to do a better PoC and then we can more meaningfully discuss how it should align with everything else.

Of course, this is very much going the opposite direction from most of the goals of this group, but if we could make this work along side those, then we'd probably make everyone pretty happy.. well except folk who want to worry about fat pointer stability. ;)

@yaahc
Copy link
Member

yaahc commented Dec 4, 2020

I donno enough about this. We discussed alloc-based gates for Backtrace elsewhere, some options existed, but not confident about their suitability across the board.

ooh well the good news is I'm already working on this issue as part of moving Error to core. the backtrace type will be backed by a hook(or maybe hooks) similar to the panic hook functionality which will let core own the interface but std provide the definition for how backtraces are handled, and that should work with no_std and no_alloc.

I probably need to take some time to do a better PoC and then we can more meaningfully discuss how it should align with everything else.

Sounds good.

Of course, this is very much going the opposite direction from most of the goals of this group, but if we could make this work along side those, then we'd probably make everyone pretty happy.. well except folk who want to worry about fat pointer stability. ;)

I don't really feel like this is going against the goals of the group, though the tie in to error handling is a little tenuous. Either way we're happy to help with brainstorming and providing feedback. If you're interested you should definitely attend our biweekly meetings and give status updates on your progress here.

@lygstate
Copy link

Does the TinyBox are part of rust core library?

@burdges
Copy link
Author

burdges commented Feb 17, 2021

It does not exist yet, but it should only require the dyn Trait layout remain unchanged, so there is no reason to put it in core per se. It's mostly a tweaked reimplementation of core::ptr::Unique which core does not expose. I should really try to do this. lol

@lygstate
Copy link

It does not exist yet, but it should only require the dyn Trait layout remain unchanged. It's mostly a reimplementation of core::ptr::Unique which core does not expose. I should really try to do this. lol

Good to hear if it's finally to be implemented in rust core

@burdges
Copy link
Author

burdges commented Apr 5, 2022

dyn* Trait in https://smallcultfollowing.com/babysteps/blog/2022/03/29/dyn-can-we-make-dyn-sized/ by @nikomatsakis looks like TinyBox<dyn Trait> here, although his "views on traits" goes much further.

I'll note Option<TinyBox<dyn Trait>> could hide the option flag inside the vtable pointer niche, but not inside the value.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants