Reciclado de memoria - Fernando Rodríguez

[ethernet]

La clase que mando se encarga de reciclar nodos que han sido
creados en memoria. Para ello, éstos se crearán una sola vez
usando new y no serán destruidos con delete hasta que se finalice
la instancia a la clase. Las llamadas new y delete son muy
costosas, sobre todo cuando las necesitamos hacer de forma
numerosa y en grandes cantidades, haciendo que la velocidad de
procesado de nuestros algoritmos se vean seriamente dañada en el
momento en que comenzamos a utilizarlos de forma reiterada. No
hay que confundir esta clase con un manejador de memoria pero si
apuntar que en caso de disponer de uno, CRecycleNodePool se
podría beneficiar de su uso; bastaría sustituir las llamadas new
y delete internas por las del manejador

Así pues, la principal utilidad de CRecycleNodePool es la de
servir de apoyo a algoritmos en los que hace falta la creación de
un número elevado de nodos de información a consultar. De esta
forma, los algoritmos de IA pueden beneficiarse en gran medida
Un ejemplo es el de búsqueda de caminos A*, que necesita de la
creación de una gran cantidad de nodos con datos heurísticos, o
cualquier proceso backtraking en general. Sin embargo, también
podemos encontrar de gran utilidad esta clase en el trabajo con
subsistemas gráficos que funcionen en dos pasadas, esto es, con
una destinada a alojar las peticiones de dibujado (que irían en
nodos) y con otra encargada de recorrer todas las peticiones
previas para realizar el dibujado propiamente dicho

Como apuntes sobre el código, decir que he utilizado las STL para
tratar las estructuras de datos de apoyo (mantengo una lista de
nodos disponible y un conjunto de nodos usados) y uso el
protocolo Init / End que Javier Arévalo expuso hace tiempo en
Flipcode
(

http://www.flipcode.com/cgi-bin/msg.cgi?showThread=Tip-ObjectIni
tFinal&forum=totd&id=-1). La clase está implementada como
template para permitir la creación de un almacén genérico
También acudo a los asertos bastante a menudo (recomiendo que
cada cual sustituya los assert por sus propias macros), ya que
permiten asegurar el codigo en fase de desarrollo y contribuyen a
comentarlo

Para finalizar, paso a comentar muy brevemente los métodos
públicos existentes (hay comentarios más exhaustivos en el
código)

bool Init(const unsigned short& usInitSize = 0)

Inicializa / reinicializa la instancia. Recibe el tamaño inicial
del pool (almacén) de memoria

void End(void);

Finaliza la instancia

inline bool IsInitOk(void) const

Comprueba si la instancia esta correctamente inicializada

Node* GetNode(void);

Obtiene un nodo (si no fuera posible, retornará dirección nula)

void FreeNode(Node* const pNode);

Libera un nodo previamente solicitado con GetNode (nótese no se
llamará a delete)

void Realloc(const unsigned short& usNewSize);

Redimensiona el pool de nodos disponibles

inline unsigned short GetNumFreeNodes(void) const

Obtiene el número de nodos disponibles

inline unsigned short GetNumUsedNodes(void) const

Obtiene el número de nodos actualmente usados


Puedes bajarte el codigo de:

http://www.stratos-ad.com/codigosemana/cre...clenodepool.zip  




Éste código fue enviado el martes 3 de diciembre del 2002  por Fernando Rodríguez frodrig99@yahoo.com

Si quieres enviar tu propio código hazlo a eth_cotd@lycos.es

[ethernet]

Buen cotw !

Unos detalles:

Código [Seleccionar] Expand



 assert(usNumNodes < MAX_POOL_SIZE);

 unsigned short usIt = 0;

 for (; usIt < usNumNodes; ++usIt) {

Node* const pNode = new Node;

assert(pNode);

m_FreeNodes.push_back(pNode);

 }


yo lo cambiaria por :

Código [Seleccionar] Expand



assert(usNumNodes < MAX_POOL_SIZE);

 unsigned short usIt = 0;

 Node* const pNode = new Node[usNumNodes];

 assert(pNode);

 for (; usIt < usNumNodes; ++usIt) {

m_FreeNodes.push_back(pNode + usIt * sizeof(Node) );



 }



de esa manera solo reservas una vez.

Otra cosa q no entiendo es por q pasar un unsigned short con &. Por q unsigned short? por q & y no pasarlo directamente (q acupa menos pila, si eso es lo q te preocupa) ?

