哪個執行速度更快？用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查找？

回答

相關問題