優化的重新排序

Question

我有這種C函數的分支被稱爲比別人多。

我的目標是找出安排if語句以儘量減少分支的最佳方式。

我能想到的唯一方法就是寫入文件，以便每條條件都分支到，從而創建直方圖。這似乎是一個乏味的方式。有更好的方法，更好的工具嗎？

我在AS3 Linux上使用gcc 3.4構建它;使用oprofile（opcontrol）進行分析。

Answer 1

這不便攜，但是GCC的許多版本都支持一個名爲__builtin_expect()功能，可以用來告訴編譯器我們所期望的值是：

if(__builtin_expect(condition, 0)) { 
    // We expect condition to be false (0), so we're less likely to get here 
} else { 
    // We expect to get here more often, so GCC produces better code 
} 

Linux內核使用這些作爲宏來使得他們更直觀，更清潔，更便攜（即重新定義非GCC系統宏）：

#ifdef __GNUC__ 
# define likely(x) __builtin_expect((x), 1) 
# define unlikely(x) __builtin_expect((x), 0) 
#else 
# define likely(x) (x) 
# define unlikely(x) (x) 
#endif 

有了這個，我們可以重寫上面的：

if(unlikely(condition)) { 
    // we're less likely to get here 
} else { 
    // we expect to get here more often 
} 

當然，這可能是不必要的，除非你的目標是原始速度和/或你已經分析並發現這是一個問題。

Answer 2

嘗試一個分析器（gprof？） - 它會告訴你花了多少時間。我不記得gprof是否會計數分支，但如果沒有，只需在每個分支中調用一個單獨的空方法。

Answer 3

將每個分支中的代碼包裝到函數中，並使用分析器查看每個函數被調用的次數。

Answer 4

逐行分析可以讓您瞭解哪些分支更經常被調用。

使用像LLVM這樣的東西可以自動進行此優化。

Answer 5

某些計數器可能會有所幫助。在看到計數器之後，並且有很大差異，您可以按降序對條件進行排序。

 
static int cond_1, cond_2, cond_3, ... 

void foo(){ 
    if (condition){ 
     cond_1 ++; 
     ... 
    } 
    else if(/*another_condition*/){ 
     cond_2 ++; 
     ... 
    } 
    else if (/*another_condtion*/){ 
     cond_3 ++; 
     ... 
    } 
    else{ 
     cond_N ++; 
     ... 
    } 
} 

編輯：一個「析構函數」，可以在測試運行結束打印計數器：

void cond_print(void) __attribute__((destructor)); 

void cond_print(void){ 
    printf("cond_1: %6i\n", cond_1); 
    printf("cond_2: %6i\n", cond_2); 
    printf("cond_3: %6i\n", cond_3); 
    printf("cond_4: %6i\n", cond_4); 
} 

我認爲這是足以只修改以包含foo（）函數的文件。

Answer 6

在Callgrind下運行您的程序將爲您提供分支信息。另外，我希望你能夠分析並確定這段代碼是有問題的，因爲這看起來好像是一種微型優化。編譯器將會從if/else if/else生成一個分支表，如果它能夠不需要分支的話（顯然這取決於條件是什麼）0，並且甚至會使處理器上的分支預測器失效（假設這不適用於嵌入式工作，如果可以隨意忽略我）非常適合確定分支目標。

Answer 7

它實際上並不重要，你改變它們到IMO的順序。分支預測器將存儲最常見的分支，並自動進行分析。

這就是說，有一些你可以嘗試......你可以保持一組工作隊列，然後，根據該if語句，他們執行他們陸續之前分配到正確的工作隊列最後。

這可以通過使用條件移動等來進一步優化（儘管這需要彙編程序，AFAIK）。這可以通過有條件地將1移入一個寄存器中來完成，該條件在條件a時被初始化爲0。將指針值放在隊列末尾，然後決定是否增加隊列計數器，方法是將該條件1或0添加到計數器。

突然之間，你已經消除了所有的分支，它變得無關緊要，有多少分支預測失誤。當然，與其中任何一種情況一樣，你最好的方式是分析，因爲儘管看起來它會提供勝利......但它可能不會。

Answer 8

我們用這樣一種機制：

// pseudocode 
class ProfileNode 
{ 
public: 
    inline ProfileNode(const char * name) : m_name(name) 
    { } 
    inline ~ProfileNode() 
    { 
     s_ProfileDict.Find(name).Value() += 1; // as if Value returns a nonconst ref 
    } 

    static DictionaryOfNodesByName_t s_ProfileDict; 
    const char * m_name; 
} 

然後在你的代碼

void foo() 
{ 
    if (/*condition*/) 
    { 
     ProfileNode("Condition A"); 
     // ... 
    } 
    else if(/*another_condition*/) 
    { 
     ProfileNode("Condition B"); 
     // ... 
    } // etc.. 
    else 
    { 
     ProfileNode("Condition C"); 
     // ... 
    } 
} 

void dumpinfo() 
{ 
    ProfileNode::s_ProfileDict.PrintEverything(); 
} 

你可以看到它是如何的容易把這些節點也秒錶計時，看看哪些分支消耗的時間最多。

Answer 9

作爲剖析技術，this是我所依賴的。

你想知道的是：花在評估這些條件上的時間是執行時間的一小部分嗎？

樣品會告訴你，如果沒有，它沒關係。

如果如果條件包括函數調用是在棧上的時間顯著的一部分，你要避免花費太多的時間在那些假比較什麼事做，例如。你說的這種方式是，如果你經常看到它從比如第一個或第二個if語句中調用一個比較函數，那麼在這個例子中捕獲它，然後退出來看它是否返回false或true。如果它通常返回false，它可能應該更靠近列表。