我一直在使用 C-ish C 代碼實作各種基于節點的二叉搜索樹。在對這些進行基準測驗時，我注意到跨編譯器和回應小的代碼更改的性能差異驚人地大。
當我專注于在允許重復的樹中插入和洗掉時（就像 C std::multiset<int>那樣），我發現幾乎所有時間都花在像“find”和“lower_bound”這樣的操作中鋸齒形地向下移動樹的左右指標而不是在插入和洗掉之后發生的概念上“昂貴”的重新平衡步驟。
所以我開始特別關注一個案例：下限。
// Node is a binary tree node. It has the
// usual left and right links and an
// integral key.
struct Node {
int key;
Node* links[2];
};
// LowerBound returns the first node in
// the tree rooted at "x" whose key is
// not less than "key", or null if there
// is no such key.
Node* LowerBound(Node* x, int key) {
Node* lower = nullptr;
while (x != nullptr) {
bool x_gte = !(x->key < key);
lower = x_gte ? x : lower;
x = x->links[!x_gte];
}
return lower;
}
幾點和觀察：
- 我使用的是 AMD Ryzen 9 5900X 12 核。我的理解是
cmovAMD 上的條件移動（ - 我正在運行 Linux。我已經關閉了超執行緒、升壓模式，并使用我撰寫的這個腳本將 CPU 縮放調節器設定為“性能” 。性能數字穩定，變化不大。
- 上面的代碼是幾次優化迭代的結束。我有一個基準測驗（這里的代碼），它練習各種樹大小，根據隨機或按密鑰順序升序分配陣列中的節點，然后將密鑰訪問模式寫入另一個陣列，并重復運行它們。密鑰訪問模式是升序或隨機的。在較大的樹中，使用分支而不是
cmov或類似的代碼通常要慢得多。 - 一個關鍵的優化似乎是在節點中使用鏈接陣列（
Node links[2]）而不是顯式left和right指標。使用顯式欄位 gcc 可以非常快速地切換到分支代碼，這會更慢。使用links陣列 gcc 將按照我所寫的那樣對其進行索引。 - 事實上，當我使用 gcc 的組態檔引導優化時，它仍然切換到基于分支的代碼，性能損失為 1.5 到 2 倍。
- 在所有情況下，除了分支代碼可以勝出的非常小的樹之外，clang 會為此函式生成更快的代碼。
在 Godbolt 上使用上面的代碼，我們可以看到 clang 生成以下內容：
LowerBound(Node*, int):
xorl
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/515478.html
標籤：C 部件海合会优化铛