A mechanism for virtual overloads

@MaxGraey

Currently, the compiler does not support virtual overloads of class members, as one would expect from JS, but instead resolves the respective member statically from the contextual class type. This is noted in the docs so far but we should aim at resolving this.

What's necessary here is to decide on a mechanism to resolve the virtual function or field at runtime, using the unique class ids we already have in RTTI plus, possibly, unique ids for each virtual member.

Let's say we have A#foo() with foo possibly being overloaded by a class B extends A, the implementation must call B#foo() here if the actual instance we are dealing with is a B, not an A. Interfaces are similar.

One mechanism I thought about so far is to use the unique class ids (here: of A and B), and give the foo member another internal unique id, so we can generate a runtime lookup function that performs a (memberId, classId) -> functionIndex or fieldOffset mapping through a compiler-generated big switch. The implementation on the compiler side should skip making a runtime lookup if it is not necessary (that is: the class has no subclasses or respective interfaces) for perf reasons. If it is necessary, calling a virtually overloaded functions becomes a call_indirect.

This isn't exactly scientific but is solely based on what I think would work, so if this problem has already been solved in better ways in the past, feel free to comment :)

@MaxGraey, @willemneal, @bowenwang1996

I'm also not pretty experienced in different approaches but agree with your notes and also add on my own:

All subclasses share one vtable which create (link) in basic class constructor.
vtable not create if:
- basic class hasn't any subclasses or interfaces
- all methods are private or just fields
only non-private methods with identical name and signatures (?) added to vtable. Methods declared in interfaces or abstract classes always add to vtable for class which realize its.
add @final decorator? 🤔

@willemneal

Sounds reasonably to me. Let's see whether @willemneal has something to add.

All subclasses share one vtable which create (link) in basic class constructor.

In this case, the functions would look like

function MyClass~virtual(memberId: u32): u32 { // classId implicitly is idof<MyClass>
  switch (memberId) {
    case 0: return SOME_CONST;
    case 1: return SOME_CONST;
    case 2: return SOME_CONST;
    default: unreachable();
  }
}

Questions are:

Can we guarantee that member ids are adjacent? Looks like mixing interfaces into different classes will lead to holes.
How much redundant code would having one function per class yield (like, each subclass would need one case even if the member isn't overloaded deeper in the tree)? Will we be missing optimization opportunities compared to one large function where Binaryen can optimize a single big switch?

The alternative is to reverse classId/memberId by using a single function that first switches over memberId, and only then over classId:

function ~virtual(memberId: u32, classId: u32): u32 {
  switch (memberId) { // guaranteed to be adjacent because memberId is a global counter
    case 0: {
      switch (classId) {
        // might become a br_table or a series of ifs depending on classId distribution here
      }
    }
    case 1: {
      ...
    }
    default: unreachable();
  }
}

In this case, the most important question is whether such a function will optimize well. On a first glimpse this "looks" like Binaryen can rereloop a lot of stuff, but haven't seen it in action yet ofc. Hmm...

My first question is are we going to now implicitly inherit from an Object class?

Also do we want interfaces to be structural and nominal like typescript? Personally I think we should.

I think the per class method would be a good first step; you could use the class id as the index into the function table or a memory address it's

What do you mean by "each subclass would need one case even if the member isn't overloaded deeper in the tree".

I also have another question. When are class id's computed currently? After parsing? Or during compilation?

My first question is are we going to now implicitly inherit from an Object class?

I think we should do this in the long term, yeah. If we can do this now, sure, why not.

Also do we want interfaces to be structural and nominal like typescript? Personally I think we should.

Depends if a static compiler can do that. Consider those two classes for example:

class Foo { a: i32; b: f32; }
class Bar { b: f32; a: i32; }

These are statically incompatible even though structurally compatible, but interfaces might not suffer from this due to all members being virtual. So I guess that there might be ways to make something structurally compatible sometimes, not but every time, which leaves the question whether we should do it at all. Might even be that structural things like these don't work well with static typing.

What do you mean by "each subclass would need one case even if the member isn't overloaded deeper in the tree".

In a single global function there can be switch fall-throughs, while if there's one function per class every function must either implement all the cases up the tree or fall-through by means of calling the overloaded virtual table function, leading to more code overhead than just a big switch (which might also optimize better because it's one large blob of code that can possibly take advantage of re-relooping).

When are class id's computed currently? After parsing? Or during compilation?

The class ids of ArrayBuffer, String, ArrayBufferView are generated when the program is initialized, as these are static, while all the others are generated as soon as a concrete class is resolved (from type arguments), which happens during compilation when the compiler sees the use of a type or expression that requires resolving a class.

So I guess that there might be ways to make something structurally compatible sometimes, not but every time

If we are going to make fields, e.i. getter functions, have a unique member ID, we will always be able to determine structurally compatibility.

Consider this interface:

interface AB {
  a: i32;
  b: f32;
}

Then both of the above classes would implement it structurally even if they aren't in the same order. If there is ever flow where either class could be used where an AB interface is expected, we would be able to test that each class contains the set of member ids of the interface. Go, typescript, and other languages have static structural typing so it's definitely possible. After being able to validate that the class implements the interface then its invocation the same as if it was nominal. E.g.

class Foo implements AB { a: i32; b: f32; } differs from class Bar implements AB { b:f32; a: i32;}

But the use of virtual functions means it doesn't matter.

I understand the want to keep everything in one function for compactness and potential optimizations, but one down side is a lack of modularity. For example, assuming we could merge wasm binaries (which will be a future runtime feature of the loader), we couldn't merge the two big virtual method lookup functions, whereas it would if each class is responsible for their table.

Perhaps we should add a step between parsing and compiling, where we resolve classes/interfaces. A special transform that starts at the entries and produces a condensed program object, which only contains statements that will be compiled and handle the type checking.

Then both of the above classes would implement it structurally even if they aren't in the same order.

If field layout isn't statically compatible, accessing any of its members structurally must resort to doing a virtual lookup. So I assume what you are proposing here is to have something like hidden interfaces for class types that are used interchangeably in a structural way? This incurs some overhead (that might ofc be worth it).

I understand the want to keep everything in one function for compactness and potential optimizations, but one down side is a lack of modularity. For example, assuming we could merge wasm binaries (which will be a future runtime feature of the loader), we couldn't merge the two big virtual method lookup functions, whereas it would if each class is responsible for their table.

Not so sure about this point. There are already things that cannot be merged easily having just executables, like RC's __visit_members. My expectation there would be that merging requires at least enough meta information to first strip and then regenerate these features after the merge, so whether or not that'd be one or multiple functions isn't really important just for that. From a WebAssembly perspective, I think that static linking will assume two otherwise independent modules and make them work in one module (at least initially), while an AssemblyScript linker will reuse additional information to do it in a way that both modules join together to a single AS program.

More generally spoken, the way to go here seems to first get interfaces up and running, and only then think about structural compatibility of other types, like using hidden interfaces which we can always do. Does that sound reasonable?

Yeah that's what we should do for sure. My point was once we have the nominal interfaces, the implementing structural becomes easy. Assuming we have a virtual lookup for each method of a class that implements the interface, then all it would take is to add all classes that match it structurally as implementing the interface.

Regardless I think the place to start is what you first suggested:

function MyClass~virtual(memberId: u32): u32 { // classId implicitly is idof<MyClass>
  switch (memberId) {
    case 0: return SOME_CONST;
    case 1: return SOME_CONST;
    case 2: return SOME_CONST;
    default: unreachable();
  }
}

Each classid could correspond to an table entry that points to the class's virtual method like above.

Then each class has its methods in the table and function above would map the method ids to their table entries.

let func = call_indirect(load<u32>(ref - 8), memberid); // Calls MyClass~virtual.
call_indirect(func,...) // make actual function call.

