智能指针产生低效的编译代码

Question

我正在实现 BST，我认为使用

unique_ptr

来表示子节点所有权是个好主意。然而我发现智能指针导致编译器更喜欢分支而不是无分支代码（即

cmov

）。我正在使用

g++-13

进行编译和

Ubuntu 24.04.1 LTS

。我使用三元运算符来鼓励无分支代码，但没有效果。这是一个简单的原型。

#include <memory>
#include <iostream>
struct node {
    int val;
    node* left_child;
    node* right_child;
};

struct smart_node {
    int val;
    std::unique_ptr<smart_node> left_child;
    std::unique_ptr<smart_node> right_child;
};

node*
__attribute__((noinline))
raw(node* root, int key) {
    node* prev = root;
    node* curr = prev -> left_child;
    while (curr != nullptr) {
        prev = curr;
        bool comp = key < (curr -> val);
        curr = comp ? curr -> left_child : curr -> right_child;
    }
    return prev;
}

smart_node*
__attribute__((noinline))
smart(std::unique_ptr<smart_node> root, int key) {
    smart_node* prev = root.get();
    smart_node* curr = prev -> left_child.get();
    while (curr != nullptr) {
        prev = curr;
        bool comp = key < (curr -> val);
        curr = comp ? curr -> left_child.get() : curr -> right_child.get();
    }
    return prev;
}

int main() {
    auto last1 = raw(nullptr, 1);
    auto last2 = smart(std::make_unique<smart_node>(), 1);
    std::cout << last1 -> val << last2 -> val;
}

下面是

raw

中循环的汇编代码。

    1310:   48 89 c2                mov    %rax,%rdx
    1313:   48 8b 42 10             mov    0x10(%rdx),%rax
    1317:   3b 32                   cmp    (%rdx),%esi
    1319:   48 0f 4c 42 08          cmovl  0x8(%rdx),%rax
    131e:   48 85 c0                test   %rax,%rax
    1321:   75 ed                   jne    1310 <_Z3rawP4nodei+0x20>

下面是

smart

中循环的汇编代码。

    1360:   48 8b 50 08             mov    0x8(%rax),%rdx
    1364:   48 85 d2                test   %rdx,%rdx
    1367:   74 10                   je     1379 <_Z5smartSt10unique_ptrI10smart_nodeSt14default_deleteIS0_EEi+0x39>
    1369:   48 89 d0                mov    %rdx,%rax
    136c:   3b 30                   cmp    (%rax),%esi
    136e:   7c f0                   jl     1360 <_Z5smartSt10unique_ptrI10smart_nodeSt14default_deleteIS0_EEi+0x20>
    1370:   48 8b 50 10             mov    0x10(%rax),%rdx
    1374:   48 85 d2                test   %rdx,%rdx
    1377:   75 f0                   jne    1369 <_Z5smartSt10unique_ptrI10smart_nodeSt14default_deleteIS0_EEi+0x29>

在基准测试中（2e6 调用具有 2e6 个节点的树），分支代码大约需要无分支版本的 1.4 倍时间。我使用了

RelWithDebInfo

，因此 O2 优化已开启。我的问题是如何强制编译器使用

cmov

？我读了这篇文章，似乎没有干净的方法来强制这种行为。如果不可能，我想知道为什么编译器为这两种情况生成不同的代码。

澄清一下，我不想组装，因为它不可移植。我用汇编强制了branchless版本，但这不是我想要追求的方向

Answer 1

g++ 13 确实为智能指针生成了更糟糕的代码。不过，较新版本的 gcc (14.2) 似乎生成几乎相同的代码。

您可以通过完全消除内联分支来获得更好的组装，同时仍然将分支保留在唯一的指针中。

struct sv_node {
    int val;
    std::array<std::unique_ptr<sv_node>,2> child{};
};

sv_node*
__attribute__((noinline))
svec(sv_node* root, int key) {
    auto prev = root;
    auto curr = prev->child[0].get();
    while (curr != nullptr) {
        prev = curr;
        bool const comp = key >= (curr->val);
        curr = curr->child[comp].get();
    }
    return prev;
}

这会使用 gcc 13.3 生成以下程序集：

svec(sv_node*, int):
        mov     rdx, QWORD PTR [rdi+8]
        test    rdx, rdx
        je      .L19
.L21:
        xor     eax, eax
        cmp     DWORD PTR [rdx], esi
        mov     rdi, rdx
        setle   al
        mov     rdx, QWORD PTR [rdx+8+rax*8]
        test    rdx, rdx
        jne     .L21
.L19:
        mov     rax, rdi
        ret

（现场演示）

您还可以不使用

std::array<std::unique_ptr<node>,2>

，而是将其设为具有类似汇编但遍历逻辑略有不同的

std::vector<node>

。我怀疑类似的表现。

但是，非常重要的是，为了计算性能，您必须进行基准测试。仅查看组装是不够的。