c++ - ¿Es redundante la instrucción `if` antes del módulo y antes de las operaciones de asignación?

performance arm

Question

Considere el siguiente código:

unsigned idx;
//.. some work with idx
if( idx >= idx_max )
    idx %= idx_max;

Podría ser simplificado a sólo segunda línea:

idx %= idx_max;

Y logrará el mismo resultado.

Varias veces me encontré con el siguiente código:

unsigned x;
//... some work with x
if( x!=0 )
  x=0;

Podría ser simplificado a

x=0;

Las preguntas:

• ¿Hay algún sentido para usar if y por qué? Especialmente con el conjunto de instrucciones ARM Thumb.
• ¿Podrían estos omitirse?
• ¿Qué optimización hace el compilador?

Answer 1

Considera el primer bloque de código: se trata de una microoptimización basada en las recomendaciones de Chandler Carruth para Clang (consulte here para obtener más información), sin embargo, no necesariamente sostiene que sería una microoptimización válida de esta forma (se usa más bien que ternario) o en cualquier compilador dado.

El módulo es una operación razonablemente costosa, si el código se ejecuta a menudo y hay un fuerte sesgo estadístico hacia un lado o al otro del condicional, la predicción de la rama de la CPU (dada una CPU moderna) reducirá significativamente el costo de la instrucción de la rama .

Answer 2

Hay una serie de situaciones en las que escribir una variable con un valor que ya tiene puede ser más lento que leerla, descubrir que ya tiene el valor deseado y omitir la escritura. Algunos sistemas tienen un caché de procesador que envía todas las solicitudes de escritura a la memoria inmediatamente. Si bien tales diseños no son comunes hoy en día, solían ser bastante comunes, ya que pueden ofrecer una fracción sustancial del aumento de rendimiento que puede ofrecer el caché completo de lectura / escritura, pero a una pequeña fracción del costo.

El código como el anterior también puede ser relevante en algunas situaciones de múltiples CPU. La situación más común sería cuando el código que se ejecuta simultáneamente en dos o más núcleos de CPU golpea la variable repetidamente. En un sistema de almacenamiento en caché de múltiples núcleos con un fuerte modelo de memoria, un núcleo que quiera escribir una variable debe negociar primero con otros núcleos para adquirir la propiedad exclusiva de la línea de caché que la contiene, y luego debe negociar de nuevo para renunciar a dicho control la próxima vez Cualquier otro núcleo quiere leerlo o escribirlo. Estas operaciones tienden a ser muy caras, y los costos deberán ser asumidos incluso si cada escritura simplemente almacena el valor que el almacenamiento ya tenía. Sin embargo, si la ubicación se convierte en cero y nunca se vuelve a escribir, ambos núcleos pueden mantener la línea de caché simultáneamente para un acceso de solo lectura no exclusivo y nunca más tienen que negociar más.

En casi todas las situaciones en las que múltiples CPU podrían estar golpeando una variable, la variable debería ser declarada, como mínimo, volatile . La única excepción, que podría ser aplicable aquí, sería en los casos en que todas las escrituras en una variable que ocurran después del inicio de main() almacenarán el mismo valor, y el código se comportará correctamente ya sea que haya o no un almacén de una CPU visible en otro. Si realizar una operación varias veces sería un desperdicio pero de otra manera sería inofensivo, y el propósito de la variable es decir si debe hacerse, entonces muchas implementaciones pueden generar un mejor código sin el calificador volatile que con, siempre que no lo hagan. No intente mejorar la eficiencia haciendo que la escritura sea incondicional.

Incidentalmente, si se accediera al objeto a través del puntero, habría otra razón posible para el código anterior: si una función está diseñada para aceptar un objeto const en el que cierto campo es cero, o un objeto no const que debería tener ese campo puesto a cero, código como el anterior puede ser necesario para asegurar un comportamiento definido en ambos casos.

Answer 3

Parece una mala idea usar el si existe, para mí.

Tienes razón. Sea o no idx >= idx_max , estará bajo idx_max después de idx %= idx_max . Si idx < idx_max , no se modificará, se siga si se sigue o no.

