Ottimizzazione del ramo while in loop, perché meno istruzioni costano più tempo di esecuzione?

Question

Ho un progetto di implementazione della struttura dati da C, che esporta tipi di API per altri programmi. Recentemente mi piacerebbe fare qualche ottimizzazione sulla funzione Hot profilata da grofile. Ecco il progetto per il tuo riferimento.

https://github.com/Incarnation-p-lee/libds C'è un binary_search_tree_node_insert funzione di caldo, come di seguito:

/* 
* RETURN the pointer of inserted node of the binary search tree 
*  If root is NULL or node is NULL, RETURN NULL. 
*/ 
struct binary_search_tree * 
binary_search_tree_node_insert(struct binary_search_tree *root, 
    struct binary_search_tree *node) 
{ 
    register struct binary_search_tree **iter; 

    if (!node || !root) { 
     pr_log_warn("Attempt to access NULL pointer.\n"); 
    } else { 
     iter = &root; 
     while (*iter) { 
      if (node->chain.nice == (*iter)->chain.nice) { 
       if (*iter == node) { 
        pr_log_info("Insert node exist, nothing will be done.\n"); 
       } else { 
        doubly_linked_list_merge((*iter)->chain.link, node->chain.link); 
       } 
       return *iter; 
#ifndef OPT_HOT 
      } else if (node->chain.nice > (*iter)->chain.nice) { 
        iter = &(*iter)->right; 
      } else if (node->chain.nice < (*iter)->chain.nice) { 
        iter = &(*iter)->left; 
#else 
      } else { 
       binary_search_tree_insert_path_go_through(node, iter); 
#endif 
      } 
     } 
     return *iter = node; 
    } 

    return NULL; 
} 

voglio ottimizzazione due else-if parte come è mezza a metà ramo, che possono avere un impatto sulla pipeline di molto. Quindi scrivo una macro binary_search_tree_insert_path_go_through per sostituire questi due rami. E l'implementazione come segue:

/* 
* 1. node->nice => rbx, *iter => rcx. 
* 2. compare rbx, and 0x8(rcx). 
* 3. update iter. 
*/ 
#define binary_search_tree_insert_path_go_through(node, iter) \ 
    asm volatile (           \ 
     "mov $0x18, %%rax\n\t"        \ 
     "mov $0x20, %%rdx\n\t"        \ 
     "mov 0x8(%1), %%rbx\n\t"        \ 
     "mov (%0), %%rcx\n\t"         \ 
     "cmp 0x8(%%rcx), %%rbx\n\t"       \ 
     "cmovg %%rdx, %%rax\n\t"        \ 
     "lea (%%rcx, %%rax), %0\n\t"       \ 
     :"+r"(iter)           \ 
     :"r"(node)           \ 
     :"rax", "rbx", "rcx", "rdx") 

Ma il test di unità di questa funzione è sceso del 6-8% circa su questa modifica. Dal codice objdump (codice ottimizzato sulla mano destra), ha meno istruzioni, non riesco a capire perché è costato più tempo prima dell'ottimizzazione.

E ci sono alcuni dettagli per voi riferimento:

struct collision_chain { 
    struct doubly_linked_list *link; 
    sint64     nice; 
}; 
/* 
* binary search tree 
*/ 
struct binary_search_tree { 
    struct collision_chain chain; 
    sint32     height; /* reserved for avl */ 
    /* root node has height 0, NULL node has height -1 */ 
    union { 
     struct binary_search_tree *left; 
     struct avl_tree   *avl_left; /* reserved for avl */ 
     struct splay_tree   *splay_left; /* reserved for splay */ 
    }; 
    union { 
     struct binary_search_tree *right; 
     struct avl_tree   *avl_right; /* reserved for avl */ 
     struct splay_tree   *splay_right; /* reserved for splay */ 
    }; 
}; 
struct doubly_linked_list { 
    uint32     sid; 
    void      *val; 
    struct doubly_linked_list *next; 
    struct doubly_linked_list *previous; 
}; 

Funziona su virtual-box con 2 nucleo di i5-3xxM, e cpuinfo come segue:

