Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: engel lex en 7 Diciembre 2014, 23:35 pm



Título: PoC, más rapido if-else o switch?
Publicado por: engel lex en 7 Diciembre 2014, 23:35 pm
Los que me conocen por aquí, saben que me gusta discutir por tonterias como estas(y que me gusta hacer posts largos)... hace poco estaba hablando sobre un tema con mDrinky y discutíamos si el código compilado de if else es el mismo que switch o si switch era más rápido...

aquí mi prueba de concepto... switch es más rápido... muy ligeramente más rápido

leo un archivo (pi2.txt) y repito 100 veces con 1.000.000 de valores leidos, calculo promedio y repito por el otro metodo
Código
  1. #include <iostream>
  2. #include <fstream>
  3. #include <ctime>
  4. using namespace std;
  5.  
  6. int ifelse_op(int largo, char memoria[]);
  7. int switch_op(int largo, char memoria[]);
  8.  
  9.  
  10. int main(){
  11. int a = 0;//control de ciclos
  12. int ciclos = 100;//cantidad de muestras
  13. /*tiempos*/
  14. float promedio = 0;
  15. float max = 0;
  16. float min = (unsigned int)-1;//maximo u_int
  17. float buff = 0;
  18. /*********/
  19.  
  20. /*pasamos el archivo a ram, cuidado con archios grandes*/
  21. ifstream archivo ("pi2.txt",ios::ate);//abrimos con apuntador al final
  22. int largo =(int) archivo.tellg();//calculamos el largo por el apuntador
  23.  
  24.   archivo.seekg (0, ios::beg);//colocamos apuntador en el inicio
  25.   char memoria[largo];//char-s tan largo como archivo
  26.    archivo.read (memoria, largo);//botamos archivo completo a memoria
  27.    archivo.close();//listo con el archivo
  28.  
  29. /*primer metodo if-else*/
  30. for(a=0;a<ciclos;a++){
  31. buff = ifelse_op(largo,memoria);
  32. promedio += buff;//suma para promedio
  33. max = max>buff?max:buff;//si maximo es menor que buff max=buff
  34. min = min<buff?min:buff;//si minimo es mayor que buff min=buff
  35. }
  36. promedio/=ciclos;//promedia
  37. cout << "promedio if-else: " << promedio/CLOCKS_PER_SEC << "s" << endl;
  38. cout << "min if-else:" << min/CLOCKS_PER_SEC << "s - ";
  39. cout << "max if-else:" << max/CLOCKS_PER_SEC << "s" <<endl;
  40.  
  41. /*se reinician las variables*/
  42. promedio = 0;
  43. max = 0;
  44. min = (unsigned int)-1;
  45. /****************************/
  46. /*segundo metodo switch*/
  47. for(a=0;a<ciclos;a++){
  48. buff = switch_op(largo,memoria);
  49. promedio += buff;
  50. max = max>buff?max:buff;
  51. min = min<buff?min:buff;
  52. }
  53. promedio/=ciclos;
  54. cout << "promedio if-else: " << promedio/CLOCKS_PER_SEC << "s" << endl;
  55. cout << "min if-else:" << min/CLOCKS_PER_SEC << "s - ";
  56. cout << "max if-else:" << max/CLOCKS_PER_SEC << "s" <<endl;
  57. return 0;
  58. }
  59.  
  60. /*****************************************/
  61. int ifelse_op(int largo, char memoria[]){
  62. clock_t inicio_reloj = clock();//tiempo inicial
  63. int control;//variable para control
  64. int i;//control de ciclos
  65. for(i=0;i<largo;i++){
  66. //char valor = memoria[i];//trampa a mi favor mwahaha!!
  67. if(memoria[i]=='1') control = 1;
  68. else if(memoria[i]=='2')control = 2;
  69. else if(memoria[i]=='3')control = 3;
  70. else if(memoria[i]=='4')control = 4;
  71. else if(memoria[i]=='5')control = 5;
  72. else if(memoria[i]=='6')control = 6;
  73. else if(memoria[i]=='7')control = 7;
  74. else if(memoria[i]=='8')control = 8;
  75. else if(memoria[i]=='9')control = 9;
  76. else if(memoria[i]=='0')control = 0;
  77. else control = 0;
  78. }
  79. return clock() - inicio_reloj;//retorna tiempo
  80. }
  81.  
  82. int switch_op(int largo, char memoria[]){
  83. clock_t inicio_reloj = clock();//tiempo inicial
  84. int control;//variable para control
  85. int i;//control de ciclos
  86. for(i=0;i<largo;i++){
  87. //char valor = memoria[i];
  88. switch (memoria[i]){
  89. case '1':control =  1;
  90. case '2':control =  2;
  91. case '3':control =  3;
  92. case '4':control =  4;
  93. case '5':control =  5;
  94. case '6':control =  6;
  95. case '7':control =  7;
  96. case '8':control =  8;
  97. case '9':control =  9;
  98. case '0':control =  0;
  99. default: control =  0;
  100. }
  101. }
  102. return clock() - inicio_reloj;//retorna tiempo
  103. }
  104.  
  105.  

con mi perolita los resultados son
Código:
promedio if-else: 0.0238996s
min if-else:0.023581s - max if-else:0.024229s
promedio if-else: 0.0180653s
min if-else:0.018014s - max if-else:0.018394s

con ligeras variaciones menores a +-0.0007 dando como resultado un switch 8% más rápido que el if :P

si alguien cree que mi metodología o código esta mal o me equivoqué avisen

el archivo pi2.txt es un archivo que tengo por ahí tiempo y lo uso para probar cosas, es una generacion de pi a 1.000.000 de decimales, sin cabeceras, ni texto y medio mocho... son casi 1.1mb, si lo quieren, aqui está

https://mega.co.nz/#!6xAmGIaA!FtCMe4bM5NVm-gcO2zW-myUWlBdLI3TqlweAhKaQ-0I (https://mega.co.nz/#!6xAmGIaA!FtCMe4bM5NVm-gcO2zW-myUWlBdLI3TqlweAhKaQ-0I)


PD: codigo corregido...


Título: Re: PoC, más rapido if-else o switch?
Publicado por: ivancea96 en 8 Diciembre 2014, 00:13 am
A mi me da lo mismo en la mayoría de los casos:

Citar
promedio if-else: 2270ms
promedio switch : 2271ms


EDITO: Tras hacer unos cambios, esta es la resolución:

Citar
promedio if-else: 15681ms
promedio switch : 6944ms


Título: Re: PoC, más rapido if-else o switch?
Publicado por: x64core en 8 Diciembre 2014, 00:50 am
@engel lex, @mDrinky:
Intentar calcular la velocidad de este tipo de códigos es ridiculo, la decisión final es tomada por el compilador. Aquí no mencionas nisiquiera el compilador y parametros ni nada por el estilo, bien puedo activar todas las optimizaciónes. Cualquier programador con un minimo de conocimiento en C/C++ lo sabe y ya que tienen interesantes discuciónes, mDrinky puede empezar a compartir el compilador que utiliza para generar super ensamblador universal con auto-generación.

-

Mejor vayan a leer un buen libro de C/C++.


Título: Re: PoC, más rapido if-else o switch?
Publicado por: engel lex en 8 Diciembre 2014, 01:02 am
@engel lex, @mDrinky:
Intentar calcular la velocidad de este tipo de códigos es ridiculo, la decisión final es tomada por el compilador. Aquí no mencionas nisiquiera el compilador y parametros ni nada por el estilo, bien puedo activar todas las optimizaciónes. Cualquier programador con un minimo de conocimiento en C/C++ lo sabe y ya que tienen interesantes discuciónes, mDrinky puede empezar a compartir el compilador que utiliza para generar super ensamblador universal con auto-generación.

-

Mejor vayan a leer un buen libro de C/C++.


es cierto cada compilador tiene sus metodos... pero solo por probar con g++ en linux me da así :P sin más parametros, x64Core tu tienes buenos conocimientos sobre lo que se refiere a temas de más bajo nivel. por que no lo pasas tu por varios compiladores con diferentes optimizaciones y sin optimizaciones y vemos las diferencias, al final dentro de un mismo compilador con los mismos parametros, las diferencias si se marcan y al final los ejemplos practicos y pruebas de concepto son más visuales y practicas para ciertas cosas, no?


Título: Re: PoC, más rapido if-else o switch?
Publicado por: x64core en 8 Diciembre 2014, 02:27 am
es cierto cada compilador tiene sus metodos... pero solo por probar con g++ en linux me da así :P sin más parametros, x64Core tu tienes buenos conocimientos sobre lo que se refiere a temas de más bajo nivel. por que no lo pasas tu por varios compiladores con diferentes optimizaciones y sin optimizaciones y vemos las diferencias, al final dentro de un mismo compilador con los mismos parametros, las diferencias si se marcan y al final los ejemplos practicos y pruebas de concepto son más visuales y practicas para ciertas cosas, no?
¿Y sólo por el hecho que alguna persona conozca acerca de temas de bajo nivel debe de hacer estas pruebas? Pues creo que por esa misma razon de saber como esto funciona se evita perder el tiempo de esta manera, pero bueno supongo que lo decias en tono sarcastico e intentando pasarte de listo.
Para que entiendas, habran situaciónes en donde los compiladores generán código más veloz usando if's o switch's, todo dependerá de la logica del programa asi que no hay manera de concluir diciendo cosas como:"usando if's es más veloz", "en general, switch generará código más veloz" o algo por el estilo.


Título: Re: PoC, más rapido if-else o switch?
Publicado por: engel lex en 8 Diciembre 2014, 02:31 am
¿Y sólo por el hecho que alguna persona conozca acerca de temas de bajo nivel debe de hacer estas pruebas? Pues creo que por esa misma razon de saber como esto funciona se evita perder el tiempo de esta manera, pero bueno supongo que lo decias en tono sarcastico e intentando pasarte de listo.
Para que entiendas, habran situaciónes en donde los compiladores generán código más veloz usando if's o switch's, todo dependerá de la logica del programa asi que no hay manera de concluir diciendo cosas como:"usando if's es más veloz", "en general, switch generará código más veloz" o algo por el estilo.

entonces según el codigo, el compilador puede generar un codigo maquina sobre los switch o if diferente, haciendolos más eficientes según el caso?

en caso general cual es la forma de saber cual sería más eficiente en tu codigo?



Título: Re: PoC, más rapido if-else o switch?
Publicado por: x64core en 8 Diciembre 2014, 02:39 am
entonces según el codigo, el compilador puede generar un codigo maquina sobre los switch o if diferente, haciendolos más eficientes según el caso?

en caso general cual es la forma de saber cual sería más eficiente en tu codigo?


No me referia a eso, dije que va a depender de la logica de tu programa al final el código se traduce en u lenguaje que es entendido por el compilador ya no depende de las sentencias if o switch.


Título: Re: PoC, más rapido if-else o switch?
Publicado por: engel lex en 8 Diciembre 2014, 02:46 am
No me referia a eso, dije que va a depender de la logica de tu programa al final el código se traduce en u lenguaje que es entendido por el compilador ya no depende de las sentencias if o switch.

XD pero mi duda es: la eficiencia no va a cambiar según usemos una u otra o otra estructura entonces? (supongamos el caso de x codigo que se enfrenta constantemente a esta estructura, caso para el que que son perfectamente intercambiables y requiriendo eficiencia ante todo)


Título: Re: PoC, más rapido if-else o switch?
Publicado por: x64core en 8 Diciembre 2014, 03:30 am
XD pero mi duda es: la eficiencia no va a cambiar según usemos una u otra o otra estructura entonces? (supongamos el caso de x codigo que se enfrenta constantemente a esta estructura, caso para el que que son perfectamente intercambiables y requiriendo eficiencia ante todo)
Es posible pero como dije todo depende de la logica de tu programa, los compiladores no tienen inteligencia artificial como para saber lo que el programador está intentando hacer, lo que si hacen es, intentar darle logica lo que se quiere lograr. Solo pensar que los compiladores hacen comparaciones como decir: "Si es una sentencia if entonces generar una instruccion test reg,reg o si encuentro un switch generar cmp reg, imm" es ridiculo.

Por ejemplo, unas situaciónes que he visto en las ultimas versiones del compilador de VC++ es que al usar una sentencia  switch con varios case's, este crea una tabla de direcciones a los destinos, a la hora de comparar se toma la dirección base de esa tabla y se le suma un offset para obtener la dirección de destino, esto es mejor que ir comparando case por case, solo imagina un switch con 100+ case's. Claro que esto va a depender, si hay pocos case's entonces podria ser mejor comparar uno por uno.





Título: Re: PoC, más rapido if-else o switch?
Publicado por: engel lex en 8 Diciembre 2014, 03:36 am
comprendo!  ;D

entonces ya se que no tiene demasiado sentido comprar estructuras, sino solo algoritmos en si mismos


Título: Re: PoC, más rapido if-else o switch?
Publicado por: _Enko en 9 Diciembre 2014, 20:24 pm
Mi humilde opinion es que entre switch y elseif no hay mucha diferencia.
La diferencia real la hace la estructura que se utiliza.

Supongamos este ejemplo
Código
  1. memoria[i] = 556;
  2.                if(memoria[i]=='1') control = 1;
  3. else if(memoria[i]=='2')control = 2;
  4. else if(memoria[i]=='3')control = 3;
  5. else if(memoria[i]=='4')control = 4;
  6. else if(memoria[i]=='5')control = 5;
  7. else if(memoria[i]=='6')control = 6;
  8. else if(memoria[i]=='7')control = 7;
  9. else if(memoria[i]=='8')control = 8;
  10. else if(memoria[i]=='9')control = 9;
  11. else if(memoria[i]=='0')control = 0;
  12. else control = 0;
  13.  
El codigo este va hacer 10 comparaciones inutiles para llegar a ejcutar el "else" que es lo que vale.

Entonces a mi criterio la mejor optimizacion que se puede hacer , es poner primero las condiciones que tengan más probabilidad de suceder. De manera que se ejecutén menos comparaciones y se pierda menos el tiempo.

La ventaja de switch-case es que tenemos la posibilidad de utilizar o no el Break  cosa que se pueden agrupar varios casos en un mismo grupo.

Saludos.


Título: Re: PoC, más rapido if-else o switch?
Publicado por: engel lex en 9 Diciembre 2014, 20:35 pm
es un numero bastante aleatorio así que cualquier cosa es probable XD

aunque lo que dice x64Core es cierto, el compilador verá como resuelve su lio allí para que sea rapido (posiblemente hasta vuelve eso una tabla o algo así)


Título: Re: PoC, más rapido if-else o switch?
Publicado por: x64core en 10 Diciembre 2014, 02:37 am
Mi humilde opinion es que entre switch y elseif no hay mucha diferencia.
La diferencia real la hace la estructura que se utiliza.

Supongamos este ejemplo
Código
  1. memoria[i] = 556;
  2.                if(memoria[i]=='1') control = 1;
  3. else if(memoria[i]=='2')control = 2;
  4. else if(memoria[i]=='3')control = 3;
  5. else if(memoria[i]=='4')control = 4;
  6. else if(memoria[i]=='5')control = 5;
  7. else if(memoria[i]=='6')control = 6;
  8. else if(memoria[i]=='7')control = 7;
  9. else if(memoria[i]=='8')control = 8;
  10. else if(memoria[i]=='9')control = 9;
  11. else if(memoria[i]=='0')control = 0;
  12. else control = 0;
  13.  
El codigo este va hacer 10 comparaciones inutiles para llegar a ejcutar el "else" que es lo que vale.

Entonces a mi criterio la mejor optimizacion que se puede hacer , es poner primero las condiciones que tengan más probabilidad de suceder. De manera que se ejecutén menos comparaciones y se pierda menos el tiempo.

La ventaja de switch-case es que tenemos la posibilidad de utilizar o no el Break  cosa que se pueden agrupar varios casos en un mismo grupo.

Saludos.
Usando || es posible hacer lo mismo que un switch-case. if(exp || exp || exp).
Además usando switch-case la expresion debe ser constante.

Mod: editado para eliminar citas de mensajes borrados


Título: Re: PoC, más rapido if-else o switch?
Publicado por: Eternal Idol en 10 Diciembre 2014, 09:09 am
zShackra y x64Core no secuestren hilos para discutir entre ustedes y si TODAVIA tienen cosas que decirse usen los mensajes privados.


Título: Re: PoC, más rapido if-else o switch?
Publicado por: _Enko en 10 Diciembre 2014, 15:25 pm
EI no!!!!
Estaban a darnos por conocer que la novia de uno está embarazada pero no saben quien es el padre.
cha-chan-cha-chaaaaan!!!!

Citar
Usando || es posible hacer lo mismo que un switch-case. if(exp || exp || exp).
Además usando switch-case la expresion debe ser constante.

Cierto, pero lo que quería resaltar, es que la mejor optimización es tratar de hacer en lo posible que las condiciones posibles sean las primeras en aparecer en el bloque de if-case. 
Es decir no hacer 10 "elseif" para que en el 90% de los casos se ejecute el "else".

Saludos.
 


Título: Re: PoC, más rapido if-else o switch?
Publicado por: zShackra en 10 Diciembre 2014, 16:30 pm
Es decir no hacer 10 "elseif" para que en el 90% de los casos se ejecute el "else".
Saludos.

El asunto es que para pocos if-else, es mejor usar los mismos, para muchas más comprobaciones, un switch-case sería más rápido, porque según entiendo se evitan hacer cmp, y el compilador usualmente crea una tabla de saltos, así va directo a cada jmp, el problema es que se usa un poco más de memoria... pero sería un código más organizado y posiblemente más rápido.