Известное решение, позволяющее избежать медлительности dynamic_cast?

Мне нужен был полиморфизм во время выполнения, поэтому я использовал dynamic_cast.
Но теперь у меня были две проблемы: dynamic_cast был крайне медленным! (Прокрутите вниз для эталона.)

Короче говоря, я решил проблему таким образом, используя static_cast:

struct Base
{
    virtual ~Base() { }
    virtual int type_id() const = 0;

    template<class T>
    T *as()
    { return this->type_id() == T::ID ? static_cast<T *>(this) : 0; }

    template<class T>
    T const *as() const
    { return this->type_id() == T::ID ? static_cast<T const *>(this) : 0; }
};

struct Derived : public Base
{
    enum { ID = __COUNTER__ };  // warning: can cause ABI incompatibility
    int type_id() const { return ID; }
};

int main()
{
    Base const &value = Derived();
    Derived const *p = value.as<Derived>();  // "static" dynamic_cast
}

Но я, конечно, не первый, кто столкнулся с этой проблемой, поэтому я подумал, что, возможно, стоит спросить:

Вместо того, чтобы придумывать домашнее решение, подобное этому, есть ли хорошо известный шаблон/библиотека, который я могу использовать для решения этой проблемы в будущем?


Образец бенчмарка

Чтобы понять, о чем я говорю, попробуйте приведенный ниже код: dynamic_cast был примерно в 15 раз медленнее, чем простой вызов virtual на моем компьютере (110 мс против 1620 мс с кодом ниже):

#include <cstdio>
#include <ctime>

struct Base { virtual unsigned vcalc(unsigned i) const { return i * i + 1; } };
struct Derived1 : public Base 
{ unsigned vcalc(unsigned i) const { return i * i + 2; } };
struct Derived2 : public Derived1
{ unsigned vcalc(unsigned i) const { return i * i + 3; } };

int main()
{
    Base const &foo = Derived2();
    size_t const COUNT = 50000000;
    {
        clock_t start = clock();
        unsigned n = 0;
        for (size_t i = 0; i < COUNT; i++)
            n = foo.vcalc(n);
        printf("virtual call: %d ms (result: %u)\n",
            (int)((clock() - start) * 1000 / CLOCKS_PER_SEC), n);
        fflush(stdout);
    }
    {
        clock_t start = clock();
        unsigned n = 0;
        for (size_t i = 0; i < COUNT; i++)
            n = dynamic_cast<Derived1 const &>(foo).vcalc(n);
        printf("virtual call after dynamic_cast: %d ms (result: %u)\n",
            (int)((clock() - start) * 1000 / CLOCKS_PER_SEC), n);
        fflush(stdout);
    }
    return 0;
}

Когда я просто удаляю слово virtual и заменяю dynamic_cast на static_cast, я получаю время выполнения 79 мс, поэтому виртуальный вызов медленнее статического вызова только примерно на 25%!


person user541686    schedule 10.09.2012    source источник
comment
Вместо оператора dynamic_cast используйте оператор typeid или, что лучше, вызов виртуальной функции. Такой оператор может занимать заметно больше времени, чем вызов виртуальной функции, а также дольше, чем оператор typeid.   -  person Tutankhamen    schedule 10.09.2012
comment
вместо dynamic_cast используйте вызов виртуальной функции Хм, вы случайно не читали вопрос?   -  person user541686    schedule 10.09.2012
comment
Очевидный вопрос: зачем вам dynamic_cast? В большинстве случаев вы можете полностью отказаться от приведения типов, улучшив дизайн, но то, как это будет сделано, зависит от конкретной проблемы, которую вы пытаетесь решить.   -  person casablanca    schedule 10.09.2012
comment
@casablanca: Конечно, хотя это полностью ортогонально моему вопросу здесь.   -  person user541686    schedule 10.09.2012
comment
@Mehrdad: Может быть, но из вашего вопроса неясно, так ли это. Я все еще думаю, что если вы вызываете dynamic_cast так много раз, что это действительно влияет на производительность, вам, возможно, придется пересмотреть свой дизайн.   -  person casablanca    schedule 10.09.2012
comment
@casablanca: Хорошо, спасибо за совет.   -  person user541686    schedule 10.09.2012
comment
Хорошо известное решение, позволяющее избежать медлительности dynamic_cast? Не использовать его. Полиморфизм времени выполнения и dynamic_cast — почти противоположные понятия: полиморфизм — это возможность получить ссылку на объект и использовать его, не заботясь о типе, dynamic_cast — это забота о типе, потому что вы не можете полиморфно добраться до функции. Лучший совет уже дала @casablanca: пересмотрите дизайн. Если вы используете dynamic_cast, цель состоит не в том, чтобы сделать его быстрее, а в том, чтобы удалить его из дизайна.   -  person David Rodríguez - dribeas    schedule 10.09.2012
comment
@DavidRodríguez-dribeas: Хорошо, я не думал об этом таким образом ... действительно, теперь, когда я думаю об этом таким образом, это выглядит как противоположность полиморфизму. :) Спасибо, что указали на это.   -  person user541686    schedule 10.09.2012
comment
Взгляните на LLVM isa, dyn_cast и т. д., которые накладывают ограничения на иерархию классов и выполняют некоторую ручную работу для каждого класса. , но смехотворно эффективен (просто загружает элемент и сравнивает его с постоянным IIRC). Это может быть излишним, или ограничения могут быть слишком жесткими, но тем не менее это довольно интересно.   -  person    schedule 10.09.2012


