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

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

В этой реализации дерева префикса (aka 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);
}

Ответы

Ответ 1

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

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

Ответ 2

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

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

Смотрите: GCC: как отличается марш от mtune? второй ответ идет на несколько деталей: fooobar.com/questions/24272/...

Ответ 3

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