Discussion:
Optimización de los if( )
(demasiado antiguo para responder)
Trauma
2006-01-29 09:43:33 UTC
Permalink
Holas.

¿ Como se optimizan en c las sentencias if ? osea, el compilador supone que la condición será verdadera la mayor parte de las veces, o supone que será falsa.

Es que tengo un bloque if( ) cuya condición será falsa casi siempre ( solo será verdadera la primera vez ) y, puesto que el bloque se ejecutará muchas veces, me gustaría implementarlo lo más rápido posible.

Para más datos, uso el compilador gcc (GCC) 4.0.3 20051201 (prerelease).
Manuel Petit
2006-01-29 11:46:09 UTC
Permalink
#if __GNUC__ >= 3
# define likely(x) __builtin_expect(!!(x), !0)
# define unlikely(x) __builtin_expect( !(x), !0)
#else
# define likely(x) (x)
# define unlikely(x) (x)
#endif

int
some_func()
{
int i;

// ...

for(;;) {
// ...
if (unlikely(i== 7)) {
printf("wow, this was unexpected\n");
}
// ...
}

return 0;
}
Post by Trauma
Holas.
¿ Como se optimizan en c las sentencias if ? osea, el compilador supone que la condición será verdadera la mayor parte de las veces, o supone que será falsa.
Es que tengo un bloque if( ) cuya condición será falsa casi siempre ( solo será verdadera la primera vez ) y, puesto que el bloque se ejecutará muchas veces, me gustaría implementarlo lo más rápido posible.
Para más datos, uso el compilador gcc (GCC) 4.0.3 20051201 (prerelease).
Manuel Petit
2006-01-29 12:23:09 UTC
Permalink
Post by Manuel Petit
#if __GNUC__ >= 3
# define likely(x) __builtin_expect(!!(x), !0)
# define unlikely(x) __builtin_expect( !(x), !0)
Uhm, la segunda macro que puse esta mal, debe ser:

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


manuel,
Post by Manuel Petit
#else
# define likely(x) (x)
# define unlikely(x) (x)
#endif
int
some_func()
{
int i;
// ...
for(;;) {
// ...
if (unlikely(i== 7)) {
printf("wow, this was unexpected\n");
}
// ...
}
return 0;
}
Post by Trauma
Holas.
¿ Como se optimizan en c las sentencias if ? osea, el compilador
supone que la condición será verdadera la mayor parte de las veces, o
supone que será falsa.
Es que tengo un bloque if( ) cuya condición será falsa casi siempre (
solo será verdadera la primera vez ) y, puesto que el bloque se
ejecutará muchas veces, me gustaría implementarlo lo más rápido posible.
Para más datos, uso el compilador gcc (GCC) 4.0.3 20051201 (prerelease).
Iván Sánchez Ortega
2006-01-29 12:43:07 UTC
Permalink
Post by Trauma
¿ Como se optimizan en c las sentencias if ? osea, el compilador supone
que la condición será verdadera la mayor parte de las veces, o supone que
será falsa.
Las optimizaciones de las bifurcaciones en general (ifs, whiles, switches,
etc) las realiza el propio microprocesador. Dependiendo de lo bestia que
sea el pipeline del mismo, aprenderá muy pronto (o muy despacio) cuán a
menudo esa bifurcación se produce o no, y actuará en consecuencia.


Pero esto, más que en C, se aprende en ensamblador. Algo que hay que tener
en cuenta es cómo funciona un pipeline, y las dependencias entre las
distintas fases del pipeline del procesador. Es un tema más bien
complicado, que bien se merece dos meses de universidad. Al final todo se
reduce a poner las instrucciones de ensamblador en un orden tal que la
interdependencia de datos dentro del pipeline sea mínima, y no se obligue
al procesador a insertar fases de "noop" para que una fase del pipeline
espere a que terminen los cálculos de la anterior.


Precisamente este "recolocar el ensamblador" es lo único que puede llegar a
hacer el compilador.


Más información en algún libro tocho que trate sobre ensamblador,
arquitectura de procesadores, y pipelines del procesador.

- --
- ----------------------------------
Iván Sánchez Ortega -i-punto-sanchez--arroba-mirame-punto-net

We have the power to face the future
Cause we are the fighters
Just fighting for our rights.
--Enigma
Iván Sánchez Ortega
2006-01-29 19:46:01 UTC
Permalink
Post by Iván Sánchez Ortega
Precisamente este "recolocar el ensamblador" es lo único que puede llegar
a hacer el compilador.
Se me olvidaba: si mal no recuerdo, en ensamblador existen distintas
instrucciones (dependiendo de la plataforma) para indicar si en una
determinada bifurcación queremos que el algoritmo de predicción de salto se
comporte de una manera o de otra al principio.

