通過直接內聯代碼實現更快的繼承

我想出了一種替代switch語句的虛擬表的方法（不一定是新的）。這種方法允許以增加內存爲代價來內聯虛函數。通過直接內聯代碼實現更快的繼承

而不是使用查表，一種開關的使用

switch (objecttype) 
{ 
    case objectA: inlined virtual function call for foo from objectA; break; 
    case objectB: inlined virtual function call for foo from objectB; break; 
    case objectC: inlined virtual function call for foo from objectC; break; 
    default: vtable call; 
}

因此，而不是使用指針查找和撥打電話，一比較就完成了。內聯代碼可以爲已知類完成。

爲了使這個工作正常（避免超過只是函數調用），對象需要存儲它們的類型。類型需要是順序的。

例如：

class A 
{ 
    ushort objectType; // internal id, say for class A it is 1000 
    ushort objectInc; // internal. represents a sort of offset into the jump table 
} 

class B : A 
{ 
    ushort objectInc; // one more than A's objectInc, has the same objectType 
} 

etc...

然後switch語句可以做成一個有效的跳錶上比較objectType（確保它是正確的），並使用objectInc和代碼大小直接跳轉到虛擬功能的代碼（而不是一堆比較）。

據我可以告訴這個方案的缺點是更多的內存（更大的類和更多的內聯函數）和更多的編譯器複雜性，但虛擬函數可以直接內聯（整個switch語句可以），所以沒有包裝調用。由於幾次比較和跳轉（這是O(1)），唯一的額外開銷應該是額外的幾個週期。

有沒有人有任何有用的意見，表現這樣的計劃，爲什麼它沒有使用（我敢肯定我不是第一個想到這一點）？我認爲這將是相當有效的，除了由於比較可能導致緩存失效，但我認爲對於基類而言，它可以在直接內聯方法調用的幾個週期內完成。

順便說一句，表可以看作是每個對象派生的內聯虛函數調用列表。

假設我們有以下幾點：

class A 
{ 
    void foo(); 
} 

class B : A 
{ 
    override void foo(); 
} 

class C : A 
{ 
    override void foo(); 
} 


A a = new C(); 
a.foo();   // but calls fooWrap 


/// internal 
void fooWrap(A a) 
{ 
    switch(a.Type) 
    { 
     case A: a.foo(); break; // A.foo() can be inlined here 
     case B: b.foo(); break; // B.foo() can be inlined here 
     case C: c.foo(); break; // C.foo() can be inlined here 
     default: // use vtable lookup, a's type is not known at compile time 
    } 
}

（通常fooWrap將是虛函數表查找）

現在fooWrap可以直接過內聯在這種情況下，調用foo的成本僅僅是switch語句，它可以通過使用高效的跳轉列表進一步優化。

來源

2013-08-16 user2541029

我會認爲這是效率較低，因爲它需要比較或跳轉表或任何其他方式，而通過vtable的間接方法調用是快速的：vtable中的偏移量可以在調用中硬編碼，間接方法調用是在大多數處理器上可作爲直接機器操作。

此外，每次將另一個後代添加到系統時，您的方法都需要重新編譯。因此，對於允許在應用程序運行時從互聯網加載代碼的系統（如Java或.net），運行時可能需要重新編譯某些代碼。說實話，這已經完成，以取消一些優化，但這只是一個更多的情況，你將不得不這樣做。關於「對象將不得不存儲他們的類型」：在.net和Java中，情況已經如此：每個對象都包含一個指向其類定義的指針，其中包含vtable。因此，每個類只有一個vtable，而不是每個對象。

來源

2013-08-16 16:22:34 FrankPl

1.跳轉表將只需要一個比較，以驗證的對象是正確的，它可以假定如此，所以沒有分支通常取。如果調用是基類，那麼它也不需要任何跳轉。 2.不需要重新編譯。默認情況下使用vtable。 – user2541029

比無條件跳轉（間接函數調用在某種程度上），比較通常更昂貴（通常至少有兩條機器指令，如果cpu的分支預測錯誤，性能可怕）。 – FrankPl

@FrankPI虛擬呼叫的花費比您想象的要多。你必須設置變量，推送內容，進行調用，設置堆棧，可能會修改變量，返回等......使用跳轉列表除了缺省值外，不存在無條件跳轉。人們可以進行間接跳躍，而不會造成任何預測問題。人們也可以像我描述的那樣內聯函數，目的是虛擬函數不能這樣做。 – user2541029

智能艾菲爾使用非常類似描述的技術，其中約80％的虛擬功能被內聯。這種方法不允許將vtable dispatch作爲默認設置來防止動態鏈接，所以這對於通用目的來說可能是更合適的想法。

http://smarteiffel.loria.fr/papers/oopsla97.pdf

來源

2013-08-16 18:33:15 user2541029

通過直接內聯代碼實現更快的繼承

回答

相關問題