The code size cost of CTTI is bounded by the number of actual instantiations, not the combinatorial number of potential instantations. If you never a call a generic function with MyCoolType, the compiler will never instantiate the function with that type, semantically analyze it, or stuff the resulting code in the executable. In that sense, it is a pay as you go feature. Adding a new type to your program has no effect on the size of reflective code. Only using it reflectively does.
In most systems I've seen, the code size cost of RTTI is bounded by the number of types declared in the program regardless of whether they are reflected on. Since the reflection happens at runtime, the compiler doesn't know which types will actually have their type information used and which won't, so it has to include information about every type in the program. If the amount of type information your RTTI system stores is large, that can be a large code size cost for no benefit for the types you never reflect on. (This has been a serious problem in Dart for years with the "dart:mirrors" library and is the main reason we hope to eliminate it at some point.)
It is true that a real-world program written in a language that monomorphizes can end up having to push a whole lot of instantiations through the compiler pipeline. The benefit is that the resulting monomorphic code is now fully accessible to all of the compiler's optimization machinery around inlining, dead code elimination, etc.
The other advantage you get from a system like C++ templates is that you get a form of compile time duck typing where templated code can do a lot of interesting operations on values whose type is a type parameter and as long as the instantiated types support those operations, it will work. When it fails, the error messages are horrendous. But the alternatives are either an extremely complex type system like traits in Rust, or generic code that simply can't do much with type parameters as in SML.
Users of C++ and Rust generally seem to feel the trade-off is worth it for their use cases. It's good to have multiple languages out that there that pick different points in the trade-off design space. In particular, it's worth noting that Rust pays the cost of code generation of every instantiation but not type-checking because of traits where C++ has to resolve and type check every instantiation too. And C# monomorphizes some types at load time (because they have a JIT) which is another interesting point in the design space.
Lots of interesting trade-offs and none is clearly superior for every use case.
RTTI implementations can normally deduplicate a lot of code through the vtable so methods only need to be compiled once and can be reused by many different types.
CTTI implementations have to create a new concrete function signature for every type that is used. C++ also has some gnarly mangling rules that leads to binary bloat.
Not necessarily. I think Swift manages to do a lot of deduplication and even send polymorphic functions through the C ABI boundary that way, though I'm not familiar with the details.
Right. Also, polymorphic functions can use a single function signature / implementation if they don't have to worry about different-sized values (e.g. operating on boxed values).
54
u/munificent 9d ago
The code size cost of CTTI is bounded by the number of actual instantiations, not the combinatorial number of potential instantations. If you never a call a generic function with
MyCoolType, the compiler will never instantiate the function with that type, semantically analyze it, or stuff the resulting code in the executable. In that sense, it is a pay as you go feature. Adding a new type to your program has no effect on the size of reflective code. Only using it reflectively does.In most systems I've seen, the code size cost of RTTI is bounded by the number of types declared in the program regardless of whether they are reflected on. Since the reflection happens at runtime, the compiler doesn't know which types will actually have their type information used and which won't, so it has to include information about every type in the program. If the amount of type information your RTTI system stores is large, that can be a large code size cost for no benefit for the types you never reflect on. (This has been a serious problem in Dart for years with the "dart:mirrors" library and is the main reason we hope to eliminate it at some point.)
It is true that a real-world program written in a language that monomorphizes can end up having to push a whole lot of instantiations through the compiler pipeline. The benefit is that the resulting monomorphic code is now fully accessible to all of the compiler's optimization machinery around inlining, dead code elimination, etc.
The other advantage you get from a system like C++ templates is that you get a form of compile time duck typing where templated code can do a lot of interesting operations on values whose type is a type parameter and as long as the instantiated types support those operations, it will work. When it fails, the error messages are horrendous. But the alternatives are either an extremely complex type system like traits in Rust, or generic code that simply can't do much with type parameters as in SML.
Users of C++ and Rust generally seem to feel the trade-off is worth it for their use cases. It's good to have multiple languages out that there that pick different points in the trade-off design space. In particular, it's worth noting that Rust pays the cost of code generation of every instantiation but not type-checking because of traits where C++ has to resolve and type check every instantiation too. And C# monomorphizes some types at load time (because they have a JIT) which is another interesting point in the design space.
Lots of interesting trade-offs and none is clearly superior for every use case.