避免 dynamic_cast 缓慢的著名解决方案是什么?

5

我需要运行时多态性,所以我使用了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比简单的virtual调用慢了约15倍(使用下面的代码,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%!

1
不要使用dynamic_cast运算符,而应该使用typeid运算符,或者更好的方法是使用虚函数调用。这种运算符的执行时间比虚函数调用要长得多,甚至比typeid运算符还要长。 - Tutankhamen
@casablanca:当然,不过那与我在这里提出的问题完全无关。 - user541686
3
可能是这样,但从您的问题中并不清楚。我仍然认为,如果您需要调用 dynamic_cast 这么多次以至于它会影响性能,那么您可能需要重新审视您的设计。 - casablanca
1
避免 dynamic_cast 缓慢的众所周知的解决方案是什么?不使用它。运行时多态和 dynamic_cast 几乎是相反的概念:多态是能够获取对象的引用并在不关心类型的情况下使用它,而 dynamic_cast 则关心类型,因为您无法通过特征进行多态操作。最好的建议已经由 @casablanca 给出:重新审视设计。如果您正在使用 dynamic_cast,目标不是使其更快,而是将其从设计中删除。 - David Rodríguez - dribeas
1
看一下LLVM的isadyn_cast等,它们对类层次结构施加了限制,并且需要为每个类进行一些手动工作,但效率非常高(只需加载成员并将其与常量进行比较)。这可能有点过度设计,或者限制可能太严格,但仍然非常有趣。 - user395760
显示剩余3条评论
2个回答

3

大多数使用dynamic_cast的情况都可以用双重分派(又称访问者模式)替代。这将涉及两个虚拟调用,但根据您的基准测试,速度仍然比dynamic_cast快7.5倍。


+1,但是如果您无法修改正在访问的类的源代码怎么办?您会为每个类都创建一个包装器吗? - user541686
@Mehrdad:你仍然可以包装/扩展该类以添加访问者支持。 - casablanca
嗯,但是扩展并不总是可行的(或者是一个好主意!),而包装会让你不得不将所有的 foo.bar 改成 wrapper.foo.bar …… 这真的是个好主意吗? - user541686
@Mehrdad:看起来你正在处理一个外部库(因为你提到无法修改它),所以如果你的整个代码库都与该库耦合,那已经是一个问题了。尽管如此,对其进行包装似乎是个好主意,因为这将保护你免受该库未来变化的影响。 - casablanca
嗯,我现在没有处理外部库,因为你可以在问题中看到我能够修改这个类。 :) 但是,是的,我想知道如果将来我处于那种情况下该怎么办,因为这就是问题的意图。那么当我处于那种情况下时,创建一个包装器如何让我免受更改的影响?然后我只需要在任何更改之后更新包装器,而任何非微不足道的更改(新功能或弃用功能)都将要求我在任何情况下都更改其余代码...似乎为每个库制作包装器有点奇怪。 - user541686
@Mehrdad:抱歉,我并不是在字面上使用“wrapper”的意思。通常情况下,您会尽量减少与任何外部库的耦合,因此您需要为应用程序所需的内容创建自己定义良好的接口,而该接口的实现将与库进行通信。如果您做得正确,那么您的其余代码将不受库中更改的影响。 - casablanca

2
您可能会对这个常数时间的实现感兴趣:http://www.stroustrup.com/isorc2008.pdf 此外,请注意在特定约束条件下可以简化许多向上转换 - 例如,如果您不使用多重继承,仅使用浅层继承或以其他方式保证类型没有共同的祖先,则某些评估可以短路,并且无需执行详尽的评估(由dynamic_cast提供)。
像往常一样,针对您的给定用例和实际类层次结构,与供应商的实现进行性能测试。

1
哦,看起来这是一篇很深入的阅读!我会尽快查看,谢谢!+1 - user541686
1
@Mehrdad 我还记得几年前读它时感觉很愉快。不客气。 - justin
1
我想读它,但是我已经整天在读编程的东西了。这个得等到明天了,但我肯定会喜欢它的。 - chris

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接