对于二叉树“LowerBound”算法，gcc 能否发出与 clang 一样高效的代码？

Question

我一直在使用 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;
}

几点和观察：

1. 我使用的是 AMD Ryzen 9 5900X 12 核。 我的理解是条件移动 ( cmov) 指令在 AMD 上比在 Intel 上更快（我的理解是错误的，请参阅 Peter Cordes 对这篇文章的评论），但我发现当我在我的 8 年旧 Intel 笔记本电脑上抽查结果时在 AMD 上速度更快的代码在英特尔上也更快。
2. 我正在运行Linux。我已经关闭了超线程、升压模式，并使用我编写的脚本将 cpu 缩放调节器设置为“性能” 。性能数据稳定，变化很小。
3. 上面的代码是几次优化迭代的结束。我有一个基准测试（此处为代码），它练习各种树大小，根据随机或按键顺序升序分配数组中的节点，然后将键访问模式写入另一个数组，并重复运行它们。密钥访问模式可以是升序的，也可以是随机的。在较大的树中，使用分支而不是cmov或类似的代码通常要慢得多。
4. Node links[2]一个关键的优化似乎是在节点中使用链接数组 ( ) 而不是显式left和right指针。使用显式字段，gcc 可以非常快地切换到分支代码，但分支代码速度较慢。对于links数组，gcc 将按照我所写的那样对其进行索引。
5. 事实上，当我使用 gcc 的配置文件引导优化时，它仍然切换到基于分支的代码，性能损失为 1.5 到 2 倍。
6. 在所有情况下，除了分支代码可以胜出的非常小的树之外，clang 都会为此函数生成更快的代码。

通过上面的 godbolt 代码，我们可以看到 clang 生成了以下内容：

LowerBound(Node*, int):
        xorl    %eax, %eax
        testq   %rdi, %rdi
        je      .LBB0_3
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        xorl    %ecx, %ecx
        cmpl    %esi, (%rdi)
        setl    %cl
        cmovgeq %rdi, %rax
        movq    8(%rdi,%rcx,8), %rdi
        testq   %rdi, %rdi
        jne     .LBB0_1
.LBB0_3:
        retq

而海湾合作委员会做得更糟：

LowerBound(Node*, int):
        xorl    %eax, %eax
        testq   %rdi, %rdi
        je      .L5
.L4:
        cmpl    %esi, (%rdi)
        setl    %dl
        cmovge  %rdi, %rax
        movzbl  %dl, %edx
        movq    8(%rdi,%rdx,8), %rdi
        testq   %rdi, %rdi
        jne     .L4
        ret
.L5:
        ret

gcc 变体在我的机器上大约慢 2 倍（树高为 1 到 18 的时间的几何平均值）。这可以用简单的方式解释吗？我注意到 clang 首先清除%ecx，然后设置%cl，然后使用%ecx，而 gcc 设置%dl然后将其移动到%edx使用之前%rdx。

gcc 的方法在逻辑上是等效的，但在实践中要慢得多。可以改进吗？

Answer 1

使用llvm-mca（LLVM 套件中的一个工具来分析给定架构的机器代码），我们可以看到确实存在差异。

对于 Intel Skylake 架构，GCC 与 LLVM 生成的代码：

Instructions:      1200 vs 1200 
Total Cycles:      1305 vs 1205
Total uOps:        1700 vs 1400

对于 AMD Zen3 架构，GCC 与 LLVM 生成的代码：

Instructions:      1200 vs 1100 
Total Cycles:      1205 vs 1105
Total uOps:        1200 vs 1100

GCC 的平均等待时间高出 20%

Average Wait times (based on the timeline view):
[0]: Executions
[1]: Average time spent waiting in a scheduler's queue
[2]: Average time spent waiting in a scheduler's queue while ready
[3]: Average time elapsed from WB until retire stage

      [0]    [1]    [2]    [3]