Así que si quieres "optimizar" tu código en C, siempre te queda el poner un
trozo de ensamblador a pelo en tu código ;-)


Todo esto del pipelining y la predicción de saltos lo tengo un poco oxidado,
así que no me toméis demasiado en serio.

- --
- ----------------------------------
Iván Sánchez Ortega -i-punto-sanchez--arroba-mirame-punto-net

El dinero no da la felicidad, pero aplaca los nervios.
David Asorey Álvarez
2006-01-30 08:58:23 UTC
Permalink
No tengo mucha idea sobre optimización, pero te remito al libro
clásico "La práctica de la programación", de Brian W. Kernighan y
Rob Pike.

En uno de los capítulos dedicados al asunto dicen que la primera
pregunta que hay que hacerse antes de optimizar es ¿merece la pena?.

Por otra parte, prueba a pasarle al compilador los "flags" (creo que
eran -O) para que optimice. Probablemente haga una optimización mejor
que la que se nos pueda ocurrir a cualquiera de nosotros/as.

Saludos.

David.
Antoine Leca
2006-01-30 18:15:19 UTC
Permalink
Post by Trauma
¿ Como se optimizan en c las sentencias if ? osea, el compilador
supone que la condición será verdadera la mayor parte de las veces, o
supone que será falsa.
El compilador no hace hipotesis al respecte, pero por norma general se
supone que la mayoría de las veces se ejecutará la parte if() y no la parte
else.
En ningun caso esta suposición será una optimización determinante (es decir,
no hay que tener gran expectación al respecte).
Post by Trauma
Es que tengo un bloque if( ) cuya condición será falsa casi siempre (
solo será verdadera la primera vez ) y, puesto que el bloque se
ejecutará muchas veces, me gustaría implementarlo lo más rápido
posible.
Pués ponlo al revés. Y mides si has gañado algo.
Si no has gañado nada que sea mesurable, vuelve a guardarlo como primero
caso: es muchísimo más facil para un humano entender lo que pasa si la fase
de inicialisación esté presentado antes de las fases ulteriores.
Recuerda siempre que el humano puede ser tú dendro de muy pocas años.
Post by Trauma
Para más datos, uso el compilador gcc (GCC) 4.0.3 20051201
(prerelease).
GCC puede tener posibilidades de optimizar este caso, dandole información.
Mira la documentación sobre __builtin_expect. Después, compara si hay, o no,
una diferencia notable...

También puedes usar el profiler. Puede ser más trabajo en este caso
concreto, pero mucho más genérico.


Por favor, hagas las pruebas que te hemos indicado: si, como lo suponemos,
no ves ninguna diferencia, o al menos el tiempo que has pasado medir las
diferencias no vale el tiempo que te has ahorrado con las optimisaciones
encontradas, estarás vaticinado para la vida al tanto de los
"optimisaciones". Y será una cosa muy importante para el resto de tu vida de
programador.

Y para rematar: no olvides que el ordenador del próximo año correrá al menos
30% más que el actual, y será más barato; tampoco olvides que si te cuesta x
horas de trabajo optimizar un programa, hay que comparar este coste con el
diferencial de precio de un ordenador más potente.
Dicho esto, por favor hagas las pruebas, al menos una vez. Vale la pena, de
verdad.


Antoine
Jesús M. Navarro
2006-01-31 19:29:19 UTC
Permalink
Post by Trauma
Holas.
¿ Como se optimizan en c las sentencias if ? osea, el compilador supone
que la condición será verdadera la mayor parte de las veces, o supone que
será falsa.
El compilador, en la generalidad de los casos, no supondrá nada (a menos que
estemos ante una comparación de constantes, por ejemplo, porque entonces ya
no hay nada que verificar).
Post by Trauma
Es que tengo un bloque if( ) cuya condición será falsa casi siempre ( solo
será verdadera la primera vez ) y, puesto que el bloque se ejecutará
muchas veces, me gustaría implementarlo lo más rápido posible.
A poco código que haya que ejecutar tras la condicional (comparado con la
propia evaluación), hacerlo en un orden u otro posiblemente no tenga
consecuencias significativas. Sin embargo, el principio general es obvio:
cuantas menos comparaciones tenga que hacer un programa, menos tardará en
ejecutarlas (de cajón, vamos).

