productivo - ejercicios resueltos de cuello de botella

C-tiene un bucle simple que hace cálculo aritmético; Profiler muestra que esto es un cuello de botella. ¿Cómo acelerarlo?

Question

Mi primera publicación aquí. Un gran sitio y recurso.

Busqué un poco y miré las preguntas con títulos similares, pero no pude encontrar algo específicamente sobre esto.

Estoy tratando de eliminar cualquier redundancia e hinchazón de una biblioteca de cálculo astronómico C que utiliza mi programa C ++. Ejecuté un perfilador simple (VerySleepy).

Aquí está el código que el generador de perfiles mostró como el que más tiempo utiliza (aparte de las funciones de la biblioteca C sprintf, etc.):

double swi_echeb(const double x, const double* const coef, const int ncf)
{
    int j = ncf - 1;
    double x2, br, brp2, brpp;
    x2 = x * 2.;
    br = 0.;
    brp2 = 0.;  /* dummy assign to silence gcc warning */
    brpp = 0.;

    for (; j >= 0; --j) {                 // <-- 0.39s
        brp2 = brpp;                      // <-- 0.01s
        brpp = br;                        // <-- 0.32s
        br = x2 * brpp - brp2 + coef[j];  // <-- 3.49s ***
    }                                     // <-- 0.14s

    return (br - brp2) * .5;              // <-- 0.06s
}                                         // <-- 0.05s

Esta función en particular está profundamente arraigada en otros y la función principal de "inicio" a la que llama mi programa se llama miles de veces.

Puede ver la declaración destacada con 3.49s mucho más alta que todos los demás tiempos de declaración. Sé que hay formas de acelerar la aritmética C con el uso de la multiplicación sobre la división cuando sea posible. Pero no sé mucho más que eso.

Me gusta:

1. ¿Sería mejor dividir esta declaración en pedazos más pequeños ?:

   br = x2 * brpp;

   br -= brp2;

   br += coef[j];

Cualquier otra idea o crítica. No escribí este código, aunque agregué el const a los parámetros de la función porque me encanta la corrección de const.

Nunca he intentado usar registros u otros trucos de fantasía para acelerar las cosas antes. ¿Alguien piensa que algo así puede funcionar aquí?

Sé que la gente dirá: "Pruébalo". Así que lo haré, y actualizaré lo que obtengo si ayuda a alguien con preguntas aritméticas similares.

EDITAR: Publicando resultados que he probado a partir de sugerencias

En orden de más rápido a más lento, aquí están los que he encontrado hasta ahora. Profiler es VerySleepy. El compilador es Visual Studio 2008 Pro Ed. Las opciones de compilación para la biblioteca y mi aplicación son:

Debug, C7 format, /O2 /Ob2 /Oi /Ot /Oy /GT /GL /GF /FD /MTd /GS- /Gy /fp:fast /FAs

La siguiente es la sugerencia de Andrew sobre hacer "4 iteraciones por ciclo". Fue el más rápido hasta ahora.

TIEMPO TOTAL gastado en la función (los tiempos de las otras declaraciones en la función no se muestran aquí) = 2.08 segundos

for (; index >= 3; index -= 4) {                    // 0.02s
    brp2    = brpp;
    brpp    = br;                                   // 0.02s
    br      = x2 * brpp - brp2 + coef[index];       // 0.25s
    brp2    = brpp;
    brpp    = br;                                   // 0.13s
    br      = x2 * brpp - brp2 + coef[index - 1];   // 0.33s
    brp2    = brpp;
    brpp    = br;                                   // 0.13s
    br      = x2 * brpp - brp2 + coef[index - 2];   // 0.34s
    brp2    = brpp;
    brpp    = br;                                   // 0.14s
    br      = x2 * brpp - brp2 + coef[index - 3];   // 0.42s
}

for (; index >= 0; --index) {                 // 0.03s
    brp2    = brpp;                           // 0.03s
    brpp    = br;
    br      = x2 * brpp - brp2 + coef[index]; // 0.11s
}

El siguiente más rápido fue el código original sin modificaciones, con un tiempo total de 2,39 segundos dentro de la función, nuevamente incluyendo las declaraciones fuera del ciclo. Tenga en cuenta que esto es menos que mi publicación original. Mi publicación original era un código no optimizado, pero como todos lo sugirieron, todas mis pruebas fueron optimizadas lo más posible en VS08:

for (j = ncf - 1; j >= 0; j--) {      // 0.02s
    brp2 = brpp;                      // 0.03s
    brpp = br;                        // 0.07s
    br = x2 * brpp - brp2 + coef[j];  // 2.14s
}

