c++ - reproducir - ¿Cómo puede agregar código a un bucle para hacerlo más rápido?

meta tags ejemplos

Question

Tengo una función simple con un bucle interno: escala el valor de entrada, busca un valor de salida en una tabla de búsqueda y lo copia en el destino. (ftol_ambient es un truco que copié de la web para una conversión rápida de float a int).

for (i = 0;  i < iCount;  ++i)
{
    iScaled = ftol_ambient(*pSource * PRECISION3);
    if (iScaled <= 0)
        *pDestination = 0;
    else if (iScaled >= PRECISION3)
        *pDestination = 255;
    else
    {
        iSRGB = FloatToSRGBTable3[iScaled];
        *pDestination = iSRGB;
    }
    pSource++;
    pDestination++;
}

Ahora mi tabla de búsqueda es finita, y las carrozas son infinitas, por lo que existe la posibilidad de errores uno a uno. Creé una copia de la función con algún código para manejar ese caso. Tenga en cuenta que la única diferencia son las 2 líneas de código agregadas; ignore el feo lanzamiento de puntero.

for (i = 0;  i < iCount;  ++i)
{
    iScaled = ftol_ambient(*pSource * PRECISION3);
    if (iScaled <= 0)
        *pDestination = 0;
    else if (iScaled >= PRECISION3)
        *pDestination = 255;
    else
    {
        iSRGB = FloatToSRGBTable3[iScaled];
        if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))
            ++iSRGB;
        *pDestination = (unsigned char) iSRGB;
    }
    pSource++;
    pDestination++;
}

Aquí está la parte extraña. Estoy probando ambas versiones con una entrada idéntica de 100000 elementos, repetida 100 veces. En mi Athlon 64 1.8 GHz (modo de 32 bits), la primera función demora 0.231 segundos, y la segunda función (más larga) demora 0.185 segundos. Ambas funciones son adyacentes en el mismo archivo fuente, por lo que no hay posibilidad de configuraciones de compilador diferentes. He corrido las pruebas muchas veces, revirtiendo el orden en que se ejecutan, y los tiempos son más o menos los mismos todo el tiempo.

Sé que hay muchos misterios en los procesadores modernos, pero ¿cómo es posible?

Aquí, para comparar, están las salidas de ensamblaje relevantes del compilador Microsoft VC ++ 6.

; 173  :    for (i = 0;  i < iCount;  ++i)

$L4455:

; 174  :    {
; 175  :        iScaled = ftol_ambient(*pSource * PRECISION3);

    fld DWORD PTR [esi]
    fmul    DWORD PTR __real@4@400b8000000000000000
    fstp    QWORD PTR $T5011[ebp]

; 170  :    int i;
; 171  :    int iScaled;
; 172  :    unsigned int iSRGB;

    fld QWORD PTR $T5011[ebp]

; 173  :    for (i = 0;  i < iCount;  ++i)

    fistp   DWORD PTR _i$5009[ebp]

; 176  :        if (iScaled <= 0)

    mov edx, DWORD PTR _i$5009[ebp]
    test    edx, edx
    jg  SHORT $L4458

; 177  :            *pDestination = 0;

    mov BYTE PTR [ecx], 0

; 178  :        else if (iScaled >= PRECISION3)

    jmp SHORT $L4461
$L4458:
    cmp edx, 4096               ; 00001000H
    jl  SHORT $L4460

; 179  :            *pDestination = 255;

    mov BYTE PTR [ecx], 255         ; 000000ffH

; 180  :        else

    jmp SHORT $L4461
$L4460:

; 181  :        {
; 182  :            iSRGB = FloatToSRGBTable3[iScaled];
; 183  :            *pDestination = (unsigned char) iSRGB;

    mov dl, BYTE PTR _FloatToSRGBTable3[edx]
    mov BYTE PTR [ecx], dl
$L4461:

; 184  :        }
; 185  :        pSource++;

    add esi, 4

; 186  :        pDestination++;

    inc ecx
    dec edi
    jne SHORT $L4455

$L4472: ; 199 : { ; 200 : iScaled = ftol_ambient(*pSource * PRECISION3); fld DWORD PTR [esi] fmul DWORD PTR __real@4@400b8000000000000000 fstp QWORD PTR $T4865[ebp] ; 195 : int i; ; 196 : int iScaled; ; 197 : unsigned int iSRGB; fld QWORD PTR $T4865[ebp] ; 198 : for (i = 0; i < iCount; ++i) fistp DWORD PTR _i$4863[ebp] ; 201 : if (iScaled <= 0) mov edx, DWORD PTR _i$4863[ebp] test edx, edx jg SHORT $L4475 ; 202 : *pDestination = 0; mov BYTE PTR [edi], 0 ; 203 : else if (iScaled >= PRECISION3) jmp SHORT $L4478 $L4475: cmp edx, 4096 ; 00001000H jl SHORT $L4477 ; 204 : *pDestination = 255; mov BYTE PTR [edi], 255 ; 000000ffH ; 205 : else jmp SHORT $L4478 $L4477: ; 206 : { ; 207 : iSRGB = FloatToSRGBTable3[iScaled]; xor ecx, ecx mov cl, BYTE PTR _FloatToSRGBTable3[edx] ; 208 : if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource)) mov edx, DWORD PTR _SRGBCeiling[ecx*4] cmp edx, DWORD PTR [esi] jg SHORT $L4481 ; 209 : ++iSRGB; inc ecx $L4481: ; 210 : *pDestination = (unsigned char) iSRGB; mov BYTE PTR [edi], cl $L4478: ; 211 : } ; 212 : pSource++; add esi, 4 ; 213 : pDestination++; inc edi dec eax jne SHORT $L4472 Edición: tratando de probar la hipótesis de Nils Pipenbrinck , agregué un par de líneas antes y dentro del ciclo de la primera función:

