The Any trait should not use virtual calls for type checks

[pcwalton]

These are slow and should be unnecessary. They are showing up in Servo profiles.

[pcwalton]

To be clear what it should be doing instead: It should be pulling the vtable out of the trait object and inspecting the tydesc therein directly.

[nikomatsakis]

This would also address #10389

[nikomatsakis]

Well, it might address #10389 anyway. Though I think in practice we'd probably have to limit the types that Any could be applied to to nominal types which can have a unique type descriptor -- actually, I wasn't considering genericity. Even that doesn't work so obviously well. Never mind. Carry on.

[Kimundi]

Any using the typedesc from the vtable was the initial design, I changed it to what got merged for two reasons:

1. typedescriptors can be duplicated, making type equality not work across crate
2. @thestinger mentioned that having the type descriptor in the vtable at all is something that he'd like to see changed, as it prevents merging of identical vtables, which means using virtual calls is the only way to encode the information in a trait object.

[nikomatsakis]

We can also just add a u64 field to the struct that stores the hash/whatever-code-we-eventually-settle-on. That would prevent virtual calls, we'd just have to load the field and compare.

[eddyb]

There are two non-Any-specific-compiler-magic ways of solving this, that I can think of:

• if we had pure functions, a pure method taking no arguments could be replaced in the vtable by its result (and on x64, we could represent &Any as (TypeId, *data), since the method returning the TypeId would be the only one in the vtable - this is an optimization I've mentioned a few times before)
• associated items in traits could also provide the optimizations mentioned above (might require CTFE if they are treated like today's statics)

[treeman]

Triage bump, carry on.

[eddyb]

Given that we are going to get associated items, an associated constant with get_type_id::<Self>() as the value seems like the best option.
The intrinsic call could be allowed without any form of CTFE.

[thestinger]

There's no type id or type descriptor in the virtual function table right now. There's only a slot for a destructor and then the methods.

[Yoric]

If someone is willing to mentor me on this, I'd be interested in giving it a try.

[eddyb]

@Yoric It's a design problem, i.e. how do you represent the TypeId in Any such that it's a load of a vtable field?

I was going to go with "associated constant" a while back, but now that trait objects work by having the compiler implement Trait for Trait, with each method that is available (i.e. not those with where Self: Sized) forwarding through the vtable, there is a problem:

Anything that has to look up the vtable needs access to self, and this rules static methods and associated constants.
I would be happy with a compromise, such as trait_object.CONST which doesn't go through the Trait impl for Trait shim, but I doubt others would like that.

[Yoric]

Right, and I take it that we want to ensure that there is no vtable even when we don't monomorphize.

How would trait_object.CONST work? I may be missing something, but that looks much more like duck typing than any kind of polymorphism I have seen in Rust.

[eddyb]

Right, and I take it that we want to ensure that there is no vtable even when we don't monomorphize.

I don't understand what you mean here. This issue is about avoiding a virtual call, not the entire vtable, which is necessary (and having TypeId as a field in the vtable is probably the best we can do).

How would trait_object.CONST work? I may be missing something, but that looks much more like duck typing than any kind of polymorphism I have seen in Rust.

Assuming the following definition compiles, Trait should be object-safe:

trait Trait {
    fn method(&self) -> char;
    const CONST: char where Self: Sized;
}

Then one could imagine the vtable to also contain CONST, i.e.:

struct VtableForTrait {
    dtor: unsafe fn(*mut u8),
    size: usize,
    align: usize,
    method: unsafe fn(*const u8) -> char,
    // The above fields are present in current Rust, only CONST below is new:
    CONST: char
}

And let's add some impls:

struct A;
impl Trait for A {
    fn method(&self) -> char { 'A' }
    const CONST: char = 'A';
}
struct B;
impl Trait for B {
    fn method(&self) -> char { 'B' }
    const CONST: char = 'B';
}

<Trait as Trait>::CONST would still be missing, because there's no way to supply the actual trait object to get the original CONST value from the impl (of Trait for A or B, in this case).

Methods don't have this problem: we could call method via trait_object.method(), which is really sugar for <Trait as Trait>::method(trait_object), and that will go through the vtable of trait_object.

However, we don't want the cost of calling a method through a vtable, especially if we can just load CONST instead, so what we're missing is a way to get CONST from trait_object (of type &Trait).

And what I'm proposing is to just use trait_object.CONST:

let trait_objects: [&Trait; 2] = [&A, &B];
assert_eq!(trait_objects[0].CONST, 'A');
assert_eq!(trait_objects[1].CONST, 'B');

[eddyb]

Thinking more about this, it's effectively a feature request for accessing constants on trait objects, or a similar feature, allowing Any to read a vtable field instead of calling a virtual method.

Therefore, I believe it belongs on the RFCs repo, as an issue in this form, or a fully fledged RFC.

cc @rust-lang/lang

[aturon]

@eddyb I agree. I'm actually working with @nikomatsakis on a related RFC in the near future :)

[Yoric]

I don't understand what you mean here. This issue is about avoiding a virtual call, not the entire vtable, which is necessary (and having TypeId as a field in the vtable is probably the best we can do).

Sorry, I meant a virtual dispatch.

[Yoric]

I'm not up-to-date in how traits and vtables are represented, so please bear with me if I stumble upon this like a complete noob, but wouldn't it be as simple to somehow use the address of the vtable implementing Any as a typeid? If so, we could replace pure virtual get_type_id with an implementation uniform across all implementations of Any.

Or is this a problem because of @Kimundi 's earlier comment on eliminating duplicate vtables?

[eddyb]

@Yoric we do not and cannot (AFAIK) deduplicate vtables to make that work.

[Yoric]

@eddyb Out of curiosity, how/when do we end up with vtables that would need to be deduplicated?

[eddyb]

@Yoric More than one crate. If you want to make it even more complicated, add generics that you monomorphize in different crates with different parameters.

[Yoric]

Right, that makes sense. On the other hand, could it be possible to generate a globally unique identifier per type (using, basically, mangling), and store it at constant position in the vtable?

[nikomatsakis]

@eddyb another option would be to special-case this some, and just have all vtables include a TypeId -- or at least those that extend Reflect -- we could then use unsafe code to extract it. :)

[Yoric]

That doesn't sound very different from my suggestion, except for the mangling part.

[aturon]

Closing, since our preferred approach here would require an RFC.