Después de este código original, el siguiente más rápido fue la idea de Drew de establecer el puntero por adelantado y usarlo. El tiempo total dedicado a la función interna fue de 2.49 segundos , incluidos los tiempos de las declaraciones fuera del ciclo:

for (; index >= coef; --index) {         // 0.01s
    brp2    = brpp;
    brpp    = br;                        // 0.06s
    br      = x2 * brpp - brp2 + *index; // 2.24s
}

También probé una combinación del desenrollamiento del lazo de Andrew y el uso del puntero de Drew, pero eso tomó 2.39 segundos , lo mismo que el código inalterado.

De acuerdo con los resultados, el desenrollado de bucles es el camino a seguir para mi uso.

Answer 1

Nunca he intentado usar registros u otros trucos de fantasía para acelerar las cosas antes. ¿Alguien piensa que algo así puede funcionar aquí?

Hay un truco de registro muy fácil que cualquiera puede hacer. Construye el proyecto para una CPU reciente. ¿Este código necesita ejecutarse en una computadora desde 1995? 2000? 2005? Si el programa puede contar con una CPU más nueva, puede contar con más registros a su disposición.

Además, la indexación entera no es necesaria. En su lugar, podría hacer j un puntero directamente al double de interés. Esto puede hacer una diferencia si su compilador de optimización no lo está haciendo.

double swi_echeb(const double x, const double* const coef, const int ncf)
{
    const double *j = &coef[ncf - 1];
    // (stuff...)

    while (true) { 
        // (stuff...)

        br = x2 * brpp - brp2 + *j;
        if ( j == coef )
            break;
        --j;
    }  
}

Answer 2

¿Cuáles son los valores típicos para ncf ? La razón principal por la que pregunto es que estás iterando coef revés. El acceso no secuencial no hace un buen uso del caché .

Answer 3

¿Necesitas la precisión completa de un doble? Mudarse a flotar podría ahorrar algo de tiempo.

Aunque el optimizador debería resolverlo, agregar una sugerencia de registro explícita a sus declaraciones de variables no podría perjudicar:

register double x2, br, brp2, brpp;

También puedes intentar mover el coef a un registro:

register double* rc;
rc = coef;
. . .
br = x2 * brpp - brp2 + rc[j];

No sé sobre este caso en particular, pero he visto una cantidad sorprendente de casos en que el compilador no optimiza correctamente las expresiones compuestas. Puede aumentar las posibilidades de que haga lo correcto dividiéndolo en simples expresiones de dos componentes:

brp2 = brpp;     
brpp = br;
br = x2 * brpp;
br -= brp2;
br += rc[j];

Puede echar un vistazo al código generado para ver si hay ineficiencias obvias.

Answer 4

Bueno, a menos que haya algunos problemas especiales, ¿cómo es la matriz de coeficientes lo suficientemente grande como para intercambiar? - Probablemente estés muy cerca.

• Se debe intentar la noción de Andrew de desenrollar bucles.
• Definitivamente, asegúrese de tener la optimización activada con -O3

Después de eso, tendrá que mirar el lenguaje ensamblador o el paralelismo.

Answer 5

El principal "problema" con ese código es que tienes una ruta crítica a lo largo de br . No puede comenzar a calcular la siguiente iteración antes de haber terminado completamente la anterior. Esto también prohíbe las instrucciones vectoriales: no hay nada que vectorizar.

Tengo la impresión de que los coeficientes numéricos siempre son más bien (¿un solo dígito?) Y el tiempo de ejecución se deriva de la cantidad de llamadas a esa función.

Una forma de mitigar eso es calcular la evaluación de múltiples polinomios a la vez. Por supuesto, esto depende de un diseño especial de sus estructuras de datos: los coeficientes de cierto grado tienen que estar en una matriz lineal, por lo que pueden cargarse mediante una única instrucción vectorial.

Answer 6

Esta operación es una ligera variación de una suma / exploración de prefijos. (Es una exploración de 3 operaciones, 2 historias). El limitador clave para el rendimiento aquí es más que probable la serialización (de sus operaciones de matemáticas en el conducto de instrucciones) causada por las dependencias de bucle cruzado, por lo que es poco probable que el bucle en serie ayude mucho aquí.

Hay formas estándar de paralelizar sumas de prefijo (ver wikipedia), que podrían usarse para acelerar esto. Incluso con un hilo, usted podría mejorar enormemente su eficiencia al subdividir el conjunto de coeficientes en 4 matrices secundarias y calcular el prefijo para cada una de ellas por iteración de bucle: las cuatro corrientes de cálculo son independientes y se canalizarán correctamente. por tu hardware Además, dado que son independientes, usted (o su compilador si tiene la suerte, pero lo dudo) puede utilizar SSE o AVX en un x86 para procesar el conjunto en paralelo.

