c++ - memes - Predicción de rama y optimización de predicción de destino de rama

tutorial weka en español

Question

Mi código hace frecuentes llamadas a una función con múltiples ramas (impredecibles). Cuando realicé un perfil, descubrí que se trata de un pequeño cuello de botella, con la mayoría del tiempo de CPU utilizado en los JMP condicionales.

Considere las siguientes dos funciones, donde el original tiene múltiples ramas explícitas.

void branch_example_original(void* mem, size_t s)
{
    if(!(s & 7)) {
        /* logic in _process_mem_64 inlined */
    }
    else if(!(s & 3)) {
        /* logic in _process_mem_32 inlined */
    }
    else if(!(s & 1)) {
        /* logic in _process_mem_16 inlined */
    }
    else {
        /* logic in _process_mem_8 inlined */
    }
}

Aquí está la nueva función, donde intenté eliminar las ramas que causaban el cuello de botella.

void branch_example_new(void* mem, size_t s)
{
    const fprocess_mem mem_funcs[] = {_process_mem_8, _process_mem_16, _process_mem_32, _process_mem_64};
    const uint32_t magic = 3 - !!(s & 7) - !!(s & 3) - !!(s & 1);
    mem_funcs[magic](mem, size >> magic);
}

Sin embargo, cuando diseñé el nuevo código, el rendimiento aumentó solo ~ 20%, y la llamada en sí (a un func en la matriz mem_funcs) tomó mucho tiempo.

¿La segunda variación es simplemente un condicional más implícito, ya que la CPU aún no puede predecir la función que se llamará? ¿Estoy en lo cierto al suponer que esto tiene que ver con la predicción del objetivo de rama?

¿Por qué sucede esto, y hay otras soluciones para esto?

Editar:

Gracias por las ideas, pero me gustaría una explicación de por qué sucede esto también.

Answer 1

Podrías probar algo como esto:

switch(s & 7) {
case 0:
    /* _process_mem_64 */
    break;
case 1:
case 3:
case 5:
case 7:
    /* _process_mem_8 */
    break;
case 2:
case 6:
    /* _process_mem_16 */
    break;
case 4:
    /* _process_mem_32 */
    break;
}

Esto implica solo un salto en una tabla de salto y no requiere una instrucción de llamada.

Answer 2

Un procesador moderno no solo tiene predicción de bifurcación, también tiene predicción de salto. Por ejemplo, si llama a una función virtual, puede predecir que la función real es la misma que en la llamada anterior y comenzar la ejecución antes de que realmente se lea el puntero a la función; si la predicción de salto fue incorrecta, las cosas se vuelven lentas.

Lo mismo sucede en tu código. Ya no usa la predicción de bifurcación, pero el procesador usa la predicción de salto para predecir a cuál de los cuatro punteros de función se llama, y ​​esto se ralentiza cuando los punteros de función son impredecibles.

Answer 3

¿La segunda variación es simplemente un condicional más implícito, ya que la CPU aún no puede predecir la función que se llamará? ¿Estoy en lo cierto al suponer que esto tiene que ver con la predicción del objetivo de rama?

Sí, las ramas indirectas incondicionales requieren un golpe de bifurcación-destino-búfer para que la CPU averigüe dónde obtener el código a partir de ahora. Las CPU modernas están muy segmentadas, y necesitan buscar el código mucho antes de donde se están ejecutando si van a evitar las burbujas en la tubería donde no tienen nada que hacer. Tener que esperar hasta que se calcule la magic es demasiado tarde para evitar una burbuja de búsqueda de instrucciones. Los contadores de rendimiento mostrarán que BTB falla como un error en la derivación, creo.

Como sugerí en un comentario, si puedes, debes reestructurar tu código para hacer una introducción escalar y limpiar alrededor de un bucle vectorizado. La introducción maneja los elementos hasta llegar a un elemento alineado. El bucle de limpieza maneja los casos donde hay una cantidad de elementos que no son cero para procesar, después del último vector completo. Entonces no estás atrapado haciendo un ciclo escalar solo porque el tamaño o la alineación del primer elemento no era ideal.

Dependiendo de lo que esté procesando, si está bien repetir el trabajo y superponerse, entonces puede hacer un inicio sin sucursales que haga un fragmento desalineado, luego el resto alineado. Algunas bibliotecas probablemente memset algo parecido a esto:

// not shown: check that count >= 16
endp = dest + count;
unaligned_store_16B( dest );    // e.g. x86 movdqu
dest+=16;
dest &= ~0xf;  // align by 16, first aligned write overlaps by up to 15B
for ( ; dest < endp-15 ; dest+=16) {
    aligned_store_16B( dest );  // e.g. x86 movdqa
}
// handle the last up-to-15 bytes from dest to endp similarly.

