¿Existe una sugerencia del compilador para que GCC fuerce la predicción de rama para que siempre vaya de cierta manera?

118

Para las arquitecturas Intel, ¿hay alguna forma de instruir al compilador GCC para que genere código que siempre fuerce la predicción de ramas de una manera particular en mi código? ¿El hardware de Intel incluso es compatible con esto? ¿Qué pasa con otros compiladores o hardware?

Usaría esto en código C ++ donde sé el caso en el que deseo correr rápido y no me importa la ralentización cuando la otra rama debe tomarse incluso cuando ha tomado esa rama recientemente.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

Como pregunta de seguimiento para Evdzhan Mustafa, ¿puede la sugerencia simplemente especificar una sugerencia por primera vez que el procesador encuentra la instrucción, todas las predicciones de bifurcaciones posteriores, funcionando normalmente?

WilliamKF
fuente
también podría lanzar una excepción si algo se vuelve anormal (que es independiente del compilador)
Shep

Respuestas:

9

A partir de C ++ 20, los atributos probables e improbables deben estandarizarse y ya son compatibles con g ++ 9 . Entonces, como se discutió aquí , puede escribir

if (a>b) {
  /* code you expect to run often */
  [[likely]] /* last statement */
}

Por ejemplo, en el siguiente código, el bloque else se inserta gracias al [[unlikely]]bloque in the if

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}

enlace godbolt comparando la presencia / ausencia del atributo

pseyfert
fuente
¿Por qué usar [[unlikely]]en ifvs [[likely]]en el else?
WilliamKF
sin razón, simplemente terminé en esta constelación después de probar dónde debe ir el atributo.
pseyfert
Muy genial. Lástima que el método no sea aplicable a versiones anteriores de C ++.
Maxim Egorushkin
Fantástico enlace de Godbolt
Lewis Kelsey
87

GCC admite la función __builtin_expect(long exp, long c)para proporcionar este tipo de característica. Puedes consultar la documentación aquí .

Donde expse usa la condición y ces el valor esperado. Por ejemplo, en tu caso querrías

if (__builtin_expect(normal, 1))

Debido a la sintaxis incómoda, esto se usa generalmente para definir dos macros personalizadas como

#define likely(x)    __builtin_expect (!!(x), 1)
#define unlikely(x)  __builtin_expect (!!(x), 0)

solo para facilitar la tarea.

Tenga en cuenta que:

  1. esto no es estándar
  2. un compilador / predictor de rama de cpu probablemente sea más hábil que usted para decidir tales cosas, por lo que esto podría ser una microoptimización prematura
Jack
fuente
3
¿Hay alguna razón por la que muestra una macro y no una constexprfunción?
Columbo
22
@Columbo: No creo que una constexprfunción pueda reemplazar esta macro. Tiene que estar ifdirectamente en la declaración, creo. La misma razón assertnunca podría ser una constexprfunción.
Mooing Duck
1
@MooingDuck Estoy de acuerdo, aunque hay más razones para afirmar .
Shafik Yaghmour
7
@Columbo una razón para usar una macro sería porque este es uno de los pocos lugares en C o C ++ donde una macro es más semánticamente correcta que una función. La función solo parece funcionar debido a la optimización ( es una optimización: constexprsolo habla de semántica de valor, no de la inserción del ensamblado específico de implementación); la interpretación sencilla (no en línea) del código no tiene sentido. No hay ninguna razón para usar una función para esto.
Leushenko
2
@Leushenko Considere que en __builtin_expectsí mismo es una sugerencia de optimización, por lo que argumentar que un método que simplifica su uso depende de la optimización no es ... convincente. Además, no agregué el constexprespecificador para que funcione en primer lugar, sino para que funcione en expresiones constantes. Y sí, hay razones para usar una función. Por ejemplo, no quisiera contaminar todo mi espacio de nombres con un lindo nombre como likely. Tendría que usar LIKELY, por ejemplo , para enfatizar que es una macro y evitar colisiones, pero eso es simplemente feo.
Columbo
46

gcc tiene long __builtin_expect (long exp, long c) ( énfasis mío ):

Puede usar __builtin_expect para proporcionar al compilador información de predicción de rama. En general, debería preferir utilizar la retroalimentación de perfil real para esto (-fprofile-arcs), ya que los programadores son notoriamente malos para predecir cómo funcionan realmente sus programas . Sin embargo, hay aplicaciones en las que estos datos son difíciles de recopilar.

