Specialise generic functions and types over kinds/shapes

[yorickpeterse]

Description

Generic functions are currently compiled in a subpar manner. #508 keeps this approach in an attempt to keep the scope of changes from expanding even more, but it's not something I want to keep in the long term.

The usual approach is to specialise generic types/functions across types, essentially copy-pasting these types and substituting the generic type parameters with the real types. This can result in great runtime performance, but also slows down compile times drastically; especially paired with the already slow LLVM. In case of Inko this would also be a waste, as a lot of data will be addressed through pointers and thus have the same memory layout (e.g. Array[User] and Array[String] would have the same layout).

Instead, I propose we specialise across kinds/shapes. These shapes specify both the memory layout, and how to handle aliasing. We'd start out with the following shapes:

• T: pointer sized, owned
• Int: 64 bits unboxed, passed around on the stack
• Float: 64 bits floating point, unboxed, passed around on the stack using the appropriate floating point registers
• ref T: just a pointer memory wise, but creating/dropping aliases involves changing the reference count
• T where T is an atomic value (e.g. String): basically the same as ref T, but using atomic reference counting, and decrements follow an extra check to drop the value when the ref count is zero

Splitting generic code into these different shapes means we can get rid of pointer tagging, allow unboxed Int and Float values, and don't need to perform runtime checks to figure out how to create/destroy aliases. In addition, the compiler is free to turn types into shapes if deemed beneficial, allowing for more optimisations but without compile times going down the drain as a default.

A challenge here is casting Int and Float to traits objects. Such values are typed as T and thus treated as a heap object. This requires that we box Int and Float upon a cast.

In addition, generic types containing Int and Float can't be compatible with generic types containing traits implemented by Int and Float (e.g Array[Int] isn't compatible with Array[ToString]), because we'd be passing unboxed values where boxed values are expected. This is fine when passing e.g. Int directly to a ToString, as in such a case the conversion is trivial.

Similarly, if we have a value typed as a trait it might need atomic reference counting, such as when a function takes a ToString and is given a String. What we probably need to do is insert a runtime check that checks the object header, and chooses the right strategy based on whether the value needs atomic reference counting or not. This can be avoided if we statically know the trait isn't implemented by any atomic types.

Finally, for this to work we'll need to implement Array in Inko, such that the compiler/generated code has control over the memory layout, instead of this being dictated by the runtime library. This is outlined in #349.

The end result is that we can get rid of all runtime bookkeeping for generics, improve performance, but without dramatically increasing compile times.

Related work

https://github.com/golang/proposal/blob/master/design/generics-implementation-gcshape.md

Depends on

• Consider implementing ByteArray and Array in Inko with a set of primitive instructions #349
  • Type-safe C FFI #290

[yorickpeterse]

Similarly, if we have a value typed as a trait it might need atomic reference counting, such as when a function takes a ToString and is given a String. What we probably need to do is insert a runtime check that checks the object header, and chooses the right strategy based on whether the value needs atomic reference counting or not. This can be avoided if we statically know the trait isn't implemented by any atomic types.

Instead I think we need to take a different approach:

If an argument is typed as SomeTrait, and this trait is implemented by a type that uses atomic reference counting, we also specialise over the "atomic" shape. Thus, arg: SomeTrait or arg: ref SomeTrait is effectively the same as arg: T / arg: ref T where T: SomeTrait.

Another option is that we simply disallow traits in arguments, and instead force users to go through generics. This would lead to slightly more verbose code, but also keep things consistent. It probably also solves some covariance problems down the line.