Club Builder

[Cerúleo]

Hola.

El otro día cayó en mis manos un artículo sobre la aceleración en la ejecución de los programas. En concreto hablaban de algunas técnicas para que el código ejecutable quedase optimizado y corriera más deprisa.
A mi me resulta especialmente interesante esta posibilidad dado que mi programa tiene una parte fundamental de puro cálculo matricial. Lo que pasa es que hablo, por decir algo (y sin exagerar) de matrices de
15 000 x 6 000 o de ese orden. Al final hay que resolver un sistema de ecuaciones para esa matriz y para ello empleo los típicos ciclos for.
Resulta que una de las técnicas de las que hablaba el artículo era "el desenrollo de bucles" y "sustituir el for por el while". Aducían como argumento principal que éste, el while, es más eficiente que el for al ser más sencilla de evaluar la sentencia de control de salida del bucle.
¿Podéis decirme que hay de cierto en todo esto?
Estoy probando algunas modificaciones en el código para comprobar "in situ" estas afirmaciones y ver en cuánto tiempo se reduce (o amplía) el cálculo, pero me quedaría más tranquilo si alguien me puede decir algo más.
Por cierto, en las opciones de compilación y linkado del programa tengo las casillas de optimizar para la velocidad clickadas, porque me interesa más esto que reducir el tamaño del ejecutable o del código.

Un saludo. Cuídense.
_________________
Nunca digas "Es imposible" sin intentarlo antes.

[ikis]

La clave se encuentra en las instrucciones Assembler q genera tu código, para eso puedes usar las opciones de debug y ver tu código C++ transformado en Assembler. De este modo podrías contar las microinstrucciones, aunque, me parecería más práctico usar un par de variables de tiempo y medir cuanto tardas en resolver los bucles usando distintas opciones.

Una cosa q uso a menudo, o, mejor dicho, evito usar en los ciclos largos es el >= o <= ya q genera más microinstrucciones q el > o < y de ese modo gano en velocidad.

[XyVy]

Sinceramente con las máquinas de hoy en día y los compiladores tan potentes que tenemos hoy en día, realizan el trabajo mucho mejor que nosotros.

Yo en la asignatura de Estructura de computadores, vimos el desenrollo de bucles, pero esto solo tiene cabida para optimizaciones dependientes de la máquina en que se ejecute, e intenando maximizar el uso del pipeline de instrucciones y las unidades de calculo disponibles, minimizando los riesgos de datos y dentenciones.

Creo que se hace bastante dificil entrar en todo esto y más cuando sabemos que tenemos varias arquitecturas bajo x86. En el cambio del for el while, primero creo que yo que deberías estudiar el orden de tu algoritmo teoricamente, pues imaginate que tienes un algoritmo que tiene un orden de n cuadrado, pues con una entrada de n muy grande el tiempo que puede tardar tu algoritmico es bestial, sin embargo por ejemplo uno que hiciera lo mismo pero con orden linal o n log n, tiene un tiempo de respuesta mejor.

Lo que quiero decir, es que yo primero estudiaria los tiempos de ejecución teoricos para el algoritmos, es decir, los ordenes o notaciones asintoticas, el omega (caso más favorable), la O mayuscula (o caso menos favorable o peor caso) y el caso promedio, esto nos puede decir más o menos por donde pueden ir los tiros en cuanto al tiempo de ejecución, pues realmente si tienes un algoritmo que es del O(n cuadrado) de poco te va a servir incrementar antes o despues, segun uses for o while, pues no te va a cambiar el orden de ejecución salvo en constantes de tipo despreciable.

El tema del perfilado es interesante, yo lo utilizaba en linux gprof, para saber al ejecutar mi programa (de tipo pseudomatematico o de calculo) para ver en que funciones se concentraba el mayor uso de tiempo de esa ejecución. Luego se puede estudiar como intentar optimizarla si es que se puede y en el caso de que se pudiera intentar optimizarla, pero como decía mi profe Lorenzo, hay que recordar la Ley de Amdal, que dice algo así como una vez optimizada una cosa ahora lo que nos produce el cuello de botella es otra, jajajaja toma ya!

El caso más obvio es el de la ordenación para el que haya estudiado algo de algorítmica o un poco de ordenación, sabrá que por ejemplo el burbuja tiene un caso peor de n cuadrado frente por ejemplo un mergesort que tiene un caso peor de n log n. Puede parecer que la diferencia no es mucha, incluso con una entrada muy pequeña el algoritmo de ordenación burbuja es mucho más rapido, pero si trazas una grafica con las dos funciones, veras como conforme la n va creciendo las diferencias se hacen abismales, tanto que para n grandes, tenemos que burbuja se puede tirar perfectamente media hora o mucho más (depende de la n) y con la misma n, el mergesort se puede tirar como unos segundos o algun minuto.

Por ejemplo, es decir, por ejemplo yo uso mis propios StringGrid y allí visualiza datos de la BD como si fuera un DBGrid, y entonces hago un recorrido por mi Query y voy insertando los registros de mi agrado en el DBGrid, esto tiene un orden lineal es obvio depende del número de registros a mostrar, pero veo que esto me lleva mucho tiempo, un fallo que se puede cometer (o no según se mire) es refrescar el grid tras insertar cada registro, esto provoca que accedamos a pantalla lo que me produce un retardo mayor en el redibujado más en el procesamiento total, en cambio si no redibujo, es decir meto todos los n registro y luego redibujo, observo que ese proceso se ha ejecutado en un tiempo menor, el retardo era producido por el llenado y redibujado del grid, esto ultimo se ha evitado, luego he obtenido una mejora, aun haciendo ver que el orden de mi proceso no me ha cambiado, lo que pasa es que no he tenido en cuenta que el redibujado también crecia con la n, luego todas estas cosas pueden influir en nuestra ejecución algoritmica o bien en nuestros procesos, pero hay que ver que se hace, como se hace y si realmente se puede optimizar, pues no todo es optimizable, y por supuesto no hay que olvidar si merece la pena la optimización, pues puede ser que no nos afecte apenas en nada y haya requerido más complejidad a la hora de programar.

En fin ciao y suerte.
Se nota que estoy con la algoritmica ? jajajaj.
_________________
OJO!! Ya tenemos subforo de Bases de Datos!!
Gracias a los admins.

[Roid]

Si quieres acelerar tus algoritmos de calculo en este caso en el calculo de matrices tienes 2 opciones:

Uno q es pej si haces multiplicaciones de matrices es usando la tecnica de
divides y venceras, es algo compleja de aplicar pero es super eficiente.

Y la otra opcion para calculo es usando alguna libreria matematica q ya lleva implementado estos algoritmos usando este tipo de tecnicas.

Te aconsejo q uses las Yacc van de vicio.

En general hay muchas tecnicas como backtracking, branch an bound (no se si esta bien escrito ),divide y venceras,programacion dinamica,greedy, y todos los algoritmos bioinformaticos.

Si la memoria no me falla, creo recordar q habia una pagina especializada en algoritmos algebraicos y algoritmos de calculo numerico, el problema es q no me acuerdo de la pagina. Pero si le pones empeño seguro q la encuentras

Referente a si es verdad q reduce el tiempo es verdad, por ej, hicimos un algoritmos para encontrar patrones q con un algoritmo especifico tardaba mas de 24 horas mientras que usando la tecnica de programacion dinamica el programa solo tardaba unos 20 segundos o menos, creo q rondaban los 10, pero ya ni me acuerdo pq fue hace tiempo.


Si tienes algun problema o duda postea por aqui.

Un saludo.

[XyVy]

El calculo matricial, tiene sus peros en divide y venceras, todos sabemos que el calculo matricial segun el algoritmo normal tiene un orden de ejecución de n cubo, puedes usar el método de Strassen el cual te puede reducir de n al cubo a n elevado a 2,81, el menor obtenido por ahora segun tengo yo a mano como referencia es n elevado a 2.375. El problema es que cada vez que reduces un poco el factor al que está elevado la n introduces más calculos, y claro hay que ver realmente que tamaño de matrices estás calculando, pues puede compensarte o no, esta reducción. Los ordenes que he hablado antes son para referencias de multiplicación de matrices de nxn elementos.

Como bien dice roid, el uso de librerias, acelera calculos pues ellos ya han intentado optimizar al máximo las operaciones, estoy hablando de librerias matemáticas por supuesto.

Aun así eso no quita que si tú solo vas a usar dos o tres cosas te implementes tus propias funciones y que intentes estudiar los tiempos de ejecución, ordenes y demás notaciones.

El método de Strassen es extremadamente sencillo de comprender y te puede mejorar un poco los calculos. Pideme más información si te interesa y pego aquí las ideas clave.

Ciao.
_________________
OJO!! Ya tenemos subforo de Bases de Datos!!
Gracias a los admins.

[Roid]

Muy bien, veo q estas hecho un buen estudiante pero referente a la multiplicacion de matrices el numero elevado cada año es reducido ya q hay un campeonato mundial para reducir este numero,asi q no te fies de ese numero

Un saludo.

[XyVy]

Este número es el que yo tengo desde hace unos años, no sé si habrá bajado o no, no tenía ni idea lo del campeonato, aunque no es muy iluso pensar que siempre se está intentado resolver problemas y demostraciones aun no demostradas o mejoras en los algoritmos.

Gracias por el apunte.
_________________
OJO!! Ya tenemos subforo de Bases de Datos!!
Gracias a los admins.

[Cerúleo]