0.     3     0.0    0.0    12.0      xorl   %eax, %eax
1.     3     11.0   0.3    0.7       testq  %rdi, %rdi
2.     3     12.0   0.0    0.0       je .L5
3.     3     11.0   0.3    0.0       cmpl   %esi, (%rdi)
4.     3     16.0   0.0    0.0       setl   %dl
5.     3     17.0   0.0    0.0       movzbl %dl, %edx
6.     3     15.0   0.0    1.0       cmovgeq    %rdi, %rax
7.     3     17.0   0.0    0.0       movq   8(%rdi,%rdx,8), %rdi
8.     3     22.0   0.0    0.0       testq  %rdi, %rdi
9.     3     23.0   0.0    0.0       jne    .L4
10.    3     1.0    1.0    18.0      retq
11.    3     1.7    1.7    17.3      retq
       3     12.2   0.3    4.1       <total>

针对 LLVM 生成的代码

Average Wait times (based on the timeline view):
[0]: Executions
[1]: Average time spent waiting in a scheduler's queue
[2]: Average time spent waiting in a scheduler's queue while ready
[3]: Average time elapsed from WB until retire stage

      [0]    [1]    [2]    [3]
0.     3     0.0    0.0    11.7      xorl   %eax, %eax
1.     3     10.3   0.3    0.7       testq  %rdi, %rdi
2.     3     11.0   0.0    0.0       je .LBB0_3
3.     3     0.0    0.0    12.0      xorl   %ecx, %ecx
4.     3     10.0   0.3    0.0       cmpl   %esi, (%rdi)
5.     3     15.0   0.0    0.0       setl   %cl
6.     3     14.7   0.0    0.0       cmovgeq    %rdi, %rax
7.     3     15.3   0.0    0.0       movq   8(%rdi,%rcx,8), %rdi
8.     3     20.0   0.0    0.0       testq  %rdi, %rdi
9.     3     21.0   0.0    0.0       jne    .LBB0_1
10.    3     1.0    1.0    16.0      retq
       3     10.8   0.2    3.7       <total>

我们还可以看到，GCC 每次迭代的资源压力要高得多

Resources:
[0]   - Zn3AGU0
[1]   - Zn3AGU1
[2]   - Zn3AGU2
[3]   - Zn3ALU0
[4]   - Zn3ALU1
[5]   - Zn3ALU2
[6]   - Zn3ALU3
[7]   - Zn3BRU1
[14.0] - Zn3LSU
[14.1] - Zn3LSU
[14.2] - Zn3LSU
[15.0] - Zn3Load
[15.1] - Zn3Load
[15.2] - Zn3Load

Resource pressure per iteration:
[0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]    
1.33   1.33   1.34   3.33   1.35   1.65   2.65   2.02   

[14.0] [14.1] [14.2] [15.0] [15.1] [15.2] 
 1.33   1.33   1.34   1.33   1.33   1.34 

反对LLVM

[0]    [1]    [2]    [3]    [4]    [5]    [6]    [7]  
1.00   1.00   1.00   2.55   0.99   1.01   2.50   1.95

[14.0] [14.1] [14.2] [15.0] [15.1] [15.2] 
 1.00   1.00   1.00   1.00   1.00   1.00  

看起来 LLVM 编译器在优化管道压力方面做得更好。

• 编译器资源管理器（原始）：https ://godbolt.org/z/abde4vv7r
• 编译器资源管理器（按照 Peter Cordes 的建议排除了 ret 指令，选择 zen3 arch）：https://godbolt.org/z/4K6814chq

如果您只对作为内部循环的执行的某些部分感兴趣，则可以将要分析的区域标记为

Instructions:      1200 vs 1200 
Total Cycles:      1305 vs 1205
Total uOps:        1700 vs 1400

这使得 GCC 的总周期达到 1303 个，LLVM 的总周期达到 1203 个。

编译器资源管理器：https://godbolt.org/z/8KoKfab34