sábado, 2 de junio de 2012

¿Problemas de memoria? ... no lo sé, no me acuerdo.

Puede que haya alguien a quien no le preocupe la memoria principal: la posición de los datos en el heap, la fragmentación, la "irritante" falta de espacio en muchos casos, la eficiencia del "malloc standard", los temidos "caches misses",etc.

Las razones por las que no les preocupe pueden ser muchas: son personas "normales", no son programadores, tienen una "vida social sana", ... pero casi nadie que haya tenido que programar para consolas, se puede quedar indiferente ante este "continuo dolor de cabeza".

Yo personalmente, a dia de hoy, sigo entrando en pánico al hacer un "malloc", ni que hablar de un "new". ¿Por qué?. Pues tendré que comenzar explicando mis razones.


Hola señor Arce ... Hola señor Montículo.

Esto puede parecer una canción de "La Hora Chanante" pero nada más alejado de la realidad. El Heap (o montículo si así lo quereis) de memoria, es un mecanismo que gestiona un área de memoria de forma dinámica, aceptando ordenes de reserva y liberación de memoria por parte del usuario.

La interfaz básica que se ofrece en "lenguaje C" (a dia de hoy, todavia el standard en "esta industria") es un par de funciones: "malloc" y "free". "C++" va un poco más allá, y sustituye este par de funciones por un par de operadores que aparecen en esta "extensión del lenguaje": "new" y "delete".

Lo primero que me gustaria destacar es la simplicidad de este método. No hay que pensar que tipo de dato es, donde habria que ponerlo, junto a que otros datos seria eficiente que estuviera, la alineación que deberia tener, ni nada de eso. Es una solución simple y elegante: "Hola, dame 64 bytes memoria." o también: "void* ptr = malloc(64);".

También encontramos los típicos recursos de "C++": "FooClass* pFoo = new FooClass();" Que seria equivalente a: "FooClass* pFoo = (FooClass*)malloc( sizeof(FooClass) );" seguido de una llamada al constructor de la clase, cosa que no podremos hacer sin el "placement new" que seria algo asi: "pFoo = new (pFoo) ();".

Y explicado esto, queda clara una cosa: malloc y free (new y delete)  son una solución genérica. Sea cual sea la utilidad que le quieres dar a la memoria que reservas, todo pasa por estas funciones.


La solución general

No creo que haya una solución genérica para todo. Si la hay, no creo que hagan falta más ingenierios en el mundo, de echo sobrariamos todos.

El buscar la fórmula perfecta para todo no me parece "coherente", ni "razonable", y creo que al final puedes acabar como el protagonista de "Pi: Fe en el Caos" (excelente película por otra parte).

En cambio, el caso de algunas implementaciones de heaps de memoria puede hacerme dudar, en algún momento, de esta afirmación. Casos como el "DougLeaAllocator" se proponen como una muy buena solución para manejar de forma rápida y eficiente todo tipo de "reservas de memoria". Utilizando diferentes partes de la "Arena de Memoria", reserva en espacios distintos para "mallocs" de diferentes tamaños, reduciendo drásticamente el problema de la "fragmentación externa".

Para equipos con grandes cantidades de RAM, con pocos problemas de cache, y un sistema de memoria virtual, el "DougLeaAllocator" es una solución "quasi perfecta". Pero la realidad en la mayoria de dispositivos orientados al "entretenimiento electrónico" es muy diferente.


Un ejemplo


No hay forma mejor de explicar mis "reservas" con el "standard allocator" que un ejemplo.

Como "base" voy a utilizar una estructura común en esto de los "jueguecitos":

struct Vec3
{
  float    x;
  float    y;
  float    z;
};

void set_vec3(Vec3* pOut, float x, float y, float z)
{
  pOut->x = x;
  pOut->y = y;
  pOut->z = z;
}

void set_all_vec3(Vec3* pOut, float val)
{
  pOut->x = val;
  pOut->y = val;
  pOut->z = val;
}

