Início / coding / Perguntas / 79309593
Accepted
cpp is hard
Asked: 2024-12-26 21:27:45 +0800 CST

Ponteiro inteligente produz código compilado ineficiente

  • 772

Estou implementando um BST e acredito que é uma boa ideia usar unique_ptr para representar a propriedade do nó filho. No entanto, descobri que ponteiros inteligentes fazem com que o compilador prefira ramificação em vez de código sem ramificação (especificamente cmov). Estou usando g++-13 para compilar no Ubuntu 24.04.1 LTS. Tentei usar o operador ternário para encorajar código sem ramificação, mas não funcionou. Aqui está um protótipo simples

#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() {
    // Use null instead of a non-degenerative tree to shorten the code
    // I verified this doesn't cause the assembly of the two functions above to mutate
    auto last1 = raw(nullptr, 1);
    auto last2 = smart(std::make_unique<smart_node>(), 1);
    std::cout << last1 -> val << last2 -> val;
}

Abaixo está o código de montagem para o loop em 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>

Abaixo está o código de montagem para o loop em 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>

No benchmark (chamada 2e6 para uma árvore com nós 2e6), o código de ramificação leva cerca de 1,4x o tempo da versão sem ramificação. Eu usei RelWithDebInfopara que a otimização O2 esteja ativada. Minha pergunta é como posso forçar o compilador a usar cmov? Eu li esta postagem e parece que não há uma maneira limpa de forçar esse comportamento. Se não for possível, gostaria de saber por que o compilador gera código diferente para os dois casos.

Para esclarecer, não quero assembly, pois ele não é portátil. Usei assembly para forçar a versão branchless, mas não é a direção que quero seguir.

c++

1 respostas

  1. Best Answer

    g++ 13 de fato produz código pior para os ponteiros inteligentes. Versões mais recentes do gcc (14.2) parecem produzir código quase idêntico, no entanto.

    Você pode obter uma montagem ainda melhor eliminando completamente até mesmo a ramificação embutida e, ao mesmo tempo, mantendo as ramificações em ponteiros exclusivos.

    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;
}

    Isso produz a seguinte montagem com 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

    ( demonstração ao vivo )

    Você também pode, em vez de usar std::array<std::unique_ptr<node>,2>, fazer um std::vector<node>com assembly similar, mas com lógica de travessia ligeiramente diferente. E eu suspeito que tenha desempenho similar.

    No entanto, muito importante, para descobrir o desempenho, você tem que fazer benchmark. Apenas olhar para a montagem não será suficiente.

    • 3

relate perguntas