Una vez que tenga los cuatro resultados acumulados (es probable que los resultados sean pares ya que tiene una suma de prefijos de 2 historias), puede combinarlos de la manera matemáticamente adecuada para su secuencia.

Answer 7

Este es un caso en el que el generador de perfiles encuentra lo que cabría esperar. Mire el código: tiene una configuración de bucle ("oh, eso se ejecuta una vez, no ocupará nada") y un bucle. Dentro del ciclo, tienes dos asignaciones ("no, esas son baratas") y precisamente una línea de código que hace una multiplicación, dos adiciones y una matriz de referencia.

No va a conseguir que esta función se ejecute mucho más rápido con micro-optimizaciones. El procesador en realidad está gastando su tiempo en hacer el trabajo que desea que la función haga, sí, lo sé, es impactante.

Su mejor apuesta es subir un nivel o dos. ¿Cómo se puede reducir el número de veces que se llama a esta función? ¿Lo están llamando con los mismos parámetros varias veces para que pueda almacenar en caché los resultados? ¿Hay lugares donde puede usar menos coeficientes, reduciendo el número de veces que se ejecuta el bucle?

Answer 8

Esto parece ser un problema de caché, no de aritmética.

for (; j >= 0; --j) {
    ...
    ... coef[j];
}

Estás accediendo a una matriz aquí, y estás disminuyendo un índice para hacerlo. Esta acción realmente puede interrumpir la localidad amigable con el caché inherente en un bucle simple.

¿Es posible contar hacia adelante? Es decir,

for (int i = 0; i <= j; i++) {
    ...
    ... coef[i];
}

¿Sería su cálculo válido?

Answer 9

Lo primero que intentaría sería iterar en pasos de 4, es decir: j + = 4 (o en su caso, j - = 4) y semi-desenrollar el ciclo. El motivo es que ayudará al compilador a realizar optimizaciones de SSE y a acceder a la memoria por lotes desde la memoria principal a la memoria caché. Solo tenga en cuenta que tendrá que atender los últimos elementos en caso de que el recuento de bucles no sea divisible por 4. Por ejemplo:

// Disclaimer: I have not tested this code!
for (; j >= 3; j -= 4) {              
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j]; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j-1]; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j-2]; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef[j-3]; 
}                          
// if (j % 4) != 0 before the loop operation, 
// handle 1, 2 or 3 remaining elements here

Lo segundo que intentaría sería precargar coeff [j] en un registro inmediato antes del cálculo. La razón de esto es que los cálculos de punto flotante están canalizados, lo que significa que el acceso a la memoria en el lugar incorrecto puede tener efectos adversos en el rendimiento. El cálculo en sí puede ser muy rápido, pero podría tomar 14 instrucciones solo para poner en cola los datos de la memoria caché en la FPU. Agregar a eso un acceso desde la memoria principal puede empeorar. Por ejemplo, intente esto (también podría probarse con y sin el - = 4 desenrollar)

// Disclaimer: I have not tested this code!
register double coef1, coef2, coef3, ceof4;
for (; j >= 3; j -= 4) {           
    coef1 = coef[j];    // Preloads the 4 sequential coeffs from 
    coef2 = coef[j-1];  // main memory to cache (if available)
    coef3 = coef[j-2];  
    coef4 = coef[j-3];  
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef1; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef2; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef3; 
    brp2 = brpp;                      
    brpp = br;                        
    br = x2 * brpp - brp2 + coef4; 
} 

En este caso, las variables double x2, br, brp2, brpp, coef1, coef2, coef3, coef4 deben registrarse, si es posible.

Finalmente, utilizando lo anterior, ¿puede aplicarle la optimización SSE / SSE2? Asegúrate de que esté habilitado en el compilador de GCC (estoy acostumbrado a VS, por lo que el equivalente sería el modo de lanzamiento activado, los símbolos de depuración desactivados, la optimización activada, SSE2 activada) y el código de referencia sin el depurador adjunto. Esto solo puede tener un efecto dramático en el rendimiento.

Déjenos saber los resultados. Ajuste de rendimiento es de prueba y error!

La mejor de las suertes,

Answer 10

Si va con la sugerencia de Drew de usar un puntero en lugar de una indexación de matriz, podría ser necesario restringir el puntero para ver cualquier beneficio:

...
double *restrict index = coef + ncf - 1;
...
for (; index >= coef; --index) {
    brp2    = brpp;
    brpp    = br;
    br      = x2 * brpp - brp2 + *index;
}

Esto podría ayudar a la optimización del caché, porque el compilador puede estar seguro de que nadie cambiará el valor al que apunta el index .

Además, publiqué un problema similar el año pasado, que obtuvo varias respuestas excelentes. Asegúrate de echarle un vistazo .