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);
}
->
, они могут быть очень дорогими. - person Kerrek SB   schedule 16.07.2015dummy++
, а сif (C->N[0] == C->N[1])
. Я предполагаю, что эта проверка приводит к тому, что кеши используются, и данные дляC = C->N[u]
сразу считываются в кеше. - person LPs   schedule 16.07.2015SIZE
? - person edmz   schedule 16.07.2015N
, когда видит, что к нему обращаются несколько раз? - person Alexander Balabin   schedule 16.07.2015dummy++
часть избыточна, однойif (C->N[0] == C->N[1]);
достаточно, чтобы вызвать эффект. - person exebook   schedule 16.07.2015__builtin_prefetch
на gcc? gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html - person erenon   schedule 16.07.2015__builtin_prefetch(C->N[u]);
, и эффект тот же. На самом деле даже на 5% быстрее. - person exebook   schedule 16.07.2015if (C->N[0] == C->N[0]);
, который проверяет тавтологию, а затем ничего не делает. Я ожидаю, что компилятор оптимизирует это (при условии отсутствия побочных эффектов от перегрузок операторов). С другой стороны,if (C->N[0] == C->N[1]);
не является тавтологией и может повлиять на кэширование, прогнозирование ветвлений, спекулятивное выполнение и т. д. - person Adrian McCarthy   schedule 16.07.2015