Virtual call optimizations

[jemc]

There are a variety of performance optimizations we can make to the virtual call system, which are related enough that they can probably be tackled together:

• Reduce the size of virtual tables by avoiding including methods in it unless a call site for that method was reached that:

  • Calls it via an abstract type like a :trait
  • Calls it via a union type (e.g. calling ptr on a (Bytes'box | String'box) variable)
  • Calls it as an asynchronous behavior (all actor message numbers need the virtual table)

• Automatic specialization of functions (in --release mode only, since it's likely to be expensive)

  • When argument types of a call site are more specific than the parameter types,
    • Create an internal pseudo-reification of that function with the more specific parameter types
    • Continuing an analysis similar to today's reach analysis, but with the more specific pseudo-reifications
  • Each variable and each call site should be marked with its new more specific pseudo-type
    • This analysis will be consumed by CodeGen to create more specific LLVM code,
    • which can hopefully avoid a lot of virtual calls and avoid "boxing" a lot of :struct/:numeric values
  • Note that this more specific analysis should also feed into the optimization mentioned above
    • we should avoid creating virtual table entries if the pseudo-reifications have no virtual call sites for it

EDIT 2022-04-01:

• Automatic elision of single-concrete abstract types
  • If in the reachable program there is only one concrete type that is a subtype of a given abstract type,
    • Then we can treat every usage of the abstract type as if it referred to the single concrete type instead
  • Note that this would be useful for platform-specific implementations of platform-agnostic trait surfaces
    • For example, if we separated TCP.Engine into concrete types TCP.Engine.Posix and TCP.Engine.Windows that both fulfill the same trait, and guard their creation with platform-specific conditionals, then the compiler should be smart enough to devirtualize all of the abstract calls into concrete ones.

[jasoncarr0]

One solution to prevent code blowup on Bullet 1 is via user input. Not perfect but GHC uses {-# SPECIALIZE term :: type #-} pragmas to allow the user to ensure specialization in certain cases.

[jemc]

Yes, that's a good callout. It's something I have thought about before but forget to mention here in the ticket.

We should have some kind of heuristic/threshold indicating when it's expected to be better to specialize vs not doing so. Perhaps allowing the threshold to be tunable at compile time.

And then as you mention, we should have a way to declare a guarantee that a certain critical path needs to be fully specialized or fail at compile time if that's not possible.

[jemc]

Today I added another class of optimization to the ticket description: "Automatic elision of single-concrete abstract types"