void add_vec3(Vec3* pOut, Vec3* pIn0, Vec3* pIn1)
{
  pOut->x = pIn0->x + pIn1->x;
  pOut->y = pIn0->y + pIn1->y;
  pOut->z = pIn0->z + pIn1->z;
}


void scalar_mult_vec3(Vec3* pOut, Vec3* pIn0, float scalar)
{
  pOut->x = pIn0->x * scalar;
  pOut->y = pIn0->y * scalar;
  pOut->z = pIn0->z * scalar;
}



// A simple random function for floats
inline float random_float01()
{
  return (float)rand()/(float)RAND_MAX;
}

inline float random_float(float min, float max)
{
  return random_float01() *(max-min) + min;
}

inline void random_vec3(Vec3* pOut, Vec3* pMin, Vec3* pMax)
{
  pOut->x = random_float(pMin->x, pMax->x);
  pOut->y = random_float(pMin->y, pMax->y);
  pOut->z = random_float(pMin->z, pMax->z);
}
Como habreis notado define un vector de tres dimensiones, por simplicidad las operaciones definidas son "escalares": NO se definen tipos ni operaciones "vectoriales" o SIMD. Y además tiene un estilo "old C", sin utilizar clases, ni métodos. Esto último se debe a que voy a proponer dos formas de hacer las cosas, una será más "C++", y la otra más "old C", y ambas utilizarán esta estructura y estas operaciones.

Versión C++


La primera versión del código está completamente orientada a objetos, y reserva memoria/libera memoria con "new/delete" para cada objeto (partícula) durante el update.

class Particle
{
public:

  Particle()
  {
    set_all_vec3(&m_position, 0.0f);
    set_vec3(&m_velocity, 0.0f, 10.0f, 0.0f);
    m_life = 2.0f;
  }

  Particle(const Vec3& pos, const Vec3& vel, float life)
    : m_position(pos), m_velocity(vel), m_life(life) { }

  bool update(float dt)
  {
    if (m_life <= 0.0f)
      return false;

    m_life -= dt;

    Vec3 deltaVel;
    scalar_mult_vec3(&deltaVel, &m_velocity, dt);
    add_vec3( &m_position, &m_position, &deltaVel );

    return true;
  }


  //protected: // avoid getters and setters
public:

  Vec3    m_position;
  Vec3    m_velocity;
  float   m_life;
};



class ParticleEmitter
{
public:
  typedef std::list ParticleList;

protected:
  ParticleList            m_particles;
  float                   m_newParticleTime;

  
public:
  // Emitter properties
  float                   m_minRatio;
  float                   m_maxRatio;
  int                     m_maxParticles;
  
  float                   m_minLife;
  float                   m_maxLife;

  Vec3                    m_position;
  Vec3                    m_posOffsetMin;
  Vec3                    m_posOffsetMax;

  Vec3                    m_initMinVel;
  Vec3                    m_initMaxVel;

  Vec3                    m_gravity;


public:
  // Public Interface
  ParticleEmitter()
  {
    reset_defaults();
  }
  
  ~ParticleEmitter()
  {
    clean_list();
  }
  
  void clean_list()
  {
    ParticleList::iterator it      = m_particles.begin();
    ParticleList::iterator it_end  = m_particles.end();
    while( it != it_end )
    {
      Particle* ptr = *it;
      delete ptr;
      ++it;
    }
    m_particles.clear();
  }

  void reset_defaults()
  {
    clean_list();

    // Default properties
    m_minRatio = 0.1f;
    m_maxRatio = 0.2f;
    m_maxParticles = 39;

    set_all_vec3(&m_position, 0.0f);
    set_all_vec3(&m_posOffsetMin, -0.1f);
    set_all_vec3(&m_posOffsetMax, +0.1f);

    const float kOffset = 1.0f;

    set_vec3(&m_initMinVel, -kOffset, +5.0f, -kOffset);
    set_vec3(&m_initMaxVel, +kOffset, +8.0f, +kOffset);

    set_vec3(&m_gravity, 0.0f, -9.8f, 0.0f);


    m_newParticleTime = 0.2f;
  }