Así, en el caso típico de una construcción if/then/else, el código
comprobará la primera expresión; si es cierta, ya ha acabado; si es falsa,
se irá al else. Por lo tanto, vemos que siempre será más rápido colocar
primero la condición que es más probable que sea cierta, ya que eso evitará
tener que comprobar la siguiente.

En tu caso, si sabes de antemano que la condición de búsqueda será cierta
sólo la primera vez, lo que puedes intentar es evitarte la comprobación
para los siguientes casos. Un ejemplo (muy tonto, pero que creo que
mostrará lo que quiero decir):

Si tenemos un análogo a...
for (i=0; i<10; i++){
(i<1) ? this() : that();
}
...donde se ve que la condición sólo será cierta la primera vez, pero será
evaluada todas ellas, se podría convertir en:
i=0;
while (i++<1) this();
while (i++<10) that();

...en general, "romper" el código en bloques para su ejecución estructurada
y minimizar las evaluaciones*1 (en principio, si puedes saber de antemano
cómo va a evolucionar tu "máquina de estado", deberías ser capaz de avanzar
sin necesidad de evaluar la situación en tiempo de ejecución).

Pero, volviendo al principio, no olvides que uno de los grandes males de la
programación es tratar de optimizar antes de tiempo. Salvo casos muy
específicos, es poco probable que tu evaluación requiera un tiempo
significativo, así que codifica primero de la forma más clara y lógica
posible. Sólo *después*, si tienes problemas de rendimiento, perfila la
aplicación para ver dónde están tus cuellos de botella (y no caigas en la
trampa de "buscar las llaves debajo de la farola": perfilar sólo la parte
que te sea más sencilla). Sólo *después* de haber perfilado la aplicación,
trata de optimizarla donde traiga más a cuenta: resiste la tentación de
optimizar donde te parezca más sencillo (sólo conseguirás un código más
enrevesado, con suerte, y un código incluso más lento, con mala suerte).

*1 En este caso trivial, hemos reducido las evaluaciones a la mitad.
Iván Sánchez Ortega
2006-01-31 23:42:40 UTC
Permalink
Post by Jesús M. Navarro
A poco código que haya que ejecutar tras la condicional (comparado con la
propia evaluación), hacerlo en un orden u otro posiblemente no tenga
cuantas menos comparaciones tenga que hacer un programa, menos tardará en
ejecutarlas (de cajón, vamos).
Nota al margen: en *teoría*, dependiendo de cómo el microprocesador predizca
los saltos, y de la interdependencia del uso de los registros, la
eficiencia puede tranquilamente duplicarse (al evitar que se introduzcan
pausas en el micro).

Repito: En teoría. Hoy en día prácticamente todo el mundo trabaja con
lenguajes de algo nivel y procesadores de un gigahertzio. Si no trabajas
con drivers, con hardware, con algo relacionado con el kernel, o con un
sistema de tiempo real, yo no me preocuparía tanto.

- --
- ----------------------------------
Iván Sánchez Ortega -i-punto-sanchez--arroba-mirame-punto-net

File not found. ¿Me lo invento? (S/N)
Antoine Leca
2006-02-01 09:41:26 UTC
Permalink
Sin embargo, el principio general es obvio: cuantas menos
comparaciones tenga que hacer un programa, menos tardará
en ejecutarlas (de cajón, vamos).
No es tan obvio. Hoy en día, cuesta más hacer solo dos comparaciones
completas (CMP a,b y salto condicional) y equivocarse a la predicción de
salto de ambdos, que hacer cuatro comparaciones y acertar todas a la
predicción. Se debe al hecho que el procesador ejecute el código después del
salto _antes_ de saber cual es el resultado de la comparación; y si se
equivoca, le cuesta mucho empezar de nuevo donde se equivocó.
He ponido dos como base, por que el problema es tan agudo, que con una sola
comparación, algunos procesadores no se meten en predicción y "prueban" los
dos caminos...
Así, en el caso típico de una construcción if/then/else, el código
comprobará la primera expresión;
¿¿¿???
En un if/then/else (en C, if(){...}else{...}), solo veo UNA expresión, la
del if(); las demas son instrucciones.
En tu caso, si sabes de antemano que la condición de búsqueda será
cierta sólo la primera vez, lo que puedes intentar es evitarte la
comprobación para los siguientes casos.
Tienes razón, de esta manera se puede ahorrar mucho más que con los
optimizaciones locales de poner un bloque antes del otro.


Antoine

Loading...