Cómo sugerir compilador gcc más probable rama

Question

Ejemplo:

if (almost_always_false_condition) {
       // do something
}

¿Hay una manera que sugiera compilador que en la condición 99% será falsa. El cálculo del estado de toma ~ 60 ciclos de comprobación, y no se puede calcular en tiempo de compilación propio compilador.

(gcc 4.3)

Answer 1

Si quiere sugerir al CCG que una condición es probable que tenga un valor dado como una sugerencia para organizar el flujo de código, se debe utilizar __builtin_expect( ):

if (__builtin_expect(almost_always_false_condition,0)) {
   // do something
}

Sin embargo, parece que usted quiere encontrar una manera de evitar la evaluación de la condición, que no va a hacer __builtin_expect( ). ¿Hay una manera que se puede aproximar rápidamente el estado, y sólo hacer la comprobación completa cuando la aproximación es cierto:

if (__builtin_expect(fastCheckThatIsTrueIfFullConditionIsTrue,0)) {
    // most of the time, we don't even get to here, so you don't need
    // to evaluate the condition
    if (almostAlwaysFalseCondition) {
        // do something
    }
}

Puede decirnos más sobre lo que es la condición?

Answer 2

Si el resultado podría variar durante una sola ejecución, es posible que pueda utilizar la evaluación perezosa de los operadores booleanos para dividir su condición en una pieza barata y una parte más costosa, y ejecutar la parte barato primero.

if (a == 5 && somethingexpensive())
{
   ...
}

Dado que el cálculo de a == 5 es más barato que somethingexpensive(), y si es casi siempre false se debe ejecutar en primer lugar, lo que evita la evaluación de la cláusula somethingexpensive.

Si por el contrario el resultado es constante para una ejecución del programa, se puede optimizar mediante el almacenamiento del resultado del cálculo en una variable global o estática.

static int result = doevalfunctiononlyonce();

if (result)
{
   ....    
}

De esta manera se ha reducido el costo de la if a una simple consulta de la memoria.

Si la condición sólo cambia en respuesta a una acción en otro procedimiento, se puede actualizar el mundial a este procedimiento:

int condition;

void appendToList(int a)
{
   list.append(a);
   if (list.somethingexpensive())
   {
     condition = true;
   } else
   {
     condition = false;
   }
}

void someotherfunction()
{
  // if (list.somethingexpensive())
  if (condition)
  {
    ...
  }
}

Esto es útil si someotherfunction se llama mucha más frecuencia que la función appendtolist.

Answer 3

En primer lugar, ¿cuántos ciclos se gastan en la cláusula else, o en otro lugar en el programa? Si su perfil o toma stackshots , se está gastando al menos el 10% de su tiempo en esa prueba? Si no es así, probablemente hay problemas más importantes que usted debe buscar en un primer momento.

En segundo lugar, si vas a pasar> 10% del tiempo en esa prueba, se debe mirar para ver si el algoritmo puede ajustarse para que tenga los puntos de decisión más cerca de 50-50 probabilidad. Un punto de decisión 50-50 rinde 1 bit de información cuando se ejecuta, mientras que un punto de decisión 99-1 sólo produce alrededor de .07 bits. * (Es decir, no se dice mucho, por lo que es un uso ineficiente de los ciclos de CPU. ) Un ejemplo de este fenómeno es si se compara con la búsqueda lineal binario de búsqueda.

* Si usted tiene un punto de decisión binaria y las probabilidades de los resultados está a y b, el rendimiento de la información (entropía) en bits es -(a*log(a) + b*log(b))/log(2).

Answer 4

La documentación sugiere que GCC (o puede) hacer la optimización del perfil de motor. No es algo que he intentado hacer con gcc, por lo que no puede proporcionar ningún consejo más, podría valer la pena golpear Google.

Answer 5

En mi opinión, la mejor manera de realizar este tipo de optimización es utilizar las opciones -fprofile-generate y -fprofile-use. Esto requiere una base de casos de uso representativas para recopilar información acerca de lo que es probable y lo que no es, pero las pruebas se pueden utilizar para este propósito. Por otro lado, el código no está decorado con las directivas portátiles feas, no.

https: // gcc .gnu.org / onlinedocs / gcc-4.3.6 / gcc / Optimizar-Options.html # Optimizar-opciones para obtener más información acerca de estas dos opciones.