Then after we get this to work interfaces are just classes with static methods that do the above look up on a constant memberid. After get some data about the performance we can revisit and use a different method.

Does this make sense?

Another pro for a single function might be that multiple levels of indirect calls can be avoided, since we don't have to look up the respective virtual function first. I also wonder if storing something (for methods) in class instance's memory can be avoided, e.g.

let func = ~virtual(memberId, classId); // direct call returning the function index, memberId is static
call_indirect(func, this, ...args) // make the actual function call

where ~virtual contains the statically known function indexes directly and avoids a second indirect call due to being a single big function. This seems like it can be more efficient, if I'm not missing something about storing in instance memory (please let me know if I do). Also, if it just so happens (memberId and classId are constant, even though classId usually isn't) that Binaryen can precompute the outcome of the ~virtual call, it can optimize the indirect to a direct call, but this might not necessary be possible in the single function case only.

How about Static Polymorphism? And CRTP which desugared (generated) by compiler?

So this code:

class B {
   i: i32 = 1;
   add(i: i32): void { // abstract method
   }
}

class D extends B {
    add(i: i32): void { // override subtyped method foo
       this.i += i;
    }
}

let boo: B = new D();
boo.foo(1);
log(boo.i); // should be 2

generate as:

class B {
   i: i32 = 1;
   add(i: i32): void { // abstract method
   }
}

class _B<T extends D> {
  i: i32 = 1;
  add(i: i32): void {
    changetype<T>(this).add(i); // generated in compile time
  }
}

class D extends _B<D> {
  add(i: i32): void { 
    this.i += i;
  }
}

let boo: _B<D> = new D(); // _B<D> generated in compile time
boo.add(1);
log(boo.i); // -> 2

Of course it as always speed / size trade-off so main disadvantage of this approach is quickly growing codesize and slower compilation but I guess this could be partially solved.

When we have a D down-cast to B, and pass that around to

function callMe(actuallyD: B): void {
  actuallyD.add(1);
}

how would the compiler not have to do a lookup there? I might be missing something, but CRTP seems like an alternative pattern that can be used in some situations in C++, but doesn't necessarily solve our inheritance model.

We don't cast to B actually. Instead we cast to statically generic class _B<D> which link to its supertype.

See this approach in C++ fiddle. I don't use virtual keyword.

btw great article how this solving in different languages (C++, Java and C#):
https://lukasatkinson.de/2018/interface-dispatch/

So it seems that they are all in memory tables. I've been working on it and I've currently updated the compiler so that whenever there is a conversion from a concrete type to an interface (e.g. passed into a function that has an interface as the parameter type), the concrete class is added to the interface's list of implementing classes (the class is also checked if it adheres to the interface, meaning that it handles structural interfaces as well). Then at call sites, the call convert into calling ~virtual passing in the signature id and then class id of the concrete object.

Then at the end of compilation each compiled interface method looks up the corresponding function prototypes of the implementing classes and compiles if necessary, adds to the function table, and collects the table entries.

I'm stuck figuring out the reloooper, but am getting close. However, after reading the article I am drawn back to adding in memory vtables and fat pointers seem like the best way to add mixins/traits/ default interface methods.

Also above once the interfaces methods are known, we could reassign them method ids so that they are sequential and then recompile the interface methods using the new ids.

All in all I think that there is some middle ground here. I think we should start with the table as is and then see how it affects performance.

Isn't one important difference to the mechanisms in the above article that we have a classId on each instance (that ultimately determines the vtable) and there's nothing like (<SomeInterface>someObject).someMethod like in Java that can call something different than someObject.someMethod in JS, so we don't even have to think about something like itables?

I've finally got the relooper working and am close to pushing what I have. It depends on if we want to leave ourselves open to adding new features that JS doesn't support. Also in the example you give, isn't that more of a syntax issue? Since JS is dynamic you could imagine the syntax <SomeInterface>someObject) as passing the instance to an interface function that returns a new object that you could call someMethod on.

What I am trying to get at is that JS with its prototypes is more like those languages at the bottom of that article that "do method lookup by name" and we should use that to our advantage. For instance, the type before (<T>someObject) is irrelevant in our case since we only use the classId anyway. This lets us simplify the virtual lookup in that implementing interfaces becomes merely a compile-time check (just a type, dont' have a classId).

@MaxGraey

One additional aspect is that we should abstract these internals in a way that one can still call virtual methods from the outside normally. For example, in a case like

export abstract class Foo { // or even an interface
  abstract bar(): i32;
}
class Baz extends Foo {
  bar(): i32 { return 42; }
}
export var foo = new Baz();

one might want to call Foo#bar(foo) externally without knowing that it is a Baz. In this case we'd have to generate a method Foo#bar anyway that then performs the lookup, so the method could as well be the virtual table itself, making this somewhat similar to CRTP again.

function Foo#bar(this): i32 {
  switch (LOAD_RT_ID(this)) {
    case Baz_ID: return Baz#bar(this);
  }
  return unreachable();
}
function Baz#bar(this): i32 {
  return 42;
}

