Временная сложность операций typeid и dynamic_cast в C++

Если оставить в стороне все опасения по поводу необходимости использования typeid и dynamic_cast и их сомнительного влияния на обслуживание кода, есть ли какая-либо информация о производительности этих двух механизмов самоанализа динамического типа? В статье Википедии о RTTI утверждается, что:

Использование typeid в неполиморфном контексте часто предпочтительнее, чем dynamic_cast‹class_type› в ситуациях, когда нужна только информация о классе, потому что typeid всегда является процедурой с постоянным временем, тогда как dynamic_cast может потребоваться пройти через решетку производных классов. своего аргумента во время выполнения.

Однако цитата не приводится. Поэтому я хотел спросить, верно ли это утверждение и следует ли определенно предпочесть один из этих двух механизмов с точки зрения производительности другому. Мне не удалось найти информацию о каких-либо ограничениях на временную сложность этих операций.


c++ time-complexity rtti dynamic-cast typeid
person janekb04    schedule 14.05.2021    source источник
comment
Возможно, взгляните на cppreference.com: оператор typeid: При применении к выражению полиморфного типа оценка выражения с идентификатором типа может повлечь за собой накладные расходы во время выполнения (поиск в виртуальной таблице), в противном случае выражение с идентификатором типа разрешается во время компиляции.   -  person Scheff's Cat    schedule 14.05.2021
comment
Спасибо за цитату. Для меня это предполагает, что сложность постоянна, поскольку поиск в vtable будет всего лишь парой разыменований указателя, но это явно не указано, так ли это на самом деле.   -  person janekb04    schedule 14.05.2021
comment
Похоже на то: возня в Compiler Explorer   -  person Scheff's Cat    schedule 14.05.2021
comment
Хотя, может быть, сравнение не совсем корректное. С помощью typeid вы можете проверить определенный тип, но не совместимость типа (как вы могли бы сделать с dynamic_cast): Counter Пример в Compiler Explorer   -  person Scheff's Cat    schedule 14.05.2021
comment
Хотя мои навыки чтения сборки не очень хороши, если я правильно понимаю, в случае typeid операция, похоже, реализована как сравнение указателей между указателями (хранящимися в vtable) на соответствующие объекты std::type_info. Clang даже оптимизирует его. Между тем, dynamic_cast вызывает непрозрачную функцию __dynamic_cast с std::type_info в качестве аргументов, поэтому трудно сказать, как ее производительность сравнивается с производительностью typeid, не зная реализации. Хотя, конечно, сам вызов функции уже является накладным, чего не происходит с typeid.   -  person janekb04    schedule 14.05.2021
comment
Я тоже не читаю ассемблер плавно, но пришел к такому же выводу. Учитывая, что dynamic_cast может следовать дереву наследования, я предполагаю, что он делает немного больше, чем просто сравнивает два указателя vtable.   -  person Scheff's Cat    schedule 14.05.2021
comment
Кажется, что type_info не обязательно должно быть таким дешевым. Этот вопрос говорит о реализациях, использующих strcmp: stackoverflow.com/questions/49773686/ . Этот файл libstdc++, кажется, подтверждает: gcc.gnu.org /onlinedocs/gcc-7.5.0/libstdc++/api/ .   -  person janekb04    schedule 14.05.2021

Ответы (1)


arrow_upward
1
arrow_downward

Стандарт языка не предъявляет никаких требований к сложности той или иной операции. Таким образом, утверждение, которое вы цитируете, не подкреплено спецификацией. Предположительно, это основано либо на том, как может быть реализована функциональность, либо на том, как она была реализована на практике.

Большая проблема с заявлением о предпочтительности заключается в том, что совершенно неясно, как dynamic_cast можно использовать даже в неполиморфном контексте.

Если вы используете объектно-ориентированный динамический полиморфизм, то вам следует отдать предпочтение виртуальным функциям.

person eerorika    schedule 14.05.2021