miércoles, noviembre 12, 2008

Core coding

En estos días mientras salgo del slump en el que ando con el diseño de unas estructuras de datos para el problema de mi proyecto doctoral, me fui entonces a hacer otra cosa que es más lateral, pero que esta intrínsecamente relacionada con el rendimiento del programa, y es el manejo de memoria.

La verdad, yo siempre me he considerado un programador de “alto nivel” (en el sentido de la abstracción de la programación, claro xD, no en que me considere muy superior o algo así!), es decir, que minimizo al máximo el manejo de memoria, la aritmética de punteros. Por supuesto, como todo programador de C/C++, yo adoro los punteros xD (no entiendo como pueden vivir los programadores de Java sin ellos!), pero en general mi manejo de apuntadores es lo más sencillo posible, y si puedo, los emulo con arrays.

A la hora de trabajar con la memoria, el conteo de posiciones, y el cambio del tipo del puntero (“castings”) son cruciales. Tuve que recurrir a estas operaciones de “bajo nivel” para diseñar un manejador de memoria, que no llamara al OS cada vez que necesito más memoria, pues mi implementación usa muchas listas encadenadas, pues mientras hago las búsquedas no tengo forma de saber cuantos elementos voy a necesitar, puedo saber cual es el valor máximo, pero el valor mínimo puede estar muy por debajo de ese valor... En todo caso, al pedir memoria para cada elemento de la lista, se pierde un poquito de tiempo, que para problemas que no son necesariamente grandes, empieza a ser apreciable...

Pablo me propuso que usara el manejador que tiene TNT, pero yo quiero un programa que sea de código abierto (igual, fue Pablo quien me hizo notar la importancia de manejar la memoria, yo por mi mismo, nunca lo hubiera pensado :P) así que me puse a buscar por ahí, y encontré que en el Kernighan & Ritchie hay un ejemplo de como implementar una función tipo malloc. La implementación del libro blanco es super pequeña y sencilla: una estructura que tiene un puntero a el siguiente bloque libre de memoria, y el tamaño del bloque.

Yo hice una un poco más compleja que mantiene unidos siempre a todos los bloques de memoria, de manera que si quiero limpiar todo el heap que este usando, lo pueda hacer (i.e. En caso de leaks de memoria, aún puedo liberar el bloque completo), con la implementación de K&R no se me ocurre como hacer eso (o bueno, se puede hacer haciendo una especie de meta-cabecera que controlara cada bloque), porque los bloques libres solo apuntan a otro bloque libre, así que no podemos encontrar los bloques ocupados.

Mi solución es tener una estructura con tres elementos: el puntero al siguiente bloque, el tamaño del bloque, y el estado del bloque (es decir, si esta libre o no). De esa forma, si yo quisiera liberar la memoria, solo tengo que recorrer la lista: no hay posibilidad de leak!

Bueno, mi manejador funciona bien en los ejemplitos de depuración que escribí, ahora voy a ponerlo en el piloto que tenía hasta el momento y ver si no se produce ningún comportamiento extraño xD.

Pd. Por cierto, si todo sale con lo planeado, hoy viajo a Buenos Aires... No se si es motivo para alegrarme o para sentirme aburrido xP.

Pd2. Humor geek para la ocasión, vía Fox Trot


No hay comentarios.: