無分支溢出處理

Question

我正在嘗試創建一種安全緩衝區，可自動處理沒有任何分支的溢出。緩衝區大小是2的冪，並且只應具有有效的正（即不包括零）索引。它還允許檢查刪除，如果存儲在該索引處的元素等於搜索鍵，則在給定索引處刪除該刪除。

我基本上去爲這樣的事情

Element *buffer[256]; 

inline void buffer_insert(size_t index, Element *elem){ 
    buffer[index < 256 && index] = elem; 
} 

//Optional: checked insert to prevent overwrite. Will only insert 
//if the buffer holds NULL at index. 
inline void buffer_checkedInsert(size_t index, Element * elem){ 
    buffer[index && !buffer[index < 256 && index]] = elem; 
} 

inline void buffer_checkedRemove(size_t index, Element *elem){ 
    buffer[0] = NULL; //Maybe useful if buffer[0] stores elem 
    buffer[((elem == buffer[index < 256 && index)) && index] = NULL; 
} 

所以我基本上要訪問索引0時傳入的索引超出範圍，如buffer[0]不是一個有效的緩衝指數。我也想訪問索引0，只要要移除的元素不等於傳入移除的元素，並且我可能還想訪問索引0（如果緩衝區包含索引處的內容）。

我的問題是：

• 是我真正的網點？因爲如果C編譯器決定使用& &上的短路，則代碼可能會分支。
• 如果& &會導致分支，有沒有替代方案在這種情況下具有相同的行爲，不涉及分支？
• 這可以比基本的溢出檢查更快嗎？或者C編譯器能以某種方式給出if(index < 256) buffer[index] = elem的無分支版本？

Answer 1

是我真的無分路？因爲如果C編譯器決定使用& &上的短路，則代碼可能會分支。

也許吧。在這些情況下，編譯器可能足夠聰明以發出無分支機器碼，但您不能依賴它。

如果& &原因分枝，有沒有在這種情況下，不涉及分支相同的行爲選擇？

你的問題有點困惑。編譯器可能發出分支代碼來實現&&操作的事實源於該操作的已定義行爲。任何具有相同行爲的替代方案都必須提供相同的分支可能性。另一方面，如果你的意思是詢問在所有情況下是否有替代方案計算相同的結果，那麼是的，你可以重寫那些表達式，但不能分支。例如，你可以使用任何的&或*運營商，像這樣：

buffer[(index < 256) & (index != 0)] = elem; 

或者，你可以實現的行爲實際上要：

buffer[(index < 256) * index] = elem; 

我們沒有理由認爲，編譯器會爲這些計算中的任何一個發出分支指令;如果確實如此，那很可能是因爲它認爲這會提高目標架構的性能。

這可以比基本的溢出檢查更快嗎？或者C編譯器能否以某種方式給出無分支版本的if（index < 256）buffer [index] = elem？

無分支版本肯定可以會更快。在非（非）分支執行很多的工作負載上，它們最有可能顯着加快，並且沒有容易辨別的替代方式。但是，如果（非）分支大多遵循規則模式，特別是如果它幾乎總是以單向的方式進行，那麼CPU的分支預測單元可以進行普通有效性檢查，至少與無分配分配一樣快。

最終，沒有充分的理由擔心這個問題，而沒有在實際數據或者其良好的傳真基礎上對代碼的實際性能進行基準測試。結果很可能取決於數據，它的重要程度取決於程序的運行時間花費在您詢問的功能上的多少。除非你有一個好的基準，否則你應該爲清晰度和可維護性編碼。