The cost/benefit of virtual functions and interfaces

In the case where different concrete types need to interact, like in the list of list examples you mentioned, you can simply instantiate the meta-type with a type erasure. Since the current std’s Allocator is already a type erasure, you could have something like this:

pub fn List(comptime T: type, comptime Allocator: type) type;

Then the concrete type is instantiated like this:

const Element = List(i32, std.mem.Allocator);
const ConcreteList = List(Element, MyConcreteAllocator);

The top-level list uses an allocator directly, but the elements use a runtime determined allocator. This allows users to pay only for what they need. When they need the runtime polymorphism, they get can get it (and pay for it), by using the indirection through std.mem.allocator. Those who don’t need the indirection, like the top-level list, use whatever allocator they want directly, without paying the cost of indirection. This technique also allows us to avoid binary size explosion, as there are only two instantiations of the List, one with the the sts.mem.Allocator type erasure and one with the concrete allocator, even if the individual elements use a lot of other allocators.

3 Likes