Início / user-19495138

cpp is hard's questions

Martin Hope
cpp is hard
Asked: 2024-12-26 21:27:45 +0800 CST
  • 9

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++