Почему случайный дополнительный код повышает производительность?

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){...}; 
}; 

В этой реализации дерево префиксов (ака TRIE) Я обнаружил, что 90% от findNode() времени исполнения принимается за одну операцию C=C->N[u];

В моей попытке ускорить этот код, я случайно добавил строку который прокомментирован в отрыве выше, и код стал на 30% быстрее! Почему это?

ОБНОВЛЕНИЕ

Здесь представлена ​​полная программа.

#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

Это во многом предположение, но из того, что я прочитал о prefetcher данных CPU, он будет только предвыборным, если он увидит множественный доступ к одной и той же ячейке памяти и что доступ соответствует триггерам предварительной выборки, например, выглядит как сканирование. В вашем случае, если есть только один доступ к C->N, prefetcher не будет интересовать, однако, если их несколько, и он может предсказать, что более поздний доступ будет входить в тот же бит памяти, который может заставить его предварительно выбрать более одной строки кэша ,

Если вышеуказанное происходило, то C->N[u] не нужно было ждать, пока память поступит из ОЗУ, поэтому будет быстрее.

Answer 2

Поскольку каждая операция записи является дорогостоящей, чем прочитанная. Здесь, если вы видите это, C = C-> N [u]; это означает, что процессор выполняет запись в каждой итерации для переменной C. Но когда вы выполняете if (C-> N [0] == C-> N [1]) dummy ++; write on dummy выполняется только в том случае, если C-> N [0] == C-> N [1]. Таким образом, вы сохраняете множество инструкций по написанию CPU, используя условие if.

Answer 3

Похоже, что то, что вы делаете, - это предотвращение простоя процессора, задерживая выполнение кода до тех пор, пока данные не будут доступны локально.

Выполнение этого способа очень маловероятно, что вряд ли продолжит работать последовательно. Лучший способ - заставить компилятор сделать это. По умолчанию большинство компиляторов генерируют код для семейства общих процессоров. BUT Если вы посмотрите на доступные флаги, вы обычно можете найти флаги для указания вашего конкретного процессора, чтобы он мог генерировать более конкретный код (например, предварительные выборки и код блокировки).

См: GCC: how is march different from mtune? второй ответ идет в некоторые детали: https://stackoverflow.com/a/23267520/14065