Por cierto, creo q en release el assert se deshabilita.
Tb tengo entendido q STL hace algo parecido a lo q haces tu, reserva memoria con antelacion. En la doc de la STL de SGI viene al final explicado.

saludos

[Grugnorr]

                                Gracias fer :P                                

[fiero]

                               

Otra cosa q no entiendo es por q pasar un unsigned short con &. Por q unsigned short? por q & y no pasarlo directamente (q acupa menos pila, si eso es lo q te preocupa) ?

Solo una puntualización, un unsigned short& ocupa lo mismo en la pila que un unsigned short* y que un unsigned short. Las tres formas meten 32 bits en la pila (1 posición), al hacer la llamada. Es que yo he entendido eso, si no te referias a esa "pila" pido perdón  :oops:  :)

un saludo                                

[metaxas]

                                ¡ Muy buen COTD !, te comento par de cosillas que se me ocurren para tratar de hacerlo más eficiente:

- Cada vez que creas un nodo nuevo para la lista de libres, lo creas en el heap. Dado que el pool tiene un tamaño máximo, puedes crearte un array de Nodes de ese tamaño en la pila (los accesos a variables declaradas en la pila son más rápidos que los accesos al heap), y en vez de crear un Node nuevo y meter su puntero en la lista de libres, meterías el puntero al Node adecuado en el array. Para borrar un node, lo que harías sería resetear el Node del array a sus valores por defecto, en vez de hacerle un delete.
- El std::list que usas para guardar los nodos libres. Cada vez que le haces un push_back te está reservando memoria para almacenar el puntero, pues al contrario que el vector el list no te reserva memoria en segmentos de tamaño fijo, sino individualmente para cada elemento. Lo ideal sería hacerle un resize de MAX_NODES al principio y hacer siempre un push_front y un pop_front, como si fuese una pila vamos, pero eso sí, guardando tu un contador con el tamaño actual en cada momento (pues al hacerle un size() te devolvería siempre MAX_NODES)


Metaxas                                

[ethernet]

Un unsigned short en mi maquina son 16 bits ... y en mi maquina un unsigned short & y un unsigned short * son 32 bits. y mi maquina trabaja mejor con datos de 32 bits. Y la tuya ? XD

saludos

[Frodrig]

                                Hola chicos, perdonad por no responder antes pero ayer por la noche todo mi equipo se ha ido a hacer gargaras (machacado esta el pobre) en lo relativo a disco duro y ahora estoy con un portatil que no es mio y que tengo que devolver de inmediato.

En primer lugar, con el codigo mostrado he pretendido que fuera didactico, pequeño y, sobre todo, limpio y facil de entender. Asi pues:

1/ Estoy con la mejora apuntada por ethernet acerca de la creacion de los nodos, su propuesta esta mucho mas optimizada y no aporta ninguna dificultad de comprension.

2/ Naturalmente que los assertos no estan en version release (a no ser que te curres tu propio assert y seas tu el que decidas cuando y cuando no estan), pero su utilidad esta mas orientada a lo que es el proceso de creacion de esta clase. En un proyecto real habra que tirar de otros mecanimos de localizacion de errores, como loggers, excepciones, etc. Lo importante de los assertos, ademas de permitir cazar errores, es que nos permiten comprender mucho mejor el codigo y reafirman la logica del mismo a medida que este se va leyendo, sobre todo cuando lo hace otra persona que no es uno de nosotros (los creadores del codigo).

3/El ordenador trabajara mejor con datos de 32 bits, pero esa implementacion estaria mas orientada a crear codigo optimizado, que no es el caso de este codigo, yo he pretendido utilizando unsigned short ceñirme a la realidad; es practicamente imposible que se cubran los 16 bits con nodos en memoria, si esto fuera asi... el volumen de datos distaria de ser manejable, con lo que se contribuye a comprender el funcionamiento de la clase. De hecho, estuve tentado de poner un typedef con un tipo predefinido para utilizar con valor estandar y asi facilitar el cambio.

4/ Uso referencias con const, porque en la vida real, dentro de un motor, lo mas normal sera que se trabaje con variables y recoger estas mediante referencias es mucho mas rapido y seguro que hacerlo utilizando punteros.