El valor de retorno es el valor de exp, que debe ser una expresión integral. La semántica del incorporado es que se espera que exp == c. Por ejemplo:

if (__builtin_expect (x, 0))
   foo ();

indica que no esperamos llamar a foo, ya que esperamos que x sea cero. Dado que está limitado a expresiones integrales para exp, debe usar construcciones como

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

al probar valores de puntero o punto flotante.

Como señala la documentación, debería preferir usar comentarios de perfil reales y este artículo muestra un ejemplo práctico de esto y cómo, en su caso, al menos termina siendo una mejora con respecto al uso __builtin_expect. Consulte también ¿Cómo utilizar optimizaciones guiadas por perfiles en g ++? .

También podemos encontrar un artículo para principiantes del kernel de Linux sobre las macros del kernel probables () e improbables () que usan esta función:

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

Tenga !!en cuenta el uso en la macro, podemos encontrar la explicación para esto en ¿Por qué usar !! (condición) en lugar de (condición) .

El hecho de que esta técnica se use en el kernel de Linux no significa que siempre tenga sentido usarla. Podemos ver en esta pregunta que recientemente respondí la diferencia entre el rendimiento de la función al pasar el parámetro como constante o variable de tiempo de compilación que muchas técnicas de optimización hechas a mano no funcionan en el caso general. Necesitamos perfilar el código cuidadosamente para comprender si una técnica es efectiva. Es posible que muchas técnicas antiguas ni siquiera sean relevantes con las optimizaciones modernas del compilador.

Tenga en cuenta que, aunque los elementos integrados no son portátiles, el clang también admite __builtin_expect .

Además, en algunas arquitecturas puede que no suponga una diferencia .

Shafik Yaghmour
fuente
Lo que es suficientemente bueno para el kernel de Linux no es suficiente para C ++ 11.
Maxim Egorushkin
@MaximEgorushkin nota, en realidad no recomiendo su uso, de hecho, la documentación de gcc que cito, que es mi primera cita, ni siquiera usa esa técnica. Yo diría que el objetivo principal de mi respuesta es considerar las alternativas cuidadosamente antes de seguir esta ruta.
Shafik Yaghmour
44

No no hay. (Al menos en procesadores x86 modernos).

__builtin_expectmencionado en otras respuestas influye en la forma en que gcc organiza el código ensamblador. No influye directamente en el predictor de rama de la CPU.Por supuesto, habrá efectos indirectos en la predicción de rama causados ​​por reordenar el código. Pero en los procesadores x86 modernos no hay instrucción que le diga a la CPU "suponga que esta rama está / no está tomada".

Consulte esta pregunta para obtener más detalles: ¿Se utilizó realmente la predicción de rama de prefijo Intel x86 0x2E / 0x3E?

Para ser claros, __builtin_expecty / o el uso de -fprofile-arcs puede mejorar el rendimiento de su código, tanto dando pistas al predictor de rama a través del diseño del código (consulte Optimizaciones de rendimiento del ensamblaje x86-64: predicción de alineación y rama ) como también mejorando el comportamiento de la caché manteniendo el código "improbable" lejos del código "probable".

Artelius
fuente
9
Esto es incorrecto. En todas las versiones modernas de x86, el algoritmo de predicción predeterminado es predecir que las ramas hacia adelante no se toman y las hacia atrás (consulte software.intel.com/en-us/articles/… ). Entonces, al reorganizar su código, puede dar una pista de manera efectiva a la CPU. Esto es exactamente lo que hace GCC cuando usa __builtin_expect.
Nemo
6
@Nemo, ¿leíste más allá de la primera oración de mi respuesta? Todo lo que ha dicho está cubierto por mi respuesta o en los enlaces proporcionados. La pregunta planteaba si se puede "forzar la predicción de ramificaciones para que siempre vaya en cierta dirección", a lo que la respuesta es "no", y no sentí que otras respuestas fueran lo suficientemente claras al respecto.
Artelius
4
Bien, debería haber leído más detenidamente. Me parece que esta respuesta es técnicamente correcta, pero inútil, ya que el interrogador obviamente está buscando __builtin_expect. Así que esto debería ser solo un comentario. Pero no es falso, por lo que he eliminado mi voto negativo.
Nemo
En mi opinión, no es inútil; Es una aclaración útil de cómo funcionan realmente las CPU y los compiladores, lo que podría ser relevante para el análisis de rendimiento con o sin estas opciones. por ejemplo, normalmente no puede utilizar __builtin_expectpara crear trivialmente un caso de prueba con el que pueda medir perf statque tendrá una tasa de predicción errónea de rama muy alta. Solo afecta el diseño de la rama . Y por cierto, Intel desde Sandybridge o al menos Haswell no usa mucho o nada la predicción estática; siempre hay alguna predicción en el BHT, ya sea un alias obsoleto o no. xania.org/201602/bpu-part-two
Peter Cordes
24

