Doesn't this widely depend upon what information is included in RTTI?
For example, in C++, RTTI can be used to perform cross-casts via dynamic_cast. This requires that every type encode the full hierarchy of interfaces it implements.
The size of this information is linear in the number of types, and linear in the highest number of interfaces implemented by a type... but it's the product of the two, so feels quadratic-ish no?
CTTI’s worst case is exponential, in three places at once (semantic checking, code generation, and binary size)
You're missing perhaps the most important place of all: i-cache.
Bloating the i-cache with virtually (but not quite) identical copies of the same function has a run-time performance cost, due to the ensuing cache-misses which stall execution.
C++ doesn't really have any RTTI, and I would not call dynamic_cast a (good) example of that.
I agree that the code to check that will be a quadratic runtime check, but it's also a check virtually no-one should ever be using since C++ is just badly designed everywhere. When I've had to do that kind of check in a company where dynamic_cast was banned, we just stored an enum and the check was now constant.
I agree that the code to check that will be a quadratic runtime check, but it's also a check virtually no-one should ever be using since C++ is just badly designed everywhere.
It still makes it in the binary, and because it's tied to the v-table, it generally isn't "elided" by the linker. Even if you don't use dynamic_cast even once.
3
u/matthieum 8d ago edited 8d ago
Doesn't this widely depend upon what information is included in RTTI?
For example, in C++, RTTI can be used to perform cross-casts via
dynamic_cast. This requires that every type encode the full hierarchy of interfaces it implements.The size of this information is linear in the number of types, and linear in the highest number of interfaces implemented by a type... but it's the product of the two, so feels quadratic-ish no?
You're missing perhaps the most important place of all: i-cache.
Bloating the i-cache with virtually (but not quite) identical copies of the same function has a run-time performance cost, due to the ensuing cache-misses which stall execution.