Esto hace que el manejo del inicio desalineado del bucle sea sin ramas, porque no le importa cuánto se superpone el inicio desalineado.

Sin embargo, tenga en cuenta que la mayoría de las funciones de un solo buffer no son repetibles. por ejemplo, in-place a[i] *= 2 , o sum+=a[i] necesita evitar procesar la misma entrada dos veces. Por lo general, con un bucle escalar hasta llegar a una dirección alineada. a[i] &= 0x7f , o maxval = max(a[i], maxval) son excepciones.

Las funciones con dos punteros independientes que pueden desalinearse en diferentes cantidades son más complicadas. Debe tener cuidado de no cambiar su desplazamiento relativo con enmascaramiento. memcpy es el ejemplo más simple de una función que procesa datos desde un src a un buffer de dest. memcpy tiene que funcionar si (src+3) %16 == 0 y (dest+7) %16 ==0 . A menos que pueda poner restricciones a las personas que llaman, lo mejor que puede hacer en general es tener cada carga o cada tienda alineada en el ciclo principal.

En x86, las instrucciones de movimiento movdqu ( movdqu y amigos) son tan rápidas como la versión de alineación requerida cuando la dirección está alineada . Por lo tanto, no necesita una versión separada del ciclo para el caso especial cuando src y dest tienen la misma (incorrecta) alineación, y las cargas y las tiendas se pueden alinear. IIRC, esto es cierto para Intel Nehalem y las CPU más nuevas, y para AMD reciente.

// check count >= 16
endp = dest + count;
unaligned_copy_16B( dest, src );  // load with movdqu, store with movdqu
// src+=16; dest+=16;  // combine this with aligning dest, below

dest_misalign = dest & 0xf;  // number of bytes the first aligned iteration will overlap
src  += 16 - dest_misalign;  // src potentially still misaligned
dest += 16 - dest_misalign;  // dest aligned

for ( ; dest <= endp-16 ; src+=16, dest+=16) {
    tmpvec = unaligned_load_16B( src ); // x86 movdqu is fast if src is aligned
    aligned_store_16B( dest, tmpvec );  // x86 movdqa
}
// handle the last dest to endp bytes.

Un destino alineado es probablemente más probable que una fuente alineada. No se superponen trabajos repetidos cuando el puntero que alineamos ya está alineado.

Si no está haciendo memcpy, puede ser una ventaja tener src alineado para que la carga se pliegue en otra instrucción como un operando de memoria. Esto ahorra una instrucción y, en muchos casos, también guarda un uop Intel internamente.

Para el caso en que src y dest tienen diferentes alineamientos, no he probado si es más rápido hacer cargas alineadas y tiendas desalineadas, o al revés. Escogí tiendas alineadas debido a los potenciales beneficios de reenvío de carga de tienda para breves amortiguadores. Si el búfer de destino está alineado, y solo un par de vectores es largo, y se leerá de nuevo de inmediato, las cargas alineadas de dest se detendrán durante ~ 10 ciclos (Intel SnB) si la carga cruza un límite entre dos tiendas precedentes que no tienen acceso t llegó a la memoria caché L1 todavía. (es decir, el reenvío de la tienda falla). Consulte http://agner.org/optimize/ para obtener información sobre detalles de bajo nivel como este (especialmente la guía de microarchivos).

El reenvío de tienda de memcpy a cargas en el siguiente ciclo solo ocurrirá si los almacenamientos intermedios son pequeños (quizás hasta 64B?), O si su próximo ciclo comienza a leer desde el final del búfer (que aún estará en el caché, incluso si el comienzo ya ha sido desalojado). De lo contrario, las tiendas al inicio del búfer habrán salido de un buffer de tienda a L1, por lo que el reenvío de tienda no entrará en juego.

Es posible que para buffers grandes con diferentes alineamientos, las cargas alineadas y las tiendas desalineadas sean mejores. Solo estoy inventando cosas aquí, pero esto podría ser cierto si las tiendas desalineadas pueden retirarse rápidamente incluso si cruzan una línea de caché o página. Por supuesto, las cargas desalineadas no pueden retirarse hasta que los datos se carguen realmente. Con más instrucciones de carga / tienda en vuelo, hay menos posibilidades de que un caché pierda cosas. (Está aprovechando potencialmente más buffers de carga / memoria de la CPU). Nuevamente, pura especulación. Intenté buscar en Google si las tiendas desalineadas eran mejores o peores que las cargas desalineadas, pero solo obtuve resultados sobre cómo hacerlas, y las penalizaciones de desalineación que se aplican a ambas.