lunes, marzo 27, 2006

 

Optimizando el código

En este articulo intentare hacer que los programadores vean su código compilado en la cabeza según lo están escribiendo, al principio les puede parecer complicado pero después de algún tiempo haciéndolo no lo es en absoluto.
Para ello vamos a deducir como un compilador trata las secuencias if y como debemos de hacerlo correctamente para ganar velocidad.
Tenemos este código:
struct Elemento
{
void *dato;
};

Elemento *Mete( void *dato )
{
if( dato == NULL )
{
return NULL;
}
Elemento *nuevo = new Elemento;
if( nuevo == NULL )
{
return NULL;
}
nuevo->dato = dato;
return nuevo;
}
 
Esta función mete un dato dentro de una estructura Elemento, es una función sin sentido pero que nos vale para lo que queremos hacer.
Como vemos este más o menos es el código que harían la mayoría de los programadores por comodidad, exceptuando que muchos quitarían las llaves, yo las dejo ya que vale para explicar mejor a donde quiero llegar, si examinamos el código veremos que si el dato pasado a la función es null queremos que de un error y salga, después creamos el elemento y si este null saldrá dando un error, si todo sale bien dato se almacena dentro de la estructura y esta es devuelta para su manejo, ahora les muestro el código que seria correcto para ganar velocidad:
struct Elemento
{
void *dato;
};

Elemento *Mete( void *dato )
{
if( dato != NULL )
{
Elemento *nuevo = new Elemento;
If( nuevo != NULL )
{
nuevo->dato = dato;
return nuevo;
}
}
return NULL;
}
 
Como se ve la lógica del código es contraria totalmente a la anterior favoreciendo a los casos en que todo sea correcto, es decir, diferente a NULL, ¿y cual es el motivo de esto? el motivo es que todos los compiladores por lógica siempre que se entra dentro del if no se produce un salto, en cambio si el if no se cumple si que se produce, el motivo es que cuando el contenido de un if termina se tiene que seguir haciendo lo que va después, veamos lo que digo en un pseudo código:
comparar dato con NULL
es diferente?
{
… código dentro de las llaves
}
… código que va después
 
Como se ve si es diferente se hace el contenido de las llaves, pero sea o no diferente el código que va después siempre se hace, entonces llegamos a la conclusión de que el compilador producirá un salto para el caso contrario que pongamos nosotros, ya que si no el compilador realizara un salto al contenido de las llaves y después al final de estas otro salto a lo que va después de ellas, en conclusión, el compilador optimiza poniendo un salto a la comprobación contraria a la que ponemos nosotros, así solo produce saltos en el caso que no se cumpla lo que indicamos y siempre que se cumpla el código va secuencialmente, además de que al final de las llaves no se producirá un salto ya que al producirse solo cuando no se cumple el código esta justo debajo de las llaves.
Ahora examinando el primer código que puse veremos que estamos produciendo un salto siempre y en el segundo código se ve que solo se producirá el salto cuando las condiciones no se cumplan, esto también nos lleva a deducir en que siempre debemos de favorecer al código que se cumpla mas del 50% de las veces, es decir, en el segundo código vemos que lo normal es pasar un dato que no sea nulo y que la mayoría de las veces exista suficiente memoria como para crear una estructura Elemento, de esta manera no existirán saltos en el código, exceptuando claro esta el retorno de nuevo o null.
Mas beneficios de este sistema de programacion son codigos como este:
bool CrearMalla( int numVertices, int numIndices, char *fileShader )
{
VertexBuffer *vertices = new VertexBuffer( numVertices );
if( vertices != NULL )
{
IndexBuffer *indices = new IndexBuffer( numIndices );
if( indices != NULL )
{
Shader *shader = new Shader( fileShader );
if( shader != NULL )
{
return true;
}
delete indices;
}
delete vertices;
}
return false;
}
 
Viendo la logica nos damos cuenta que siempre que se haga todo correcto no se produciran saltos, si ocurre algun error se produce un solo salto y destruimos los objetos en el orden inverso de su creacion.

lunes, febrero 27, 2006

 

Pensando en n-dimensiones

La mayoría de las veces la gente cuando se pone a programar juegos 2d o 3d se centran exactamente en el numero de dimensiones que tendrá ese juego, esto en mi humilde opinión es una forma de pensar totalmente incorrecta, el problema de pensar en 2d o 3d es que creamos funciones para este tipo de dimensiones y no pensamos en la verdadera optimización de pensar en n-dimensiones.
¿Que es pensar en n-dimensiones? Pensar en n-dimensiones es tener claro el concepto de que es una dimensión, para explicar lo que es una dimensión lo haré de la forma mas sencilla que conozco, una dimensión no es mas que un espacio comprendido entre dos puntos que se llaman -infinito y +infinito, en un ordenador lamentablemente infinito no existe (salvo en bucles), la mayoría de las veces las dimensiones son tratadas de -float +float, es decir, de 1.17549e-38 hasta 3.40282e+38, teniendo claro esto, podemos decir que todas las dimensiones se comportan de la misma manera ya que solo definen la posición en un espacio (algunos lo entenderéis mejor si lo llamara vector).
Un ejemplo practico de como pensar en n-dimensiones es la clásica función para comprobar si un cubo definido por dos puntos (mínimo y máximo) esta dentro de otro o por lo menos esta parcialmente dentro de otro, la mayoría de las personas harán la clásica rutina de mirar si uno de los dos puntos del cubo A esta dentro de los puntos del cubo B, esto en mi opinión es un error muy gordo ya que solo se ha pensado en 3d y no en n-dimensiones, partimos de que tenemos las siguientes estructuras:
struct Vector
{
float x, y, z;
}
struct Caja
{
Vector min, max;
}