Hola a todos. Gracias por vuestras respuestas. Me han parecido de lo más interesante. Yo no sé hasta qué punto puedo intentar optimizar el código, pero me interesaría que me indicárais alguna página o publicación o me ampliárais la ayuda que habéis tenido a bien brindarme.

Os espero. Un saludo.
_________________
Nunca digas "Es imposible" sin intentarlo antes.

[XyVy]

Pues por ejemplo tienes varias referencias más o menos obligadas dependiendo de lo que intentes hacer o estudiar, para estudiar el analisis de algoritmos tienes lo siguiente:

- The design and analisys of computer algorithms. Adison-Wesley
Autores: Aho, Hoptcroft y Ullman. 1974 (fijate del 1974 y apenas se pasa
de moda !!!!).

- Estructuras de datos y algoritmos. Adison-Wesley.
Autores: Aho, Hopcroft y Ullman. 1988

- Algoritmica. Concepción y análisis.
Autores: Brassad & Bratley 1990.

- Fundamentals of Algorithmics. Prentice Hall, 1996. Este también está
en castellano. (Brassard & Bratley).

- Luego hay unos volumenes. Llamados "el Arte de programar ordenadores". El autor es Mr. D.E. Knuth (otro fiera).

- Algoritmos y estructuras de Datos. Prentice-Hall 1987.
Niklaus Wirth. (Este otro fenemeno).

Todos estos autores son referencias obligadas de carrera, para el estudio de algoritmos y estructuras de datos.

Luego de optimización, yo los que he visto no eran como tales, sino que eran de arquitectura de computadores donde siempre se entraba en temas de optimización, este libro es un clasico (la versión española dicen que es algo peor).

- Computer Architecture: A Quantitative Approach. Morgan-Kaufmann Publishers. Autores: Hennesy & Patterson. 1990.

Allí se habla sobre el desenrollo de bucles y demás, con referencias logicamente a las caches, unidades de calculo, etc.

De hecho el problema que comentabas sobre multiplicación de matrices es un problema muy tipico para estudiar el rendimiento de las caches, en cuanto a localidad temporal y espacial y como el orden de acceder a la matriz por filas o por columnas puede ayudarnos a obtener un mejor rendimiento del uso de cache y por lo tanto de nuestro programa, en fin son idas de olla mias!!! jajjaaj.

Ciao y suerte. Es un tema la mar de apasionante.
_________________
OJO!! Ya tenemos subforo de Bases de Datos!!
Gracias a los admins.

[Cerúleo]

Hola.

Me he puesto a retocar algo el código del núcleo de cálculo y tengo un problema que no tiene nada que ver y que no alcanzo a comprender.

Antes de la función de cálculo obtengo la hora del sistema. Nada más terminar el cálculo la vuelvo a obtener. La diferencia de horas sería, lógicamente, el tiempo de cálculo. Pues bien. Ejecutando el mismo archivo de datos, los resultados son diferentes: 4.137 seg, 4.256 seg, 4.058 seg,... ¿Por qué puede ser?

Para obtener el tiempo del sistema he empleado las funciones time() y clock() y con ambas tengo el mismo problema.

Necesito una ayuda porque sin esto no puedo saber en qué medida influyen las optimizaciones de código.

Un saludo.
_________________
Nunca digas "Es imposible" sin intentarlo antes.

[Roid]

Este es un ejemplo de medir el tiempo de ejecucion, esta programado bajo linux,espero q te sirva.

TAntes=clock();
PuntoCercano.PuntosMasCercanos();
TDespues=clock();

Tiempo=((double)(TDespues-TAntes)/CLOCKS_PER_SEC);

Referente a los tiempos pq varian, eso es muy normal, la mejor forma para ver como funciona tu programa es , en tu caso, es calculando matrices de 1x1 hasta 4 mil por lo q sea y con los tiempos lo representas en una grafica y asi lo ves mejor.

Sobre el pq varia los tiempos puede ser por mil cosas, puede q sea por las caches del micro o por mas motivos.

Buscate algun manual de medida de eficiencia por internet y encontraras la forma de medirlo sin problema.

Un saludo.

[Roid]

http://www.ciberia.ya.com/darkdiabliyo/programacion/codigos_fuente/C_ecuaciones_lineales.zip

Son ejemplos de resolucion de ecuaciones lineales por varios metodos jacobi & cia.

Espero q te ayude.

[XyVy]

Ninguna función de tiempo te va a decir el tiempo exacto, pues ni puede ser exacto ni a veces aproximado, pues en una máquina con sistema operativo multitarea están corriendo concurrentemente varios procesos, demonios, etc, etc, luego el tiempo es aproximado, de ahí esas ligeras diferencias de tiempo, podrías ejecutarlo 1000 veces y entonces promediar, y así tener una pequeña estimación, pero aun así depende de ciertos factores.

Ciao y suerte.
_________________
OJO!! Ya tenemos subforo de Bases de Datos!!
Gracias a los admins.