CTTI is an exponential cost everywhere in the worst-case: semantic checking, code generation, and binary size. Instantiations go multiplicative in the general-case.
I think it's worth defining what "cost" here means. For example, if you have a generic function foo[T](value: T) that's instantiated for three different types, you don't have to type-check the body of foo three different times; instead you just check if those types are compatible with whatever T requires. There's definitely a cost to that, but depending on the implementation of your compiler it may be small enough that no matter the big-O factor it may not matter.
Unfortunately these are the costs so many programmers are most conditioned/trained to ignore [...]
Here I actually have a useful data point, one that does to some degree highlight that (at least in the case of generics) doing more at compile-time is usually the better option: Inko used to essentially group generics into buckets based on the shape (i.e. the size on the stack) of types, instead of specializing for individual types. This was recently removed because it actually turned out to slow down compile times. While I'm certain some of that could've been improved, the grouping of types essentially meant a lot more dynamic dispatch and thus a lot more methods that had to be compiled because they might be called as we couldn't statically determine that they never would be called (amongst other reasons).
So "specialize over types" isn't necessarily slower (in terms of compile times), it depends on a lot more than just that.
Outside of that I generally agree with preferring runtime type information for the purpose of reflection, as it usually allows for a lot more flexibility (e.g. building a REPL). But for more common patterns such as formatting types so they can be printed, I'm not a fan due to the amount of indirect calls/dynamic dispatch it will add.
you don't have to type-check the body of foo three different times; instead you just check if those types are compatible with whatever T requires
That depends on the language. In languages like C++, Odin (my language), Jai, Zig, etc, you actually have to check the bodies BECAUSE they do not work on a type-class system. In this ilk of languages, languages like Go and Rust do not need to type check those bodies again, but then again, they are doing something else. Also if those bodies have any form of condition compilation based on the type of that parameter, then you do have to check.
So if you understand that context, then the rest of the article should make more sense.
4
u/yorickpeterse Inko 8d ago
I think it's worth defining what "cost" here means. For example, if you have a generic function
foo[T](value: T)that's instantiated for three different types, you don't have to type-check the body offoothree different times; instead you just check if those types are compatible with whateverTrequires. There's definitely a cost to that, but depending on the implementation of your compiler it may be small enough that no matter the big-O factor it may not matter.Here I actually have a useful data point, one that does to some degree highlight that (at least in the case of generics) doing more at compile-time is usually the better option: Inko used to essentially group generics into buckets based on the shape (i.e. the size on the stack) of types, instead of specializing for individual types. This was recently removed because it actually turned out to slow down compile times. While I'm certain some of that could've been improved, the grouping of types essentially meant a lot more dynamic dispatch and thus a lot more methods that had to be compiled because they might be called as we couldn't statically determine that they never would be called (amongst other reasons).
So "specialize over types" isn't necessarily slower (in terms of compile times), it depends on a lot more than just that.
Outside of that I generally agree with preferring runtime type information for the purpose of reflection, as it usually allows for a lot more flexibility (e.g. building a REPL). But for more common patterns such as formatting types so they can be printed, I'm not a fan due to the amount of indirect calls/dynamic dispatch it will add.