執行預先計算的事實檢查的不同方法

我正在爲一個函數生成C代碼的程序工作。這個生成的C函數駐留在另一個目標程序的中央循環中;此功能對性能非常敏感。生成的函數用於根據布爾值調用另一個函數 - 使用傳遞給生成函數的2個整數獲取此布爾值：一個狀態編號和一個模式編號。產生的函數看起來像這樣：執行預先計算的事實檢查的不同方法

void dispatch(System* system, int state, int mode) { 
    // Some other code here... 
    if (truthTable[state][mode]) { 
     doExpensiveCall(system, state, mode); 
    } 
}

一些事實：

「國家」和範圍「模式」值從0開始，並在一些數量< 10000個終端。它們的可能值是連續的，兩者之間沒有差距。因此，例如，如果'狀態'的最終值是1000，那麼我們知道有1001個狀態（包括狀態0）。
代碼生成器知道狀態和模式，並且它知道狀態+模式的哪種組合會提前產生真值。理論上講，狀態+模式的任何組合都可以產生真正的價值，從而調用doExpensiveCall，但是在實踐中它將主要是少數狀態+模式組合，它們會產生真值。同樣，這些信息在代碼生成期間是已知的。
由於此函數將被稱爲很多，我想優化檢查真值。在平均情況下，我預計測試對於大量時間會產生錯誤。平均而言，我預計只有不到1％的電話會產生真值。但是，理論上，它可以高達100％的時間（這一點取決於最終用戶）。

我正在探索不同的方式，我可以計算一個狀態+模式是否會呼叫doExpensiveCall（）。最後，我不得不選擇一些東西，所以我現在正在探索我的選擇。這些是目前我能想到的不同方式：

1）創建一個預先計算的包含布爾值的二維數組。這是我在上面的例子中使用的。這產生了我能想到的儘可能快的檢查。問題是如果狀態和模式的範圍很大（比如說10,000x1000），生成的表開始變得非常大（在10,000x1000的情況下，那個表只有10MB）。例如：

// STATE_COUNT=4, MODE_COUNT=3 
static const char truthTable[STATE_COUNT][MODE_COUNT] = { 
    {0,1,0}, 
    {0,0,0}, 
    {1,1,0}, 
    {0,0,1} 
}

2）創建像＃1的表，但壓縮的：不是每個陣列條目是單個布爾值，這將是一個字符的位域。然後，在檢查過程中，我會用狀態+模式做一些計算來決定如何索引到數組中。這通過MODE_MODE/8減少了預計算表的大小。缺點是減少的並不多，現在需要計算位域表中布爾值的索引，而不是像＃1那樣只是簡單的數組訪問。

3）由於狀態+模式組合，將產生的真值的量預期爲小，switch語句也是可能的（在＃1使用truthTable作爲參考）：

switch(state){ 
case 0: // row 
switch(mode){ // col 
    case 1: doExpensiveCall(system, state, mode); 
    break; 
} 
break; 
case 2: 
switch(mode){ 
    case 0: 
    case 1: doExpensiveCall(system, state, mode); 
    break; 
} 
break; 
case 3: 
switch(mode){ 
    case 2: doExpensiveCall(system, state, mode); 
    break; 
} 
break; 
}

問題：

鑑於上述事實，有什麼其他方法可以用來計算調用doExpensiveCall（）所需的布爾值嗎？

感謝

編輯：我雖然關於延示例代碼，並出現以下情況給我。爲了只有一個switch語句，我可以在生成的代碼做這個計算：

// #if STATE_COUNT > MODE_COUNT 
int i = s * STATE_COUNT + m; 
// #else 
int i = m * MODE_COUNT + s; 
// #endif 

switch(i) { 
case 1: // use computed values here, too. 
case 8: 
case 9: 
case 14: 
    doExpensiveCall(system, s, m);

}

來源

2014-09-22 Dess

您是否嘗試過分析/基準測試，看看它是否重要？所有事情都是平等的，我會從最簡單的解決方案（＃1）開始，看看是否有任何優先考慮的事情。 – uesp 2014-09-22 15:01:41

具有完美散列函數的散列表？ – 2014-09-22 15:08:18

優化還取決於什麼是重要的在你的情況：速度，內存，簡單/未來的維護等...... – uesp 2014-09-22 15:09:55

我會嘗試使用（3），在那裏你實際上有一個修改版本只一個電話，以及所有的東西導致這個電話。通過這一點，你可以確保編譯器會選擇他有哪些啓發式方法來優化它。

沿

switch(state) { 
default: return; 
case 0: // row 
    switch(mode){ // col 
    default: return; 
    case 1: break; 
    } 
    break; 
case 2: 
    switch(mode){ 
    default: return; 
    case 0: break; 
    case 1: break; 
    } 
    break; 
case 3: 
    switch(mode){ 
    default: return; 
    case 2: break; 
    } 
    break; 
} 

doExpensiveCall(system, state, mode);

這是該行的東西，你只擁有switch裏面的「控制」。編譯器應該能夠很好地對此進行分類。

這些啓發式可能會在體系結構和編譯選項（例如-O3與-Os）之間有所不同，但這是編譯器的用途，根據平臺特定的知識進行選擇。

對於時間效率的參考，如果您的功能調用如您聲稱的那樣非常昂貴，那麼這個部分只會在噪音中埋下來，不用擔心。（或以其他方式對您的代碼進行基準測試）

來源

2014-09-22 15:07:14

「，你實際上只有一個電話，而所有的開關/情況都會導致這個電話。」你能展示一些示例代碼嗎？我很想知道你會如何去做這件事。 – Dess 2014-09-22 16:25:20

@Dess，請參閱我的編輯。 – 2014-09-22 20:45:05

如果代碼生成器知道正在使用的表的百分比，則可以在構建時選擇該算法。

所以，如果它是大約50％真/假使用10 MB表。

否則使用散列表或基數樹。

散列表將選擇一個散列函數和多個存儲桶。你需要計算散列值，找到存儲桶並在鏈中搜索真值（或假值）。

基數樹會選擇一個基數（如10），並且您將有10個指針指向NULL的條目（其中沒有真值），並且其中一個指針將指向另外10個條目，直到您最終達到一個值。

來源

2014-09-23 02:12:36

執行預先計算的事實檢查的不同方法

回答

相關問題