哪个执行速度更快？用N个派生类型进行vtable查找，或者用N个元素查找std :: map查找？

#include <iostream> 
#include <map> 
#include <ctime> 

struct Base { virtual void foo() {} }; 
struct A : Base { void foo() {} }; 
struct B : Base { void foo() {} }; 
struct C : Base { void foo() {} }; 

A* protoA = new A; B* protoB = new B; C* protoC = new C; 

enum Tag {a, b, c}; 

std::map<Tag, Base*> protoMap = { {a, protoA}, {b, protoB}, {c, protoC} }; 

void goo(Base* base) {base->foo();} 

void hoo(Tag tag) {protoMap[tag]->foo();} 

struct Timer { 
    const std::clock_t begin; 
    Timer() : begin (std::clock()) {} 
    ~Timer() { 
     const std::clock_t end = std::clock(); 
     std::cout << double (end - begin)/CLOCKS_PER_SEC << " seconds." << std::endl; 
    }; 
}; 

int main() { 
    const long N = 10000000; 
    { 
     Timer timer; 
     for (int i = 0; i < N; i++) 
      goo(new C); // using vtable 
    } // 0.445 seconds. 
    { 
     Timer timer; 
     for (int i = 0; i < N; i++) 
      hoo(c); // using map 
    } // 0.605 seconds. 
    std::cin.get(); 
}

但我的测试只使用三个派生类，我不知道如何定义数千个派生类来进行正确的基准测试。有没有人知道答案已经这样，我不必考虑如何运行更好的测试？哪个执行速度更快？用N个派生类型进行vtable查找，或者用N个元素查找std :: map查找？

我现在处于一种可以轻松使用地图的情况，但试图用vtable查找来提高性能时，需要重新设计我已有的许多东西（向类中添加一个新的数据成员，定义一个新的构造函数，实现访问者模式，等等......）。

来源

2014-11-09 prestokeys

你正在比较苹果和橘子;这个“标签”方法如何在现实的多态场景中提供帮助？ – 2014-11-09 01:14:15

@Oliver。因为我处于可以轻松使用地图的情况，但是尝试通过vtable查找来提高性能，需要重新设计我已有的许多内容（向类添加新的数据成员，定义新的构造函数，实现访问者模式等）。 – prestokeys 2014-11-09 01:17:01

我认为vtable速度更快，并且是唯一正确的路径，尽管在我的具体情况下我很困难。 – prestokeys 2014-11-09 01:25:37

毫无疑问，最快的方法是vtable。

实验：

你必须在类似条件下运行基准。为vtable基准测试的每次调用分配一个新元素是不合理的，但不要在map方法中分配任何东西。

我使用vtable方法使用指向已分配元素的指针运行测试。我得到了16毫秒的vtable和78毫秒的地图方法。

如果你想进一步和集会比较第1000个派生物，你必须使用递归模板。

解释结果：

V表查找一般使用对象的fixed offset in the vtable，而不是一个搜索。因此，即使有1000个派生项，您在O（1）中也会有一个持续的反应时间。

该地图需要对密钥执行昂贵的搜索操作，即O（log（n））。

补充说明：

，你提议不会在现实生活中的工作，因为你总是调用成员函数的一个单独的预定目标的地图实现：您存储在地图中的一个。虚拟功能将与家庭的任何对象一起工作。

来源

2014-11-09 01:52:20 Christophe

是的，谢谢。我使用模板运行我的测试来创建许多类。 vtable远远胜出，其时间不会随着派生类的数量而改变。 – prestokeys 2014-11-09 01:54:22

哪个执行速度更快？用N个派生类型进行vtable查找，或者用N个元素查找std :: map查找？

回答

相关问题