Notice how this doesn't even have to call_indirect. Maybe that's what @MaxGraey meant initially and I just didn't get it yet, if I'm not missing something again.

My current method in #862 still allows for calling the method directly and passing the instance, but does bury the class lookup in the virtual method. So it's a simple change to move that logic into each method.

Little bit about de-virtualization in LLVM:
https://llvm.org/devmtg/2018-10/slides/Padlewski-Pszeniczny-Sound%20Devirtualization.pdf

Different approaches for dynamic dispatching with benchmarks (if-else sequence, binary tree dispatch, switch case and vtable):
https://hal.inria.fr/inria-00072218/document

fixed by #862

@dcodeIO

@dcodeIO @MaxGraey

In #862 I just added a @virtual decorator which allows virtual overloading. In the current test file for method overloading it mentions that in the future all overloading will be virtual.

Is this still the case? If so, it wouldn't be that hard to change now, but I think using the decorator approach allows for more flexibility.

@MaxGraey

After some feedback from @MaxGraey I make all overloaded methods virtual by default and as @final decorator to prevent it.

Figured that another issue here is that overloading instance fields/properties is problematic.

interface Foo {
  foo: i32;
}

Both a field and a property implementation meet the criteria as of TS, but in AS we are compiling these differently. Field accesses are just loads and do not retain for efficiency purposes (can assume that there's at least one remaining ref), while property getters do retain as these are functions (can return something dropping to RC=0). Must be taken into account by either enforcing overriding with properties or doing some magic under the hood.

Navigation Menu

Repository navigation

A mechanism for virtual overloads #693

11 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

A mechanism for virtual overloads #693

Description

Activity

MaxGraey commented on Jun 27, 2019

bowenwang1996 commented on Jun 27, 2019

dcodeIO commented on Jun 28, 2019

willemneal commented on Jul 2, 2019

dcodeIO commented on Jul 2, 2019

willemneal commented on Jul 4, 2019

dcodeIO commented on Jul 6, 2019

willemneal commented on Jul 9, 2019

dcodeIO commented on Jul 9, 2019

MaxGraey commented on Sep 15, 2019

MaxGraey commented on Sep 15, 2019

dcodeIO commented on Sep 15, 2019

MaxGraey commented on Sep 15, 2019

11 remaining items

MaxGraey commented on Sep 22, 2019

willemneal commented on Sep 22, 2019

dcodeIO commented on Sep 22, 2019

willemneal commented on Sep 22, 2019

dcodeIO commented on Sep 22, 2019

dcodeIO commented on Sep 23, 2019

willemneal commented on Sep 23, 2019

MaxGraey commented on Sep 24, 2019

MaxGraey commented on Nov 6, 2019

willemneal commented on Dec 9, 2019

willemneal commented on Dec 11, 2019

willemneal commented on Dec 13, 2019

dcodeIO commented on Jan 26, 2020

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions