Stratos: Punto de Encuentro de Desarrolladores

¡Bienvenido a Stratos!

Acceder

Foros





Reciclado de memoria - Fernando Rodríguez

Iniciado por ethernet, 11 de Diciembre de 2002, 08:11:10 PM

« anterior - próximo »

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:


     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 :


    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                                
    hat the hells!

    fiero

                                   
    Citar
    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                                
    www.videopanoramas.com Videopanoramas 3D player

    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/                                
    IndieLib Libreria 2.5d utilizando aceleración por hardware para la programación de juegos 2d.
    Indie Rover The monkeys are reading!

    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                                
    www.videopanoramas.com Videopanoramas 3D player

    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






    Stratos es un servicio gratuito, cuyos costes se cubren en parte con la publicidad.
    Por favor, desactiva el bloqueador de anuncios en esta web para ayudar a que siga adelante.
    Muchísimas gracias.