[wasm-gc] Optimizing trait polymorphism memory usage by using static tables

[jayphelps]

trait SomeTrait {
  callback(Self) -> Unit
}

struct Value {}

impl SomeTrait for Value with callback(self) -> Unit {
  println("Value::callback")
}

fn example(value: &SomeTrait) -> Unit {
  value.callback()
}

(type $SomeTrait
  (sub
   (struct
    (field  (ref $SomeTrait.method_0)))))

(type $Value.as_SomeTrait
 (sub
  $SomeTrait
  (struct
   (field  (ref $SomeTrait.method_0))
   (field  (ref $Value)))))

Today when using Trait polymorphism (like defining a parameter as &Value above) the compiler generates a new struct that's effectively a run-time vtable every time a struct that implements that trait is passed into such a function, like this:

(call $jayphelps/example/main.example
   (struct.new $Value.as_SomeTrait
    (ref.func $@jayphelps/example/main.SomeTrait::@jayphelps/example/main.Value::callback.dyncall_as_SomeTrait)
    (local.get $value/123)))))
(; call it again or any other function which relies on trait polymorphism ;)
(call $jayphelps/example/main.example
   (struct.new $Value.as_SomeTrait
    (ref.func $@jayphelps/example/main.SomeTrait::@jayphelps/example/main.Value::callback.dyncall_as_SomeTrait)
    (local.get $value/123)))))

In this example, if you pass the struct value to multiple functions a new intermediate vtable struct is created each time. It's somewhat contrived given there's only one method, but hopefully it demonstrates the point cause "at scale" in complex apps with lots of methods this could add up.

Off hand I don't think there's a way around having this separate struct since Wasm GC doesn't (yet) support subtyping multiple structs, but I'm curious if this can be memory optimized by placing all the functions in a statically defined Wasm (table), avoiding the overhead both of the extra allocations to store the functions? That table's index is then what you put in $Value.as_SomeTrait.

That said, this might come at the cost of CPU performance as when you need to use call_indirect, which incurs bounds/type checks and lookup. But I'm not sure if call_ref is optimized beyond call_indirect yet in most VMs or not. One might argue memory is cheap these days, and to error on the side of better CPU perf. I guess you could also define the vtable still using a struct with ref.funcs but as a global, which would sort of be a middle ground perhaps. Faster calls, less redundant memory, but still some small overhead with the global lookup.

So I guess that leaves me more just curious what your thinking is around this. Mostly out of professional curiosity—you all have more compiler experience than I do, so I'd appreciate learning if this was deliberate, and why. I noticed this because my code is heavily relying on this feature, so I quickly saw a lot of redundant allocations when examining the build.

[Guest0x0]

IMO an extra layer of indirection is unavoidable if we share the table. However since MoonBit performs monofy, it is actually fine for different traits to have different layouts. For example we could perform the sharing only for objects with a lot of methods. That said, trait objects aren't intended for performance critical code anyway. Polymorphism or enum should be used for maximum performance. So sharing is probably the way to go in the future.

There are two ways to perform the sharing:

• just allocate a static table object in memory. There's no need for extra sub typing here, since pointer to the vtable is just a regular field of the object
• use table, as you have mentioned. Probably one table for each Trait::meth, so that wasm-gc would be happy with the type & we can use a single index for all methods. This approach as the extra benefit that the table index can be used for runtime cast/reflection in the future, if desired

The layout won't be changed until we settle down on our decision on downcast/reflection, though.

[jayphelps]

That said, trait objects aren't intended for performance critical code anyway.
Is this universally true, or just what you all expect for typical "application" style code? I'm using Moonbit to create a relatively complex runtime for a dataflow language (somewhat similar to Lucid, but in actuality very different), and I'm relying on traits extensively. Thankfully, though, I'm largely only paying the cost of creating these vtables at startup and when control flow changes. When the data flow graph is stable and flowing there aren't any.

Asking because I'm wondering if it's my use case that is just unique, or if I'm fundamentally misunderstanding how to idiomatically use Moonbit; totally possible, ignorantly trying to do things similar to how I would in other languages.

[Guest0x0]

Is this universally true, or just what you all expect for typical "application" style code? I'm using Moonbit to create a relatively complex runtime for a dataflow language (somewhat similar to Lucid, but in actuality very different), and I'm relying on traits extensively. Thankfully, though, I'm largely only paying the cost of creating these vtables at startup and when control flow changes. When the data flow graph is stable and flowing there aren't any.

The exact meaning here:

• if you care about performance, use polymorphism if possible
• trait objects always come with boxing and indirect call, in some scenario this is undesirable (e.g. hot loop of numeric computation)
• if open-world extensibility is not needed, enum would be slightly faster than trait objects
• we may trade some performance for richer functionality, for example perform table sharing and allow down-casting

Of course there are cases left where trait objects are necessary, and we will still try to optimize the performance of trait objects when possible.

[jayphelps]

I don't understand your distinction between "trait object" and "polymorphism". Traits in Moonbit enable its own kind of polymorphism, no?

[Guest0x0]

By polymorphism I mean [X : Trait]. Trait objects has its own unique expressiveness, but there are also some overlap of usage between [X : Trait] and &Trait. When feasible, [X : Trait] will always have better performance compared to &Trait