  void update(float dt)
  {
    // Update all the particles
    ParticleList::iterator it      = m_particles.begin();
    ParticleList::iterator it_end  = m_particles.end();

    // We need an "extra" list for "dead particles"
    typedef std::list IteratorList;
    IteratorList eraseList;

    Vec3 dtGravity;
    scalar_mult_vec3(&dtGravity, &m_gravity, dt);
    while( it != it_end )
    {
      Particle* pCurrentParticle = (*it);
      // We need to update the velocity of each particle: apply gravity
      add_vec3( &(pCurrentParticle->m_velocity), &(pCurrentParticle->m_velocity), &dtGravity );
      
      // If this particle is dead ...
      if ( pCurrentParticle->update(dt) == false )
      {
        // ... push its iterator in the eraseList
        eraseList.push_back( it );
      }

      ++it;
    }

    // Now, we have to delete the "dead particles"
    IteratorList::iterator erase_it      = eraseList.begin();
    IteratorList::iterator erase_it_end  = eraseList.end();

    while( erase_it != erase_it_end )
    {
      Particle* ptr = *(*erase_it);
      m_particles.erase( *erase_it );
      delete ptr;
      ++erase_it;
    }


    // Now we can create a new particle
    m_newParticleTime -= dt;
    int particleCount = m_particles.size();
    while ( m_newParticleTime <= 0.0f && particleCount < m_maxParticles )
    {
      Vec3 newPos;
      Vec3 newVel;
      random_vec3(&newPos, &m_posOffsetMin, &m_posOffsetMax);
      add_vec3(&newPos, &newPos, &m_position);
      random_vec3(&newVel, &m_initMinVel, &m_initMaxVel);
      m_particles.push_back( new Particle(newPos, newVel, random_float(m_minLife, m_maxLife)) );
      m_newParticleTime += random_float(m_minRatio, m_maxRatio);
      particleCount++;
    }
  }


  inline ParticleList::iterator get_begin_iterator() { return m_particles.begin();  }
  inline ParticleList::iterator get_end_iterator() { return m_particles.end();  }

  
};
Como veis, es un "emisor de particulas" extremadamente sencillo. Utiliza std::list para almacenar las particulas, aunque sustiuyendo el typdef ParticleList por std::vector debiera funcionar igual.

Un verdadero sistema de partículas deberia tener muchas más cosas. Explicar y debatir sobre como hacer un buen sistema de partículas incluye muchas cosas: data-driving, como soportar diferentes tipos de particulas, affectors, métodos de batch para el dibujado, etc. Y podria dar para un par o más de posts como este, así que lo dejaremos para otro momento. Insisto en que esto es un ejemplo simplificado.

Cualquier iniciado en C++, me diria que deberia poner la función de dibujado dentro de la clase partícula, para así tener el código "super-ordenado de la muerte". Yo en cambio, prefiero tener el dibujado en otra parte, para poder "hacer decoupling" y mantener la independencia del método de render.




A primera vista, las ventajas de esta versión serian el poder derivar tipos de particulas y virtualizar el método update. Y ya puestos, derivamos tambien el emitter, y ponemos que compartan la funcion de actualizacion, pero ponemos un método virtual puro (para liarla más, si cabe, al estilo C++) para crear nuevas particulas, y asi cada emitter puede crear las particulas que quiera del tipo que quiera.

Bien, pues esto último, para mi es una ¡¡Barbaridad!!. Comenzar a meter polimorfismo en objetos que se manejan en grandes cantidades durante cada frame es irresponsable. Las llamadas a métodos virtuales implican fallos de cache alarmantes (tanto en D-Cache como en I-Cache), porque esto implica acceder al "Puntero de la Virtual-Table" del objeto, de ahi resolver el puntero para acceder a la "Virtual-Table", ahi cojemos el offset de la dirección de la función, lo aplicamos y obtenemos finalmente el "puntero a función", con los que solo nos quedaria llamar al mismo con el puntero de la "estructura de datos implicita en la clase". Como cada una de estas cosas (excepto el puntero a v-table y la "estructura de datos") esta cada una wen un sitio de la memoria, no hay principio de localidad que se pueda aplicar a esta operación.

