Where's the catch with Box<Read + Write>?

[newpavlov]

Dynamically generating means run-time heap allocation, right?

Trait objects with Box already do heap allocation regardless, no?

Additionally, IIUC this approach still has the big per-object space overhead that “fat pointer with one vtable pointer per trait” has, it just makes the trait object pointer slightly cheaper to move (and trades that for other costs, like double indirection and heap allocation).

Hm, you are right. With const generics and a bit of compiler magic we probably can remove additional heap allocation and double indirection. Cost of adding additional pointers to stack allocated TraitObject struct is unfortunate, but it’s probably will be the best solution. Although you’ll pay this cost only if you use traits combinations (the more traits in your combination the fatter will be the pointer) so I think it fits under “zero-cost”.

To be explicit, in this approach we’ll change TraitObject struct to:

pub struct TraitObject<const N: usize> {
    pub data: *mut (),
    pub vtables: [*mut (); N],
}

Which with N=1 will be equivalent to the current TraitObject.

[rkruppe]

First, let me step back and state what my motivation here is. The current situation without any multi-trait-object support is unsatisfactory. Even the support without „narrowing“ support would be a great help in most scenarios. I’d like this to start moving somewhere, if I can help to push it a bit, that’s even better.

A good point, quite a few people in the Rust community (me included) tend to fall prey to “perfect is the enemy of good”

I don’t think if we introduce some solution that the compiler would guarantee it’ll always use the same way ‒ so if a better solution is found later on, it could be replaced.

In terms of implementation strategy? More or less, sure.

However, implementation strategies matter insofar that if no possible implementations strategy for upcasting is acceptable, then we’ll probably never have upcasts for multi-trait objects, period. If true (and it looks more and more true to me the longer I think about it) that has implications for the language design. “We’ll accept this subset of the feature and work out the generalization later” is quite different from “we let you do this thing but the natural generalization will never be possible, sorry”.

Don’t these get deduplicated during link time? I hoped that if two crates in the dep graph both use HashMap<u32, u32>, only one monomorphisation gets put into the result and a vtable generated on the spot when converting to trait object looks like a very similar concept to this.

See https://github.com/rust-lang/rust/issues/46139 – QoI issue, currently we don’t deduplicate (at least not perfectly), and there are no guarantees.

Then we could get worse performance than other multi-trait-objects with the same set of trait only if it got created by the narrowing operation, which I think would be quite rare.

I think it will be quite common to hold a trait object with a bunch of different traits, then upcast to one specific trait to interact with a library that only needs that one trait.

Not necessarily to that level. I could imagine (read: I have no idea if this is possible in current rustc) that the type erasure would link to an extern symbol for the vtable, so most of the compilation could happen without knowing the whole set of traits the type implements. Only the generation of the vtable would have to happen at the end, when all the traits for the type are known, and the vtables are likely to be reasonably small bits of code, so that work after this all is gathered together wouldn’t be that big.

That still requires analyzing the whole program when you create the vtable at the end. And it assumes there is a unique place to do that – in the usual work flow that’s the leaf binary/staticlib, but AFAICT it doesn’t play nice with dylibs, where one library’s compilation artifact can be used from multiple binaries. (dylibs are Terrible for many reasons, but we need to keep them at least functional.)

Trait objects with Box already do heap allocation regardless, no?

Not all trait objects use Box. &Trait is a thing, for example. It works perfectly fine without any heap allocation.

Also, Box<Struct> -> Box<Trait> performs no heap allocation, it just reuses the heap allocation for the object and adds a vtable pointer “externally”. With your strategy, there’s a heap allocation any time a trait object pointer is created or upcasted.

To be explicit, in this approach we’ll change TraitObject struct to: […] Which with N=1 will be equivalent to the current TraitObject.

Isn’t that exactly the “fat pointer with many vtable pointers” approach I described at the start?

(Which isn’t blocked on const generics because it’s compiler built-in.)

[newpavlov]

Isn’t that exactly the “fat pointer with many vtable pointers” approach I described at the start?

In the end, yes, it is.

(Which isn’t blocked on const generics because it’s compiler built-in.)

Is it? IIUC we will have to change std::raw::TraitObject, which will be blocked on const generics if we want to reduce amount of compiler magic to the minimum.

[rkruppe]

Is it? IIUC we will have to change std::raw::TraitObject, which will be blocked on const generics if we want to reduce amount of compiler magic to the minimum.

Oh. I forgot about that because it’s an obscure and unstable piece of library code that isn’t used very often. We don’t have to extend it to multi-trait objects, we can just say it’s for trait objects with a single non-auto trait, and all other trait objects have unspecified layout. This is especially useful if we want to keep the implementation details fluid, like @vorner suggested.

We could even deprecate and remove it. It’s a very brittle and limited API.

[vorner]

However, implementation strategies matter insofar that if no possible implementations strategy for upcasting is acceptable, then we’ll probably never have upcasts for multi-trait objects, period.

To clarify the compiler jargon, upcasting means the narrowing? If so ‒ I think most of the mentioned strategies would be sub-optimal but workable solutions. Especially if they can be made to pay for the cost only if they are actually used.

I think it will be quite common to hold a trait object with a bunch of different traits, then upcast to one specific trait to interact with a library that only needs that one trait.

Most libraries expose the static-generics, so (if I look at it correctly) if I have Box<Read + Write> and want to call serde_json::to_writer<W: Write> on it, I don’t need to create narrowed-down trait object, I just generate another monomorfization of to_writer that takes W = Box<Read + Write>. Because that one implements Write.

Therefore, I think the need to convert to narrower trait object is useful mostly in cases where I have a collection of some trait objects and want to get a collection with more general (eg less trait-constrained) trait objects. The mentioned strategies have little problems with supporting conversion to single-trait objects. So we really are talking about something a bit rare ‒ upcasting from lest say 4-trait object to 2-trait object.

[rkruppe]

To clarify the compiler jargon, upcasting means the narrowing? If so ‒ I think most of the mentioned strategies would be sub-optimal but workable solutions. Especially if they can be made to pay for the cost only if they are actually used.

Upcasting is not (Rust) compiler jargon, it’s OOP jargon

I don’t believe multi-trait objects that are never upcasted can be insulated from the implications of supporting upcasts. This is because, again, there might be code anywhere in the application that performs an upcast, so all multi trait objects need to be represented in whatever way is needed for upcasts.

With that in mind, supporting upcasts potentially has a huge cost. It’s possible that we’ll pick the “N vtable pointers” approach for other reasons, in that case upcasting is cheap to add. But these decisions are interwined.

Most libraries expose the static-generics, so (if I look at it correctly) if I have Box<Read + Write> and want to call serde_json::to_writer<W: Write> on it, I don’t need to create narrowed-down trait object, I just generate another monomorfization of to_writer that takes W = Box<Read + Write>. Because that one implements Write.

Hm, good point about proxy impls on trait objects. However, in my experience trait objects in interfaces (including interfaces within a crate) are somewhat common, despite the popularity of generics, especially in “business logic” crates as opposed to foundational crates that provide data structures, algorithms, serialization, etc.

The mentioned strategies have little problems with supporting conversion to single-trait objects. So we really are talking about something a bit rare ‒ upcasting from lest say 4-trait object to 2-trait object.

Are you suggesting we restrict which upcasts people can do? That, too would be a valid language design decision informed by what is and isn’t implementable efficiently.

[skade]

I don’t believe multi-trait objects that are never upcasted can be insulated from the implications of supporting upcasts. This is because, again, there might be code anywhere in the application that performs an upcast, so all multi trait objects need to be represented in whatever way is needed for upcasts.

Trait objects can be passed through FFI and used in dynamic libraries, so you can’t expect that it is never upcasted, even if you’d delay the analysis as much as possible.

[atagunov]

Are you suggesting we restrict which upcasts people can do? That, too would be a valid language design decision informed by what is and isn’t implementable efficiently.

…that’s as much upcasting as C++ supports isn’t it?

Matching C++ is probably not that shabby. Surely C++ people have weighted pros and cons of different approaches and how much upcasting could be supported without incurring unreasonable implementation costs?

[rkruppe]

Matching C++ is probably not that shabby. Surely C++ people have weighted pros and cons of different approaches and how much upcasting could be supported without incurring unreasonable implementation costs?

C++'s entire approach to ad hoc polymorphism (both in the design philosophy and the implementation) is so different from Rust’s that I don’t think such a comparison is useful.

But let’s run with the analogy. I suppose you’re referring to multiple inheritance:

class Foo {};
class Bar {};
class Quux {};
class Multi : Foo, Bar, Quux {};

Now FooBar* can be upcasted to either Foo* and Bar* and Quux*, but there’s no way to get something that inherits the methods of two of the base classes but not the third. If one wants that, additional classes have to be defined and arranged into an inheritance hierarchy.

The moral equivalent of that is this Rust code, which already works today:

trait Foo {}
trait Bar {}
trait Quux {}
trait Multi: Foo+Bar+Quux {}

impl<T: Foo+Bar+Quux> Multi for T {}

Here, too, we explicitly called out the combination of Foo, Bar, and Quux and reified it into a separate entity Multi, and similar limitations to the C++ variant.