Si bien podría pensar que las ramificaciones en torno al módulo pueden ahorrar tiempo, el verdadero culpable, diría, es que cuando se siguen las sucursales, las CPU modernas tienen que restablecer su canalización, y eso cuesta mucho tiempo. Mejor no tener que seguir una rama, que hacer un módulo de enteros, que cuesta aproximadamente tanto tiempo como una división de enteros.

EDITAR: Resulta que el módulo es bastante lento en comparación con la rama, como lo sugieren otros aquí. Aquí hay un tipo que examina esta misma pregunta: CppCon 2015: Chandler Carruth "Afinación de C ++ : Puntos de referencia, CPUs y compiladores. ¡Oh Dios mío!" (sugerido en otra pregunta SO vinculada a otra respuesta a esta pregunta).

Este tipo escribe compiladores, y pensó que sería más rápido sin la rama; pero sus puntos de referencia demostraron que estaba equivocado. Incluso cuando la rama se tomó solo el 20% del tiempo, probó más rápido.

Otra razón para no tener el if: una línea de código menos para mantener, y para que otra persona pueda descifrar qué significa. El chico en el enlace anterior en realidad creó una macro de "módulo más rápido". En mi humilde opinión, esta o una función en línea es el camino a seguir para aplicaciones de rendimiento crítico, porque su código será mucho más comprensible sin la rama, pero se ejecutará tan rápido.

Finalmente, el chico en el video anterior está planeando hacer que esta optimización sea conocida por los compiladores del compilador. Por lo tanto, el if probablemente se agregará para usted, si no está en el código. Por lo tanto, solo el mod solo servirá, cuando esto ocurra.

Answer 4

Si desea comprender lo que está haciendo el compilador, necesitará simplemente jalar un poco de ensamblaje. Recomiendo este sitio (ya ingresé el código de la pregunta): https://godbolt.org/g/FwZZOb .

El primer ejemplo es más interesante.

int div(unsigned int num, unsigned int num2) {
    if( num >= num2 ) return num % num2;
    return num;
}

int div2(unsigned int num, unsigned int num2) {
    return num % num2;
}

Genera:

div(unsigned int, unsigned int):          # @div(unsigned int, unsigned int)
        mov     eax, edi
        cmp     eax, esi
        jb      .LBB0_2
        xor     edx, edx
        div     esi
        mov     eax, edx
.LBB0_2:
        ret

div2(unsigned int, unsigned int):         # @div2(unsigned int, unsigned int)
        xor     edx, edx
        mov     eax, edi
        div     esi
        mov     eax, edx
        ret

Básicamente, el compilador no optimizará la rama, por razones muy específicas y lógicas. Si la división entera fuera aproximadamente el mismo costo que la comparación, entonces la rama sería bastante inútil. Pero la división de enteros (cuyo módulo se realiza en forma conjunta) generalmente es muy costosa: http://www.agner.org/optimize/instruction_tables.pdf . Los números varían mucho según la arquitectura y el tamaño de los enteros, pero por lo general podría ser una latencia de entre 15 y 100 ciclos.

Al tomar una rama antes de realizar el módulo, puede ahorrar mucho trabajo. Sin embargo, tenga en cuenta que el compilador tampoco transforma el código sin una rama en una rama en el nivel de ensamblaje. Esto se debe a que la rama también tiene un inconveniente: si el módulo termina siendo necesario de todos modos, simplemente perdió un poco de tiempo.

No hay manera de hacer una determinación razonable acerca de la optimización correcta sin conocer la frecuencia relativa con la cual idx < idx_max será verdadera. Así que los compiladores (gcc y clang hacen lo mismo) optan por mapear el código de una manera relativamente transparente, dejando esta opción en manos del desarrollador.

Así que esa rama podría haber sido una opción muy razonable.

La segunda rama debe ser completamente inútil, porque la comparación y la asignación tienen un costo comparable. Dicho esto, puede ver en el enlace que los compiladores aún no realizarán esta optimización si tienen una referencia a la variable. Si el valor es una variable local (como en su código demostrado), el compilador optimizará la rama.

En resumen, la primera parte del código es quizás una optimización razonable, la segunda, probablemente solo un programador cansado.