c++ - optimizar - optimizacion de codigo intermedio

¿Por qué el código extra al azar mejora el rendimiento?

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

En esta implementación de Prefix Tree (aka Trie) descubrí que el 90% del tiempo de ejecución de findNode() se toma con una sola operación C=C->N[u];

En mi intento por acelerar este código, agregué aleatoriamente la línea que se comentó en el recorte anterior, ¡y el código se volvió un 30% más rápido! ¿Porqué es eso?

ACTUALIZAR

Aquí está el programa 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

Dado que cada operación de escritura es costosa que la lectura. Aquí si ves eso, C = C-> N [u]; significa que la CPU está ejecutando escritura en cada iteración para la variable C. Pero cuando se realiza si (C-> N [0] == C-> N [1]) dummy ++; write on dummy se ejecuta solo si C-> N [0] == C-> N [1]. Así que tiene que guardar muchas instrucciones de escritura de la CPU al usar la condición if.

Answer 2

Esto es en gran medida una suposición, pero por lo que leí sobre el precaptor de datos de la CPU, solo captaría previamente si ve acceso múltiple a la misma ubicación de memoria y ese acceso coincide con desencadenadores de captación previa, por ejemplo, parece escanear. En su caso, si solo hay acceso único a C->N el precaptor no estaría interesado, sin embargo, si hay múltiples y puede predecir que el acceso posterior está más allá en el mismo bit de memoria que puede hacer que prefiera más de una línea de caché

Si sucediera lo anterior, entonces C->N[u] no tendría que esperar a que llegue la memoria desde la RAM, por lo tanto, sería más rápido.

Answer 3

Parece que lo que está haciendo es evitar puestos en el procesador al retrasar la ejecución del código hasta que los datos estén disponibles localmente.

Hacerlo de esta manera es muy propenso a errores y es poco probable que continúe funcionando de manera consistente. La mejor manera es hacer que el compilador haga esto. Por defecto, la mayoría de los compiladores generan código para una familia de procesadores genéricos. PERO si observa los indicadores disponibles, generalmente puede encontrar indicadores para especificar su procesador específico para que pueda generar un código más específico (como las precargas y el código de bloqueo).

Ver: GCC: ¿cómo es marzo diferente de mtune? la segunda respuesta entra en detalle: https://.com/a/23267520/14065