Since we can already do that, I’d expect multi-trait objects to be somewhat more flexible – a dynamically dispatched analogue to T: Foo+Bar+Quux bounds in generics, rather than to T: Multi. Something that is freely composable, rather than forcing the programmer to create and maintain an artifical and inflexible hierarchy.

[atagunov]

… we can already do that …

Exciting, thx a bunch!

One feature missing is upcasting &Multi to &Foo isn’t it?

[mikeyhew]

Is it? IIUC we will have to change std::raw::TraitObject, which will be blocked on const generics if we want to reduce amount of compiler magic to the minimum.

Wait, how is that blocked on const generics?

[mikeyhew]

Or, would it be possible to delay the creation of this table to the main crate being compiled? At that point, all the dependencies are already known, aren’t they?

Something along those lines has been suggested by several people. It’s a natural impulse, but it means that compiling a Rust program requires whole-program analysis, i.e., any line of any crate involved can potentially influence how any other line is compiled. That has severe downsides:

FWIW, if vtable generation were delayed until the main crate is compiled, that would mean generic methods could be object-safe. Which would be really cool and powerful. But it seems like the costs are too high

[newpavlov]

See example in this post, N there is a number of trait combinations in trait object signature, e.g. N will be equal to 2 for Read+Write object.

[mikeyhew]

Thank you for providing that context. As far as I understand, the only use for raw::Traitobject is to be able to split trait objects apart and put them back together. Is that not true? If that is the case, then functions can be provided to do just that, generically, for all ?Sized types and not just trait objects, which would anyway be a big improvement over the current situation. So not blocked on const generics, although that is going to be an awesome feature that I’m really looking forward to.

[rkruppe]

One feature missing is upcasting &Multi to &Foo isn’t it?

Oh yeah sorry forgot to mention that. You can sometimes add methods as_foo(&self) -> &Foo etc. or even as_foo(self: Box<Self>) -> Box<Foo> (on stable, this only works for Box right now, not for e.g. Rc) to emulate it.

[vorner]

Are you suggesting we restrict which upcasts people can do?

Only as a last resort… just saying it would be possible, not something to aim for.

With that in mind, supporting upcasts potentially has a huge cost.

Can we somehow summarise the costs for various approaches? Because I don’t think some of the costs mentioned here would be that huge and maybe measuring it might make sense. I definitely want to have a look at measuring the overhead of my approach (but I’m afraid it might take some time before I get to it).

[atagunov]

To expand a bit more on the “last resort” solution, one could spell out manually what upcasts are allowed:

trait Foo {}
trait Bar {}
trait Quux {}

// r can be cast to &Foo, &Bar, &Quux, &<Foo + Bar> but not to &<Foo + Quux>
let r : &<Foo + Bar + Quux + (Foo + Bar)> = ...

maybe some shorthand like type FooBar = Foo + Bar could be used to make &<Foo + Bar + Quux + FooBar> equivalent to the above

[rkruppe]

Can we somehow summarise the costs for various approaches? Because I don’t think some of the costs mentioned here would be that huge and maybe measuring it might make sense. I definitely want to have a look at measuring the overhead of my approach (but I’m afraid it might take some time before I get to it).

Very broadly, all approaches that support arbitrary upcasts seem to have either:

• binary size overhead from vtables exponential in the number of traits used per trait object type
• run-time space overhead per trait object pointer (not trait objects) that is linear in the number of traits used in the trait object

Some approaches also add double indirection to virtual calls to improve the constant factor on either of the above.

[vorner]

Very broadly, all approaches that support arbitrary upcasts seem to have either:

Either I’m missing something important, or explained my approach in a wrong way, because I believe it has neither of these two.

A multi-trait object has just one vtable pointer.

There are two ways how to tune binary-size vs. speed costs:

• When doing type erasure to a multi-trait object, create one big vtable with all the locally known traits. This is AFAIK at most one vtable (with autogenerated code of size linear in number of total methods of the type) per compiled crate (I hope rustc can do at least crate-global analysis, if not whole-program-global analysis).
• The other option is to create a vtable with only the needed traits for this type erasure. This in theory can be exponential number of different vtables. But as I create one only when doing the type erasure (not upcast from type object to type object), this happens only in exponentially large programs, so the size of binary is still polynomial in the size of the source code.
• A hybrid is to create one vtable per crate, but include only union of traits needed across all the type erasures happening in that crate. This is basically the first option, but optimised not to include things that are never used.

Yes, it does add a double indirection, but only one of them is dynamic.

The fact some trait objects may have faster or slower dynamic dispatch (because they carry lookup tables of different sizes for different sets of traits) is unfortunate, but as different trait objects can have different implementations of the methods being called through that dispatch, this doesn’t sound like a very big deal.

[rkruppe]

Sorry, you’re right, I somehow forgot about that approach.