int one = 1;
int two = 2;

        if (one == two)
            ++iSRGB;

El tiempo de ejecución de la primera función ahora es de 0.152 segundos. Interesante.

Editar 2: Nils señaló que la comparación se optimizaría a partir de una compilación de lanzamiento, y de hecho lo es. Los cambios en el código de ensamblaje son muy sutiles, lo publicaré aquí para ver si proporciona alguna pista. En este punto, me pregunto si es la alineación del código.

; 175  :    for (i = 0;  i < iCount;  ++i)

$L4457:

; 176  :    {
; 177  :        iScaled = ftol_ambient(*pSource * PRECISION3);

    fld DWORD PTR [edi]
    fmul    DWORD PTR __real@4@400b8000000000000000
    fstp    QWORD PTR $T5014[ebp]

; 170  :    int i;
; 171  :    int iScaled;
; 172  :    int one = 1;

    fld QWORD PTR $T5014[ebp]

; 173  :    int two = 2;

    fistp   DWORD PTR _i$5012[ebp]

; 178  :        if (iScaled <= 0)

    mov esi, DWORD PTR _i$5012[ebp]
    test    esi, esi
    jg  SHORT $L4460

; 179  :            *pDestination = 0;

    mov BYTE PTR [edx], 0

; 180  :        else if (iScaled >= PRECISION3)

    jmp SHORT $L4463
$L4460:
    cmp esi, 4096               ; 00001000H
    jl  SHORT $L4462

; 181  :            *pDestination = 255;

    mov BYTE PTR [edx], 255         ; 000000ffH

; 182  :        else

    jmp SHORT $L4463
$L4462:

; 183  :        {
; 184  :            iSRGB = FloatToSRGBTable3[iScaled];

    xor ecx, ecx
    mov cl, BYTE PTR _FloatToSRGBTable3[esi]

; 185  :            if (one == two)
; 186  :                ++iSRGB;
; 187  :            *pDestination = (unsigned char) iSRGB;

    mov BYTE PTR [edx], cl
$L4463:

; 188  :        }
; 189  :        pSource++;

    add edi, 4

; 190  :        pDestination++;

    inc edx
    dec eax
    jne SHORT $L4457

Answer 1

¿Cómo estás cronometrando estas rutinas? Me pregunto si la paginación o el almacenamiento en caché está teniendo un efecto en los tiempos? Es posible que la invocación de la primera rutina cargue ambos en la memoria, cruce un límite de página o haga que la pila cruce a una página no válida (lo que causa una entrada de página), pero solo la primera rutina paga el precio.

Es posible que desee ejecutar ambas funciones una vez antes de realizar las llamadas que toman las medidas para reducir los efectos que pueden tener la memoria virtual y el almacenamiento en caché.

Answer 2

¿Estás probando este circuito interno o estás probando también tu circuito externo no divulgado? Si es así, mira estas tres líneas:

if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))  
    ++iSRGB;
*pDestination = (unsigned char) iSRGB;

Ahora, parece que *pDestination es el contador del bucle externo. Por lo tanto, al hacer un incremento adicional del valor de iSRGB se salta algunas de las iteraciones en el bucle externo, reduciendo así la cantidad total de trabajo que el código necesita hacer.

Answer 3

Mi primera suposición es que la rama se predice mejor en el segundo caso. Posiblemente porque el if anidado proporciona cualquier algoritmo en el que el procesador use más información para adivinar. Solo por curiosidad, ¿qué pasa cuando quitas la línea?

if (((int *)SRGBCeiling)[iSRGB] <= *((int *)pSource))

?

Answer 4

Mi suposición es que, en el primer caso, dos ramas diferentes terminan en la misma ranura de predicción de bifurcación de la CPU. Si estas dos ramas predicen diferente cada vez que el código se ralentizará.

En el segundo ciclo, el código agregado puede ser suficiente para mover una de las ramas a una ranura de predicción de bifurcación diferente.

Para asegurarse de que puede probar el analizador Intel VTune o la herramienta CodeAnalyst de AMD. Estas herramientas le mostrarán qué está sucediendo exactamente en su código.

Sin embargo, tenga en cuenta que probablemente no valga la pena optimizar este código aún más. Si sintoniza su código para que sea más rápido en su CPU, puede al mismo tiempo volverse más lento en una marca diferente.

EDITAR:

Si desea leer sobre la predicción de bifurcación, pruebe el excelente sitio web de Agner Fog: http://www.agner.org/optimize/

Este pdf explica la asignación de ranura de predicción de ramas en detalle: http://www.agner.org/optimize/microarchitecture.pdf

Answer 5

Una vez tuve una situación similar. Levanté un código de un bucle para hacerlo más rápido, pero se hizo más lento. Confuso. Resulta que, el promedio de veces que el ciclo fue menor a 1.

La lección (que no necesitas, obviamente) es que un cambio no hace que tu código sea más rápido a menos que lo midas realmente más rápido.