5/ No utilice un vector o un array como apunte metaxas por la misma razon que he apuntado mas arriba en cuanto al volumen de nodos manejados, seria un malgasto de memoria anticiparnos a la totalidad de nodos que realmente vamos a utilizar, con el sistema actual estamos preparados para responder al peor de los casos (cuando el numero de nodos sea maximo) pero nunca iremos "mas alla". No se si me explico.
Una excelente forma de aplicar tu idea seria solicitar por template el tamaño maximo del pool y entonces crear ese vector utilizando reserve para el peor y maximo de los casos (el tamaño pasado por template). Como veis, la clase esta muy ligada a la forma en la que quereis implementar la idea en vuestros proyectos.

Saludos.                                

[ElQueSeRompeElOrto]

                                "ethernet" escribio:

Un unsigned short en mi maquina son 16 bits ... y en mi maquina un unsigned short & y un unsigned short * son 32 bits. y mi maquina trabaja mejor con datos de 32 bits. Y la tuya ? XD


Mira ethernet tu maquina deve ser cualquiercosa menos una PC compatible , si es que estamos hablando de pasar argumentos a funciones , esto se realiza algo asi:
En C: -------------------
void vMyFuncionBebe( int Argumento1 ,unsigned short Argumento2 ,int * pArgumento3 );

Compilado seria:(en el momento de la llamada) ------------------------------
Push [DireccionDeRetorno]
push Argumento1
push Argumento2
push Argumento3

Para que no te quede claro que ,"push" si estas en un procesador de 32 bits ,te va a meter en la pila 32 bits ya que como veras no se puede especificar cuantos bytes o bits se meteran ,por lo que si en memoria tu unsigned short ocupa 2 Bytes , irremediablemente se lo metera en la pila como 4 bytes.

Estoy Casi Seguro que es asi ...bue sino alguien corrija un saludo.

                               

[synchrnzr]

                                Mmmm... yo no estaría tan seguro de eso que dices

Sync                                

[ethernet]

Ya dudo q no se pueda hacer push word ax por ejemplo, aunque para mas detalles y ver si c *siempre* pone 4 bytes (en x86) podemos mirar las macros va_* para funciones con numero de parametros variables.
saludos

[Loover]

                                Creo que el que rompe el culete tiene razón. Los registros (en todos los ordenadores basados en el 80/86 son de 32 bits. Si se apila una variable de 16 bits dejará la parte alta del registro a 0, pero no por eso ocupara 16 bits. Vamos, eso tengo entendido. La verdad es que no tengo muy fresca la asignatura de computadores...

Mirar la parte de en esta dirección:
http://www.ele.uva.es/~imartin/noticias/pe...cos/compilador/                                

[synchrnzr]

                                Pues permíteme que se la quite :X9:

Haced la prueba del algodón:

PUSH AX
PUSH EAX

y comprobad el valor de ESP a cada paso. Vereis que en el primer PUSH, ESP se decrementa en 2 y en el segundo en 4 ;)

Lo que sí que no se puede hacer es un PUSH de un registro de 8 bits.

Sync

PD: Hace tiempecillo que no programo en ASM que no sea el de la GameBoy Advance, pero antes había programado mucho mucho mucho... y aun os puedo sorprender :D                                

[fiero]

                                Elqueserompeelorto tiene razón. Aunque se puede poner en pila 16 bits, por defecto, VC mete siempre 32:

mov ax,variable_short
push eax

Es más, cuando dentro de una función se definen parámetros de la siguiente manera:

void funcion(void)
{
    short f,g;

en modo debug se reservan 2 bytes por variable. Sin embargo en modo release (imagino que por cuestiones de optimización para código más rápido), se reservan 4 bytes por variable.

Por cierto, en cuanto al cotw en cuestión muy buena idea.

un saludo

PD: ups, se ha metido sync en medio XD                                

[synchrnzr]

                                Sí, soy como el jueves (el día, no la revista... bueno... no sé...  :D )

Es probable que el acceder a direcciones alineadas a 32 bits sea más rápido (aunque también tengo mis dudas ^_^) De todas formas si el tema es si se puede acceder a elementos en la pila de 16/32 bits, se puede desde el 386 hasta el Pentium III (y/o compatibles  :P ) Lo que hagan o dejen de hacer los compiladores ya es otra cosa (especialmente el VC++, que es software de Microsoft y hay que tratarlo como tal  :X9: )

Sync                                

[ethernet]

aja, o sea short *p = new short [1000]; me ocupa 4000 bytes en vez de 2000 ? (me refiero en un x86) .Eso si q optimiza memoria.
Otra cosa es q trabaje con los short como con los int debido a la arquitectura del micro.


saludos