cómo sugieren 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 de la condición requiere ~ 60 ciclos para verificarse, y el compilador no puede calcularlo en tiempo de compilación.

(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 quiere encontrar una manera de evitar evaluar la condición, que __builtin_expect() no hará. ¿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

La documentación sugiere que gcc hace (o puede) optimizar el perfil. No es algo que haya intentado hacer con gcc, por lo tanto, no puedo brindar ningún otro consejo, podría valer la pena darle a Google.

Answer 3

Si el resultado puede variar durante una sola ejecución, es posible que pueda utilizar la evaluación diferida de los operadores booleanos para dividir su condición en una parte barata y una parte costosa, y ejecutar primero la parte barata.

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, puede optimizarlo almacenando el resultado del cálculo en una variable estática o global.

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, 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 4

En primer lugar, ¿cuántos ciclos se gastan en la cláusula else, o en algún otro lugar del programa? Si hace un perfil o toma stackshots, ¿está gastando al menos 10% de su tiempo en esa prueba? Si no, probablemente haya problemas más grandes que deberías mirar primero.

En segundo lugar, si gasta> 10% de tiempo en esa prueba, debería ver si el algoritmo se puede ajustar para tener puntos de decisión más cercanos a la probabilidad 50-50. Un punto de decisión 50-50 produce 1 bit de información cuando se ejecuta, mientras que un punto de decisión 99-1 solo rinde alrededor de .07 bits. * (Es decir, no le dice mucho, por lo tanto, es un uso ineficiente de los ciclos de la CPU.) Un ejemplo de este fenómeno es si compara la búsqueda lineal con la búsqueda binaria.

* 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 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 representativos para recopilar información sobre lo que es probable y lo que no, pero las pruebas se pueden usar para este propósito. Por otro lado, el código no está decorado con directivas feas, no portátiles.

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