Versión "old C"


La siguiente versión, es más "C style" que la anterior, aunque sigue siendo "C++" ya que se utilizan diversas ventajas del mismo: namespaces, declarar las variables dentro de las funciones donde plazca, no tener que usar typedef struct, etc. Aqui está el código:
struct ParticleEmitter
{
  // Struct of arrays: more cache friendly than array of structs
  Vec3*             positionArray;
  Vec3*             velocityArray;
  float*            lifeArray;
  unsigned int      particleCount;

  float             newParticleTime;

  
  // Emitter properties
  float             minRatio;
  float             maxRatio;
  unsigned int      maxParticles;
  
  float             minLife;
  float             maxLife;

  Vec3              position;
  Vec3              posOffsetMin;
  Vec3              posOffsetMax;

  Vec3              initMinVel;
  Vec3              initMaxVel;

  Vec3              gravity;  
};



void set_emitter_defaults(ParticleEmitter* pEmitter)
{
    // Default properties
    pEmitter->minRatio = 0.1f;
    pEmitter->maxRatio = 0.2f;
    
    set_all_vec3(&(pEmitter->position), 0.0f);
    set_all_vec3(&(pEmitter->posOffsetMin), -0.1f);
    set_all_vec3(&(pEmitter->posOffsetMax), +0.1f);

    const float kOffset = 1.0f;

    set_vec3(&(pEmitter->initMinVel), -kOffset, +5.0f, -kOffset);
    set_vec3(&(pEmitter->initMaxVel), +kOffset, +8.0f, +kOffset);

    set_vec3(&(pEmitter->gravity), 0.0f, -9.8f, 0.0f);


    pEmitter->newParticleTime = 0.2f;
}

ParticleEmitter* create_emitter(unsigned int maxParticles)
{
  // We only need a single block of memory for all the structure
  unsigned int totalSize = sizeof(ParticleEmitter) +
    (sizeof(Vec3)*2 + sizeof(float)) * maxParticles;

  ParticleEmitter* pEmitter = (ParticleEmitter*)malloc( totalSize );

  // We need to init the pointers
  unsigned char* ptr = (unsigned char*)(pEmitter+1);
  unsigned int vec3ArraySize = sizeof(Vec3) * maxParticles;

  pEmitter->positionArray = (Vec3*)ptr;
  ptr += vec3ArraySize;
  pEmitter->velocityArray = (Vec3*)ptr;
  ptr += vec3ArraySize;
  pEmitter->lifeArray = (float*)ptr;

  // Init particle counters
  pEmitter->particleCount = 0;
  pEmitter->maxParticles = maxParticles;

  set_emitter_defaults( pEmitter );

  return pEmitter;
}

void destroy_emitter(ParticleEmitter* pEmitter)
{
  free( pEmitter );
}


void update_emitter(ParticleEmitter* pEmitter, float dt)
{

  Vec3 dtGravity;
  scalar_mult_vec3(&dtGravity, &(pEmitter->gravity), dt);

  Vec3*   positionArray = pEmitter->positionArray;
  Vec3*   velocityArray = pEmitter->velocityArray;
  float*  lifeArray = pEmitter->lifeArray;
  
  const unsigned int kEraseArraySize = 10;
  unsigned int eraseArray[kEraseArraySize];
  unsigned int eraseArrayCount = 0;

  for(unsigned int i = 0; i < pEmitter->particleCount; i++)
  {
    // Apply gravity
    add_vec3(&velocityArray[i], &velocityArray[i], &dtGravity);
    // Apply movement
    Vec3 deltaVel;
    scalar_mult_vec3( &deltaVel, &velocityArray[i], dt );
    add_vec3(&positionArray[i], &positionArray[i], &deltaVel);
    // Decrease life
    lifeArray[i] -= dt;

    if (lifeArray[i] <= 0.0f && eraseArrayCount < kEraseArraySize)
    {
      eraseArray[eraseArrayCount] = i;
      eraseArrayCount++;
     }
  }

  while (eraseArrayCount > 0) // && pEmitter->particleCount > 0)
  {
    eraseArrayCount--;
    pEmitter->particleCount--;
    // Erase and swap-last
    int eraseElement = eraseArray[eraseArrayCount];
    positionArray[eraseElement] = positionArray[pEmitter->particleCount];
    velocityArray[eraseElement] = velocityArray[pEmitter->particleCount];
    lifeArray[eraseElement] = lifeArray[pEmitter->particleCount];
  }


  // New particle??
  pEmitter->newParticleTime -= dt;
  unsigned int particleCount = pEmitter->particleCount;
  while ( pEmitter->newParticleTime <= 0.0f && particleCount < pEmitter->maxParticles )
  {
    Vec3* pPosition = &(positionArray[particleCount]);
    random_vec3( pPosition, &(pEmitter->posOffsetMin), &(pEmitter->posOffsetMax) );
    add_vec3( pPosition, pPosition, &(pEmitter->position) );
    random_vec3( &(velocityArray[particleCount]), &(pEmitter->initMinVel), &(pEmitter->initMaxVel) );
    lifeArray[particleCount] = random_float(pEmitter->minLife, pEmitter->maxLife);

    pEmitter->particleCount++;
    particleCount++;
    pEmitter->newParticleTime += random_float(pEmitter->minRatio, pEmitter->maxRatio);
  }

}

Más allá de si el código es "C" o "C++", la verdadera mejora aqui está en reservar memoria una sola vez: durante la creación del emitter.

Probandolo


Para ilustrar la eficiencia de un método y otro, he probado ambos métodos en el Typhoeus. El código utilizado:

// .......

// "Blog Particles Example" setup:

// cpp version
l_cppEmitter.m_maxParticles = 180;
l_cppEmitter.m_minLife = 1.0f;
l_cppEmitter.m_maxLife = 2.0f;
l_cppEmitter.m_minRatio = 0.001f;
l_cppEmitter.m_maxRatio = 0.01f;
blog_particles::set_vec3( &(l_cppEmitter.m_position), +2.0f, 0.0f, 0.0f);

// "old c" version
l_pOldCEmitter = blog_particles::oldc_way::create_emitter( 180 );
l_pOldCEmitter->minLife = 1.0f;
l_pOldCEmitter->maxLife = 2.0f;
l_pOldCEmitter->minRatio = 0.001f;
l_pOldCEmitter->maxRatio = 0.01f;
blog_particles::set_vec3( &(l_pOldCEmitter->position), -2.0f, 0.0f, 0.0f);


// .......

// update
{
  TY_PROFILE_BLOCK( _CPP_EMITTER );
  l_cppEmitter.update( game_dt );
}

{
  TY_PROFILE_BLOCK( _OLDC_EMITTER );
  blog_particles::oldc_way::update_emitter( l_pOldCEmitter, game_dt );
}

// .......

Y para dibujar, yo he utlizado el sistema de dibujado de depuración que ya tengo implementado.
// .......

// CPP VERSION

blog_particles::cpp_way::ParticleEmitter::ParticleList::iterator it, it_end;
it = l_cppEmitter.get_begin_iterator();
it_end = l_cppEmitter.get_end_iterator();
while( it != it_end )
{
  blog_particles::cpp_way::Particle* pCurrentParticle = *it;
  g_debugDrawMngr.add_cross( blog_Vec3_to_Point3( pCurrentParticle->m_position ),
    0.2f, Color::GREEN(), 2.0f );

  ++it;
}

// .......

// "OLD C" VERSION
for (unsigned int i = 0; i < l_pOldCEmitter->particleCount; i++)
{
  g_debugDrawMngr.add_cross( blog_Vec3_to_Point3( l_pOldCEmitter->positionArray[i] ),
    0.2f, Color::RED(), 2.0f
}

// .......

Pongo una captura de pantalla:





Y ahora capturas del profiler, probado en una máquina Intel de 64 bits. (que realmente no es el tipo de arquitectura donde más se tendrian que notar estas diferencias)

La versión DEBUG:


Y de la versión RELEASE:



Por los resultados (aunque en este caso hay bastante poco que actualizar) nos damos cuenta de varias cosas.
  1. En DEBUG utilizar STL suele ser muy lento, pero esto no deberia ser un problema, ya que para eso son la veriones DEBUG, ¿no?
  2. En RELEASE notamos, quizás, mayor proceso optimización por parte del compilador en la versión c++, seguramente por el uso de la STL.
  3. En RELEASE (la que en teoria vale) podemos ver como la versión C++ es entre 3 y 5 veces más lenta, asi como más susceptible a cambios de frame-rate. Pero esto tiene que ver claramente, con el uso de "new" y "delete" continuamente.

No es una "batalla entre lenguajes"


Siempre hay un termino medio, y todo tiene sus ventajas y desventajas. La versión C++, aunque más lenta, permitiria un "generalización" utilizando métodos virtuales, pero eso claramente influiria, todavia más, en el performance del mismo.

Seria razonable pensar (o al menos asi lo intento hacer yo), que se puede coger cosas buenas de la versión "old C", y reescribir el código de forma un poco más "C++", utilizando clases, etc. pero teniendo en cuenta que factores afectan a la eficiencia.

Incluso se podria (aunque yo nunca utilizo STL en "runtime") usar un std::vector, en vez de arrays de "C". Bien utilizado (almacenando objetos en vez de punteros, y inicializando el tamaño con un reserve) deberia de ser tan eficiente como la versión "C".


Otros factores: "Concurrencia"


Controlar que tipo de datos tienes en memoria, y donde los tienes, en vez dejarte envolver en la aparente mágia del "encapsulamiento" y otras falsas maravillas de la POO, es una ventaja para el "procesado concurrente".

A veces compartir datos entre diferentes hilos, nucleos e incluso procesadores (vesasé PPU-SPU) no es tan sencillo como pueda parecer en un principio.

Si tomamos el ejemplo de una SPU te puedes ir olvidando del "maravilloso polimorfismo", los templates, y de tener los datos "desperdigados" por la RAM.

Tener una API "estilo C" para un "subsistema crítico", te puede permitir compartir mayor cantidad de código entre la PPU y la SPU, pudiendo tener varias versiones del mismo subsitema (funcionando de una u otra manera). Amén, de darte una "perspectiva más clara" de lo que se trata todo esto de los jueguecitos: datos y transformaciones.

Además tener los datos consecutivos en memoria te facilita enormemente la vida para poder lidiar con las alineaciones, y la creacion de las DMA-Lists.


El source code


He subido el source con una licencia MIT:  ENLACE.

Por simplicidad, lo he metido todo en un .h (incluidas implementaciones de funciones), así que si quieres incluirlo desde varios cpps, deberias sacar la implementación de las funciones (al menos) a otro .cpp, y dejar la declaración el en header.

Algunas conclusiones

  • Los malloc/free no son gratis.
  • Hay que evitarlos a toda costa durante el game_loop.
  • La llamadas a métodos virtuales: cuanto menos, mejor.
  • "Dispersar" objetos (en memoria) que se deben actualizar de forma consecutiva durante el frame es una temeridad. Un array de "toda la vida" siempre te asegura que los datos van a estar consecutivos en memoria, lo que favorece la reutilización de la "memoria precargada" en la cache.
  • Controlar la memoria y los datos y evitar el polimorfismo es una buena práctica para facilitar la programación concurrente.

Y en próximos episodios ...

La verdad es que me ha quedado más largo de lo que esperaba, así que dejaré para el siguiente post la explicación de como manejo la memoria en el Typhoeus:
  • Trazado de reservas / liberaciones.
  • Memory Leak Detection.
  • "Mapa visual" de memoria.
  • Custom Allocators
  • Colecciones Propias
  • etc

Pues nada, ¡hasta la próxima!