El código pensado para 3d seria algo así:
bool Colision3D( Caja caja1, Caja caja2 )
{
if( PuntoDentro3D(caja1, caja2.min) || PuntoDentro(caja1, caja2.max) )
{
return true;
}
return false;
}
bool PuntoDentro3D( Caja caja1, Vector punto )
{
if( punto.x > caja1.min.x && punto.x < caja1.max.x &&
punto.y > caja1.min.y && punto.y < caja1.max.y &&
punto.z > caja1.min.z && punto.z < caja1.max.z )
{
return true;
}
return false;
}

Vemos que comprobamos que uno de los dos puntos de la caja B se encuentre dentro de la caja A, esto genera 12 comprobaciones, es decir 6 por cada punto, ¿que pasaría si hiciéramos esta función pensando en n-dimensiones? Antes de dar la solución es mejor explicar paso a paso como llegar a ella.
Lo primero es quitar las dimensiones Y y Z del tablero de juego, es decir, nos quedamos solo con la dimensión X que se comporta de la misma manera que Y y Z, ahora pensamos lo siguiente, ¿que debemos de hacer para comprobar si un valor se comprende entre otros dos, por ejemplo entre el 10 y el 20?
if( valor > 10 && valor < 20 ) return true;

Si el valor es mayor a 10 y el valor es menor a 20 es que valor esta entre 10 y 20 lógicamente, ahora un poco mas complicado, ¿que hacemos para saber si min y max se comprende entre 10 y 20 o esta parcialmente dentro?
if( max > 10 && min < 20 ) return true;

¿Ein? ¿y como es que con las mismas comprobaciones logramos esto? Pues muy sencillo, debemos de mirar todos los casos posibles, si máximo es menor a 10, significa que min es menor a 10 ya que max es mayor siempre que min, si max es mayor a 10 o 20 significa que y min y max pueden estar dentro de 10 o 20, si min es mayor a 20 significa que esta fuera del rango de 10 y 20 ya que max siempre es mayor a min, si es menor significa que puede estar dentro del rango de 10 y 20, entonces llegamos a la conclusión de que si max es mayor a 10 y min es menor a 20 esta dentro, también se podría ver al revés, decir que si min es mayor a 20 o max es menor 10 no estaría dentro.
if( min > 20 || max < 10 ) return false;

Teniendo esta afirmación en la dimensión X podemos decir que todas las demás dimensiones la cumplen ya que se comportan igual, con lo que comprobar un cubo con valor máximo y mínimo dentro de otro seria de esta manera:
bool ColisionNDimensiones( Caja caja, Caja caja2 )
{
if( caja1.min.x < caja2.max.x && caja1.max.x > caja2.min.x &&
caja1.min.y < caja2.max.y && caja1.max.y > caja2.min.y &&
caja1.min.z < caja2.max.z && caja1.max.z > caja2.min.z )
{
return true;
}
return false;
}

Nos hemos ahorrado 6 comprobaciones, esta entre otras es una de las ventajas de pensar en n-dimensiones, ¿que ocurría si quisiéramos crear comprobaciones con cubos de mas dimensiones que 3, por ejemplo 5? Seria agregar comprobaciones, algo así:
bool ColisionNDimensiones( Caja caja, Caja caja2 )
{
if( caja1.min.x < caja2.max.x && caja1.max.x > caja2.min.x &&
caja1.min.y < caja2.max.y && caja1.max.y > caja2.min.y &&
caja1.min.z < caja2.max.z && caja1.max.z > caja2.min.y &&
caja1.min.a < caja2.max.a && caja1.max.a > caja2.min.a &&
caja1.min.b < caja2.max.b && caja1.max.b > caja2.min.b
)
{
return true;
}
return false;
}

Como veis mientras mas dimensiones mas comprobaciones nos ahorramos.
Espero que ahora estéis todos pensando en n-dimensiones :)

 

Inaugurando un blog

Después de miles de guerras contra aruba.it y cansado de ver como cada dos por tres mi pagina Web personal esta fuera de servicio (service unavailable), como me quitan los permisos para subir archivos y tener que esperar semanas para poder actualizar y muchas mas pifiadas me he decidido a crear un blog (que esta de moda) para poner mis ideas o chorradas según se mire.
Espero que disfrutéis de la lectura de este blog en el que tengo pensado meter desde ideas extrañas hasta tutoriales de programación, ya veré como organizo todo ya que me parece que los blogs solo tienen búsquedas por fechas.

This page is powered by Blogger. Isn't yours?