La forma correcta de definir macros probables / improbables en C ++ 11 es la siguiente:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

Este método es compatible con todas las versiones de C ++, a diferencia de [[likely]], pero se basa en una extensión no estándar __builtin_expect.


Cuando estas macros se definieron de esta manera:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

Eso puede cambiar el significado de las ifdeclaraciones y romper el código. Considere el siguiente código:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

Y su salida:

if(a) is true
if(LIKELY(a)) is false

Como puede ver, la definición de PROBABLE usar !!como un elenco boolrompe la semántica de if.

El punto aquí no es eso operator int()y operator bool()debería estar relacionado. Cuál es una buena práctica.

Más bien, usar en !!(x)lugar de static_cast<bool>(x)pierde el contexto para las conversiones contextuales de C ++ 11 .

Maxim Egorushkin
fuente
Tenga en cuenta que las conversiones contextuales se produjeron por un defecto en 2012 e incluso a finales de 2014 todavía había divergencia de implementación. En realidad, parece que el caso al que me vinculé todavía no funciona para gcc.
Shafik Yaghmour
@ShafikYaghmour Esa es una observación interesante con respecto a la conversión contextual involucrada switch, gracias. La conversión contextual involucrada aquí es particular para el tipo booly los cinco contextos específicos enumerados allí , que no incluyen el switchcontexto.
Maxim Egorushkin
Esto solo afecta a C ++, ¿verdad? Por lo tanto, no hay razón para cambiar los proyectos de C existentes para usar (_Bool)(condition), porque C no tiene una sobrecarga de operadores.
Peter Cordes
2
En su ejemplo, usó simplemente (condition), no !!(condition). Ambos están truedespués de cambiar eso (probado con g ++ 7.1). ¿Puede construir un ejemplo que realmente demuestre el problema del que está hablando cuando usa !!booleanizar?
Peter Cordes
3
Como señaló Peter Cordes, usted dice "Cuando estas macros [están] definidas de esta manera:" y luego muestra una macro usando '!!', "puede cambiar el significado de las declaraciones if y romper el código. Considere el siguiente código:" ... y luego muestra un código que no usa '!!' en absoluto, que se sabe que está roto incluso antes de C ++ 11. Cambie la respuesta para mostrar un ejemplo en el que la macro dada (¡usando!) Falla.
Carlo Wood
18

Como las otras respuestas han sugerido adecuadamente, puede usar __builtin_expectpara darle al compilador una pista sobre cómo organizar el código ensamblador. Como señalan los documentos oficiales , en la mayoría de los casos, el ensamblador integrado en su cerebro no será tan bueno como el creado por el equipo de GCC. Siempre es mejor usar datos de perfil reales para optimizar su código, en lugar de adivinar.

En líneas similares, pero aún no mencionadas, hay una forma específica de GCC para forzar al compilador a generar código en una ruta "fría". Esto implica el uso de los atributos noinliney cold, que hacen exactamente lo que parecen. Estos atributos solo se pueden aplicar a funciones, pero con C ++ 11, puede declarar funciones lambda en línea y estos dos atributos también se pueden aplicar a funciones lambda.

Aunque esto todavía cae en la categoría general de una microoptimización y, por lo tanto, se aplica el consejo estándar (prueba, no adivines), creo que es más útil en general que __builtin_expect. Casi ninguna generación del procesador x86 usa sugerencias de predicción de rama ( referencia ), por lo que lo único que podrá afectar de todos modos es el orden del código ensamblador. Ya que sabe lo que es el código de manejo de errores o "caso de borde", puede usar esta anotación para asegurarse de que el compilador nunca predecirá una rama y lo vinculará fuera del código "caliente" al optimizar el tamaño.

Uso de muestra:

void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    
}

Aún mejor, GCC automáticamente ignorará esto a favor de la retroalimentación del perfil cuando esté disponible (por ejemplo, al compilar con -fprofile-use).

Consulte la documentación oficial aquí: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