processor  : 0 
vendor_id  : GenuineIntel 
cpu family  : 6 
model   : 58 
model name  : Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz 
stepping  : 9 
microcode  : 0x19 
cpu MHz   : 2568.658 
cache size  : 6144 KB 
physical id  : 0 
siblings  : 2 
core id   : 0 
cpu cores  : 2 
apicid   : 0 
initial apicid : 0 
fpu    : yes 
fpu_exception : yes 
cpuid level  : 5 
wp    : yes 
flags   : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl pni ssse3 lahf_lm 
bogomips  : 5137.31 
clflush size : 64 
cache_alignment : 64 
address sizes : 36 bits physical, 48 bits virtual 
power management: 

processor  : 1 
vendor_id  : GenuineIntel 
cpu family  : 6 
model   : 58 
model name  : Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz 
stepping  : 9 
microcode  : 0x19 
cpu MHz   : 2568.658 
cache size  : 6144 KB 
physical id  : 0 
siblings  : 2 
core id   : 1 
cpu cores  : 2 
apicid   : 1 
initial apicid : 1 
fpu    : yes 
fpu_exception : yes 
cpuid level  : 5 
wp    : yes 
flags   : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl pni ssse3 lahf_lm 
bogomips  : 5137.31 
clflush size : 64 
cache_alignment : 64 
address sizes : 36 bits physical, 48 bits virtual 
power management: 

Answer 1

Non so se è lo stesso per i processori moderni, ma Linus really didn't like the CMOV instruction back in '07.

Dato che si sta ottimizzando in micro, spostare il controllo di uguaglianza sull'ultima posizione. È quasi sempre falso, eppure lo stai facendo in ogni iterazione.

Inoltre, proverei non utilizzando il modello puntatore-puntatore. L'indirizzamento tende a fare strozzare gli ottimizzatori a causa di problemi di aliasing del puntatore. Invece, utilizzare un modello pollice-vite senza fine con due puntatori:

void insert(NODE *x, NODE **root) { 
    NODE *trail = NULL; 
    NODE *lead = *root; 
    while (lead) { 
    trail = lead; 
    if (x->key < lead->key) 
     lead = lead->left; 
    else if (x->key > lead->key) 
     lead = lead->right; 
    else return; // do nothing; 
    } 
    // lead has found null, so insert 
    if (trail) 
    // redo the last key comparison 
    if (x->key < trail->key) 
     trail->left = x; 
    else 
     trail->right = x; 
    else 
    *root = x; 
} 

sul mio MacBook, questo compila il seguente codice a 64 bit, in cui il circuito include solo 10 istruzioni. E 'difficile dire dai piccoli annunci nel tuo post, ma sembra che sia è molto più lungo:

pushq %rbp 
    movq %rsp, %rbp 
    movq (%rsi), %rdx 
    testq %rdx, %rdx 
    je  LBB0_11 
    movl 16(%rdi), %ecx 
LBB0_2:         
    movq %rdx, %rax  # dx=lead, ax=trail 
    cmpl 16(%rax), %ecx # comparison with key 
    jge  LBB0_4   # first branch 
    movq %rax, %rdx  # go left (redundant because offset(left)==0!) 
    jmp  LBB0_6 
LBB0_4:         
    jle  LBB0_12  # second branch 
    leaq 8(%rax), %rdx # go right 
LBB0_6:         
    movq (%rdx), %rdx # move lead down the tree 
    testq %rdx, %rdx  # test for null 
    jne  LBB0_2   # loop if not 
    testq %rax, %rax  # insertion logic 
    je  LBB0_11 
    movl 16(%rdi), %ecx 
    cmpl 16(%rax), %ecx 
    jge  LBB0_10 
    movq %rdi, (%rax) 
    popq %rbp 
    retq 
LBB0_11: 
    movq %rdi, (%rsi) 
LBB0_12:     # return for equal keys 
    popq %rbp 
    retq 
LBB0_10: 
    movq %rdi, 8(%rax) 
    popq %rbp 
    retq 

Se i confronti sono costosi, (non si presenta che cosa "bella" è), si potrebbe anche sperimentare con la memorizzazione del risultato binario del confronto tra i percorsi in modo che il controllo finale utilizzi questo anziché ripetere il confronto.

Answer 2

Non è una risposta diretta alla sua domanda, ma si può evitare la else if tutto:

sint64 mask,left,right; 
... 
if (node->chain.nice == (*iter)->chain.nice) 
{ 
    ... 
} 
else 
{ 
    mask = ((*iter)->chain.nice - node->chain.nice) >> 63; 
    left = (sint64)(&(*iter)->left); 
    right = (sint64)(&(*iter)->right); 
    iter = (struct binary_search_tree**)((left & mask) | (right & ~mask)); 
}