__builtin_expected使用邊界檢查

Question

我有這個函數，給定Gray code，返回下一個格雷碼。你可以找到關於它如何工作的更完整的解釋here。問題是我想讓這個增量函數模塊化，這樣增加對應於UINT_MAX的格雷碼將返回對應於0（分別是最高有效位和0）的格雷碼。既然這不是默認行爲，我爲這個特例添加了一個檢查。這裏是完整的算法：

unsigned next_gray(unsigned gray) 
{ 
    static const unsigned msb 
     = 1u << (CHAR_BITS - sizeof(unsigned) - 1u); 

    // gray is odd 
    if (__builtin_parity(gray)) 
    { 
     if (__builtin_expect(gray == msb, false)) 
     { 
      return 0u; 
     } 
     else 
     { 
      unsigned y = gray & -gray; 
      return gray^(y << 1u); 
     } 
    } 

    // gray is even 
    return gray^1; 
} 

所以，實際的問題實際上是關於分支預測。我經常讀到__builtin_expect只有在確實有可能選擇分支或者不太可能選擇分支時才使用，常見的例子是在沒有錯誤時加快程序運行速度。

考慮到我沒有處理錯誤的情況下，我不確定是否使用__builtin_expect這樣的邊界檢查是一個好主意。這是一個很好的地方使用__builtin_expect或增加最大值一個足夠常見的操作欺騙分支預測？

注：一如既往的意見和答案突出的東西並不清楚我的問題:)

我會給多一點背景：該功能意味着是一個庫的一部分，用於開發爲了成爲一個圖書館，並沒有被知道的任何實際項目所使用。因此，加入__builtin_expect意味着我期望人們大多增加其他值然後是最大值;沒有任何實際的項目，我想知道這是否是一個安全的假設。

Answer 1

從the GCC online docs摘自：

您可以使用__builtin_expect以提供分支預測信息的編譯器。 一般來說，您應該更願意使用實際的配置文件反饋（-fprofile-arcs），因爲程序員在預測其程序實際執行方式時表現出色。但是，有些應用程序難以收集這些數據。

這是一個很好的地方使用__builtin_expect或增加最大值一個足夠常見的操作欺騙分支預測？

這一切都取決於您的應用程序。如果gray的值是均勻分佈的，那麼它將是(UINT_MAX+1)中的1，但是您能否肯定地說？這就是爲什麼docs推薦使用-fprofile-arcs。

gcov wikipedia article實際上包含一個很好的簡單示例，關於如何使用-fprofile-arcs和gcov來獲取信息以作出明智的決定。

更新：

如果您不能配置文件，然後所有的事情都是平等的邊緣情況gray == msb是非常不可能的，所以你可能安全與您使用的__builtin_expect。但是，如果因爲不知道自己的庫將如何使用而無法進行配置文件，這聽起來更像是pessimization而不是優化。如果我使用你的圖書館，並且總是通過gray，使它等於msb，那麼你的圖書館對我來說就不會那麼快。不考慮特定應用程序而編寫的通用庫通常會嘗試在平均情況下或在不對輸入作出任何假設的情況下使用。這就是爲什麼你看到malloc的不同實現，如jemalloc和tcmalloc。兩者都針對非常具體的用例進行了優化，如果以與優化的方式不同的方式使用它，它將不會如此。 this blog article也許對你有些興趣。