Cody Grey
fuente
2
Los prefijos de sugerencias de predicción de rama se ignoran porque no son necesarios; puede lograr exactamente el mismo efecto simplemente reordenando su código. (El algoritmo de predicción de rama predeterminado es adivinar que las ramas hacia atrás se toman y las ramas hacia adelante no). Entonces, en efecto, puede darle una pista a la CPU, y esto es lo que __builtin_expecthace. No es en absoluto inútil. Tienes razón en que el coldatributo también es útil, pero __builtin_expectcreo que subestimas la utilidad de .
Nemo
Las CPU modernas de Intel no utilizan la predicción de rama estática. El algoritmo que describe, @Nemo, donde se predice que las ramas hacia atrás son tomadas y las ramas hacia adelante como no tomadas, se usó en procesadores anteriores, y hasta en el Pentium M más o menos, pero los diseños modernos básicamente adivinan al azar, indexando en su rama tablas en donde esperaría encontrar información en esa rama y usar cualquier información que esté allí (aunque puede ser esencialmente basura). Entonces, las sugerencias de predicción de ramas serían teóricamente útiles, pero quizás no en la práctica, razón por la cual Intel las eliminó.
Cody Gray
Para ser claros, la implementación de la predicción de ramas es extremadamente complicada, y las limitaciones de espacio en los comentarios me obligaron a simplificar demasiado. Esta sería realmente una respuesta completa en sí misma. Puede que todavía queden vestigios de predicción de ramas estáticas en las microarquitecturas modernas, como Haswell, pero no es tan simple como solía ser.
Cody Gray
¿Tiene una referencia para "las CPU Intel modernas no utilizan predicción de rama estática"? El propio artículo de Intel ( software.intel.com/en-us/articles/… ) dice lo contrario ... Pero eso es de 2011
Nemo
Realmente no tengo una referencia oficial, @Nemo. Intel es extremadamente reservado sobre los algoritmos de predicción de ramas que se utilizan en sus chips, y los trata como secretos comerciales. La mayor parte de lo que se conoce se ha descubierto mediante pruebas empíricas. Como siempre, los materiales de Agner Fog son los mejores recursos, pero incluso él dice: "El predictor de ramas parece haber sido rediseñado en Haswell, pero se sabe muy poco sobre su construcción". Desafortunadamente, no recuerdo dónde vi por primera vez los puntos de referencia que demostraban que la presión arterial estática ya no se usaba.
Cody Gray
5

__builtin_expect puede usarse para decirle al compilador en qué dirección espera que vaya una rama. Esto puede influir en cómo se genera el código. Los procesadores típicos ejecutan código secuencialmente más rápido. Entonces si escribes

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

el compilador generará código como

if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

Si su sugerencia es correcta, esto ejecutará el código sin que se realice ninguna rama. Se ejecutará más rápido que la secuencia normal, donde cada instrucción if se ramificaría alrededor del código condicional y ejecutaría tres ramificaciones.

Los procesadores x86 más nuevos tienen instrucciones para las ramas que se espera que se tomen, o para las ramas que se espera que no se tomen (hay un prefijo de instrucción; no estoy seguro de los detalles). No estoy seguro si el procesador lo usa. No es muy útil, porque la predicción de rama manejará esto bien. Así que no creo que puedas influir en la predicción de la rama .

gnasher729
fuente
2

Con respecto al OP, no, no hay forma en GCC de decirle al procesador que siempre asuma que la rama está o no tomada. Lo que tienes es __builtin_expect, que hace lo que otros dicen que hace. Además, creo que no querrá decirle al procesador si la rama está tomada o no siempre . Los procesadores actuales, como la arquitectura Intel, pueden reconocer patrones bastante complejos y adaptarse eficazmente.

Sin embargo, hay ocasiones en las que desea asumir el control de si, de forma predeterminada, se predice que una rama se tomará o no: cuando sepa que el código se llamará "frío" con respecto a las estadísticas de ramificación.

Un ejemplo concreto: código de gestión de excepciones. Por definición, el código de administración ocurrirá de manera excepcional, pero tal vez cuando ocurra se desee el máximo rendimiento (puede haber un error crítico que debe solucionarse lo antes posible), por lo que es posible que desee controlar la predicción predeterminada.

Otro ejemplo: puede clasificar su entrada y saltar al código que maneja el resultado de su clasificación. Si hay muchas clasificaciones, el procesador puede recopilar estadísticas pero perderlas porque la misma clasificación no ocurre lo suficientemente pronto y los recursos de predicción se dedican al código recientemente llamado. Me gustaría que hubiera una primitiva para decirle al procesador "por favor, no dedique recursos de predicción a este código" de la manera en que a veces puede decir "no almacenar en caché esto".

TheCppZoo
fuente