为什么随机额外代码会提高性能？

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

因为每次写入操作的成本都比读取高。在这里，如果你看到了， C = C->N[u];这意味着 CPU 正在为变量 C 在每次迭代中执行写入。但是当你执行 if (C->N[0] == C->N[1]) dummy++; write on dummy 仅在 C->N[0] == C->N[1] 时执行。所以你已经通过使用 if 条件保存了很多 CPU 的写指令。

Answer 2

这主要是一个猜测，但从我读到的关于 CPU 数据预取器的内容来看，它只会在看到对同一内存位置的多次访问并且该访问与预取触发器匹配时才会预取，例如看起来像扫描。在您的情况下，如果只有一次访问 C->N 预取器将不会感兴趣，但是如果有多个并且它可以预测以后的访问会进一步进入同一内存位，从而可以预取更多比一个缓存行。

如果发生上述情况，则 C->N[u] 不必等待内存从 RAM 到达，因此会更快。

Answer 3

看起来您正在做的是通过延迟代码执行直到数据在本地可用来防止处理器停顿。

这样做很容易出错，不太可能继续持续工作。更好的方法是让编译器这样做。默认情况下，大多数编译器为通用处理器系列生成代码。但是如果您查看可用的标志，您通常可以找到用于指定特定处理器的标志，以便它可以生成更具体的代码（如预取和停止代码）。

参见：GCC: how is march different from mtune? the second answer goes into some detail:

为什么随机额外代码会提高性能？

Why does random extra code improve performance?

c++

performance

pointers

trie