Perché il codice extra casuale migliora le prestazioni?

Question

Struct Node { 
    Node *N[SIZE]; 
    int value; 
}; 

struct Trie { 
    Node *root; 

    Node* findNode(Key *key) { 
     Node *C = &root; 
     char u; 
     while (1) { 
      u = key->next(); 
      if (u < 0) return C; 
     // if (C->N[0] == C->N[0]); // this line will speed up execution significantly 
      C = C->N[u]; 
      if (C == 0) return 0; 
     } 
    } 
    void addNode(Key *key, int value){...}; 
}; 

In questa implementazione di Prefix Albero (aka Trie) ho scoperto che il 90% delle findNode() tempo di esecuzione è preso da una singola operazione C=C->N[u];

Nel mio tentativo di accelerare questo codice, ho casualmente aggiunta la linea di che viene commentato nella foto sopra, e il codice diventa più veloce del 30%! Perché?

UPDATE

Ecco il programma completo.

#include "stdio.h" 
#include "sys/time.h" 

long time1000() { 
    timeval val; 
    gettimeofday(&val, 0); 
    val.tv_sec &= 0xffff; 
    return val.tv_sec * 1000 + val.tv_usec/1000; 
} 

struct BitScanner { 
    void *p; 
    int count, pos; 
    BitScanner (void *p, int count) { 
     this->p = p; 
     this->count = count; 
     pos = 0; 
    } 
    int next() { 
     int bpos = pos >> 1; 
     if (bpos >= count) return -1; 
     unsigned char b = ((unsigned char*)p)[bpos]; 
     if (pos++ & 1) return (b >>= 4); 
     return b & 0xf; 
    } 

}; 

struct Node { 
    Node *N[16]; 
    __int64_t value; 
    Node() : N(), value(-1) { } 
}; 

struct Trie16 { 
    Node root; 

    bool add(void *key, int count, __int64_t value) { 
     Node *C = &root; 
     BitScanner B(key, count); 
     while (true) { 
      int u = B.next(); 
      if (u < 0) { 
       if (C->value == -1) { 
        C->value = value; 
        return true; // value added 
       } 
       C->value = value; 
       return false; // value replaced 
      } 
      Node *Q = C->N[u]; 
      if (Q) { 
       C = Q; 
      } else { 
       C = C->N[u] = new Node; 
      } 
     } 
    } 

    Node* findNode(void *key, int count) { 
     Node *C = &root; 
     BitScanner B(key, count); 
     while (true) { 
      char u = B.next(); 
      if (u < 0) return C; 
//   if (C->N[0] == C->N[1]); 
      C = C->N[0+u]; 
      if (C == 0) return 0; 
     } 
    } 
}; 

int main() { 
    int T = time1000(); 
    Trie16 trie; 
    __int64_t STEPS = 100000, STEP = 500000000, key; 
    key = 0; 
    for (int i = 0; i < STEPS; i++) { 
     key += STEP; 
     bool ok = trie.add(&key, 8, key+222); 
    } 
    printf("insert time:%i\n",time1000() - T); T = time1000(); 
    int err = 0; 
    key = 0; 
    for (int i = 0; i < STEPS; i++) { 
     key += STEP; 
     Node *N = trie.findNode(&key, 8); 
     if (N==0 || N->value != key+222) err++; 
    } 
    printf("find time:%i\n",time1000() - T); T = time1000(); 
    printf("errors:%i\n", err); 
} 

Answer 1

Questo è in gran parte un'ipotesi, ma da quello che ho letto sui dati della CPU prefetcher sarebbe solo prefetch se vede accesso multiplo alla stessa posizione di memoria e che l'accesso corrisponde ai trigger di prelettura, ad esempio sembra scansione. Nel tuo caso se c'è un solo accesso a C->N il prefetcher non sarebbe interessato, tuttavia se ci sono multipli e si può predire che l'accesso successivo è ulteriormente nello stesso bit di memoria che può far precedere più di una linea di cache .

Se quanto sopra stava accadendo, allora C->N[u] non avrebbe dovuto attendere che la memoria arrivasse dalla RAM, quindi sarebbe più veloce.

Answer 2

Poiché ogni operazione di scrittura è costosa rispetto alla lettura. Qui Se lo vedi, C = C-> N [u]; significa che la CPU sta eseguendo la scrittura in ogni iterazione per la variabile C. Ma quando si esegue if (C-> N [0] == C-> N [1]) dummy ++; scrivere su dummy viene eseguito solo se C-> N [0] == C-> N [1]. Quindi hai salvato molte istruzioni di scrittura della CPU usando la condizione.

Answer 3

Sembra che ciò che si sta facendo impedisca il blocco del processore ritardando l'esecuzione del codice finché i dati non sono disponibili localmente.

In questo modo è molto improbabile che l'errore continui a funzionare in modo coerente. Il modo migliore è ottenere il compilatore per farlo. Di default la maggior parte dei compilatori genera codice per una famiglia di processori generica. MA se si osservano i flag disponibili, in genere è possibile trovare i flag per specificare il proprio processore specifico in modo che possa generare un codice più specifico (come pre-fetch e codice di stallo).

See: GCC: how is march different from mtune? la seconda risposta va in qualche dettaglio: https://stackoverflow.com/a/23267520/14065