Ответы (2)


В большинстве случаев dynamic_cast можно заменить двойной отправкой (также известной как шаблон посетителя). Это составило бы два виртуальных вызова, что по вашему тесту все еще в 7,5 раз быстрее, чем dynamic_cast.

person casablanca    schedule 10.09.2012
comment
+1, а как насчет того, что вы не можете изменить исходный код посещаемого вами класса? Вы делаете обертку для каждого отдельного класса? - person user541686; 10.09.2012
comment
@Mehrdad: вы все равно можете обернуть/расширить класс, чтобы добавить поддержку посетителей. - person casablanca; 10.09.2012
comment
Хм, но расширение не всегда возможно (или это хорошая идея!), а обертывание заставляет вас менять все ваши foo.bar на wrapper.foo.bar... это действительно хорошая идея? - person user541686; 10.09.2012
comment
@Mehrdad: Кажется, вы имеете дело с внешней библиотекой (поскольку вы упомянули, что не можете ее изменить), поэтому, если вся ваша кодовая база связана с этой библиотекой, это уже проблема. В любом случае обертывание кажется хорошей идеей, потому что это защитит вас от будущих изменений в этой библиотеке. - person casablanca; 10.09.2012
comment
Ну, я не имею дело с внешней библиотекой прямо сейчас, так как вы можете видеть в вопросе, что я смог изменить класс здесь. :) Но да, я спрашиваю, что я мог бы сделать, если бы я оказался в такой ситуации в будущем, поскольку это и было целью вопроса. Итак, когда я нахожусь в такой ситуации, как создание оболочки защищает меня от изменений? Тогда мне просто нужно обновить оболочку после любых изменений, и любое нетривиальное изменение (новые или устаревшие функции) в любом случае потребует от меня изменения остальной части кода... кажется странным делать оболочку для каждой библиотеки. - person user541686; 10.09.2012
comment
@Mehrdad: Извините, я не имел в виду обертку в чистом виде. В общем, вы стремитесь уменьшить связь с любой внешней библиотекой, поэтому вы должны создать свой собственный четко определенный интерфейс для того, что требуется вашему приложению, и реализация этого интерфейса будет общаться с библиотекой. Если вы сделаете это правильно, остальная часть вашего кода будет невосприимчива к изменениям в библиотеке. - person casablanca; 10.09.2012

Вас может заинтересовать эта реализация постоянного времени: http://www.stroustrup.com/isorc2008.pdf

Также обратите внимание, что многие восходящие приведения могут быть упрощены при определенных ограничениях — например, если вы не используете множественное наследование, используете только неглубокое наследование или иным образом гарантируете, что тип не будет иметь общих предков, некоторые вычисления могут быть сокращены и исчерпывающий оценка (как предусмотрено dynamic_cast) не требуется.

Как обычно, профилируйте свою реализацию в сравнении с реализацией вашего поставщика для вашего конкретного варианта использования и реальной иерархии классов.

person justin    schedule 10.09.2012
comment
О черт, это похоже на интенсивное чтение! По возможности посмотрю, спасибо! +1 - person user541686; 10.09.2012
comment
@Mehrdad, я помню, как наслаждался этим, когда читал его несколько лет назад. пожалуйста - person justin; 10.09.2012
comment
Я хочу это прочитать, но я весь день читаю про программирование. Этого придется подождать до завтра, но я уверен, что оно мне понравится. - person chris; 10.09.2012