es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Optimización de std::clamp con preferencia por entradas dentro del rango: ¿hay alguna ventaja en mantener cmov en lugar de una rama?

C++17 std::clamp es una función de plantilla que asegura que el valor de entrada no sea menor que el mínimo dado y no sea mayor que el máximo dado, y devuelve el valor de entrada; de lo contrario devuelve el mínimo o el máximo respectivamente.

El objetivo es optimizarla, asumiendo lo siguiente:
* El parámetro de tipo es un entero de 32 o 64 bits
* Es más probable que el valor de entrada ya esté dentro del rango que fuera del rango, por lo que es probable que se devuelva
* Es probable que el valor de entrada se calcule poco antes, y se conoce el mínimo y máximo con antelación
* Vamos a ignorar las referencias, que pueden complicar la optimización, pero en la práctica no son útiles para los valores enteros

Tanto para la implementación estándar como para la implementación ingenua, el ensamblado generado por gcc y clang no parece favorecer la suposición de que el valor está dentro del rango. Ambas:

“`C++
#include <algorithm>

int clamp1(int v, int minv, int maxv)
{
return std::clamp(v, minv, maxv);
}

int clamp2(int v, int minv, int maxv)
{
if (maxv < v)
{
return maxv ;
}
if (v < minv)
{
return minv;
}
return v;
}

“`

Se compilan en dos cmov (https://godbolt.org/z/oedd9Yfro):
mov eax, esi
cmp edi, esi
cmovge eax, edi
cmp edx, edi
cmovl eax, edi

Intentando decirle a los compiladores que favorezcan el caso en rango con __builtin_expect (gcc parece ignorar C++20 [[likely]]):

C++

int clamp3(int v, int minv, int maxv)
{
if (__builtin_expect(maxv < v, 0))
{
return maxv;
}
if (__builtin_expect(v < minv, 0))
{
return minv;
}
return v;
}

El resultado para gcc y clang es ahora diferente (https://godbolt.org/z/s4vedo1br).
gcc todavía evita completamente las ramas usando dos cmov. clang tiene una rama, en lugar de las dos esperadas (anotación mía):
asm-x86
clamp3(int, int, int):
mov eax, edx ; result = maxv
cmp edi, esi ; v, minv
cmovge esi, edi ; if (v >= minv) minv = v
cmp edx, edi ; maxv, v
jl .LBB0_2 ; if (maxv < v) goto LBB0_2
mov eax, esi ; result = minv (after it was updated from v if no clamping)
.LBB0_2:
ret

Preguntas:
* ¿Hay desventajas significativas en el uso de saltos condicionales que se espera que vayan a la misma rama cada vez, para que gcc los evite?
* ¿Es la versión de clang con un salto condicional mejor de lo que habría sido si hubiera dos saltos?

No usar cmov es sugerido en el Manual de Referencia de Optimización de Arquitecturas Intel® 64 e IA-32, de la versión de junio de 2021, página 3-5:

Regla de codificación de compilador/ensamblador 2. (Impacto M, generalidad ML) Use las instrucciones SETCC y CMOV para eliminar las ramas condicionales impredecibles cuando sea posible. No haga esto para las ramas predecibles. No use estas instrucciones para eliminar todas las ramas condicionales impredecibles (porque el uso de estas instrucciones incurrirá en una sobrecarga de ejecución debido al requerimiento de ejecutar ambos caminos de una rama condicional). Además, convertir una rama condicional en SETCC o CMOV intercambia la dependencia de flujo de control por la dependencia de datos y restringe la capacidad del motor fuera de orden. En la optimización, tenga en cuenta que todos los procesadores Intel 64 e IA-32 suelen tener tasas muy altas de predicción de ramas. Las ramas consistentemente mal predichas son generalmente raras. Use estas instrucciones solo si el aumento en el tiempo de cálculo es menor que el costo esperado de una rama mal predicha.

Tags:  , , , ,

Answer

  1. Avatar for davy.ai

    Respuesta

    ¿Existen desventajas significativas en el uso de saltos condicionales que se espera que vayan a la misma rama cada vez, de modo que gcc los evite?

    Hay posibles desventajas en el uso de saltos condicionales que se espera que vayan a la misma rama cada vez. Aunque los saltos condicionales pueden ser costosos al lidiar con ramas impredecibles, los procesadores suelen tener altas tasas de predicción de ramas y las ramas consistentemente mal predichas son raras. El uso de instrucciones cmov para eliminar ramas condicionales impredecibles no siempre es óptimo ya que incurre en gastos generales debido al requisito de ejecutar ambas rutas de una rama condicional. Además, convertir una rama condicional en instrucciones cmov intercambia la dependencia de flujo de control por la dependencia de datos y restringe la capacidad del motor fuera de orden. Por lo tanto, el uso de instrucciones cmov solo debe implementarse si el aumento en el tiempo de procesamiento es menor que el costo esperado de una rama mal predicha.

    ¿Es la versión de clang con un salto condicional mejor que si hubiera habido dos saltos?

    En términos de rendimiento, la versión de clang con un salto condicional es mejor que si hubiera habido dos saltos. Si bien tener dos instrucciones cmov es óptimo para eliminar ramas condicionales impredecibles, no siempre es la mejor solución ya que restringe la capacidad del motor fuera de orden. La versión de clang con un salto condicional demuestra un compromiso entre el costo de la rama mal predicha y los gastos generales de ejecutar ambas rutas de una rama condicional. Es posible que para la versión de clang, el aumento en el tiempo de procesamiento debido a la rama mal predicha sea menor que el costo esperado de ejecutar ambas rutas de una rama condicional.

Comments are closed.