BLOG C++

Programa lento? Já viu se é a gerência de memória?

Redefinindo os operadores new e delete

É fato conhecido entre os programadores C++ que a gerência de memória implementada na biblioteca padrão do C/C++ é ineficiente para a alocação/liberação de muitos (mas muuuuuitos mesmo!) blocos de memória de tamanhos distintos. Programas que alocam e liberam objetos freneticamente pagam um preço muito alto se utilizarem os operadores new e delete padrão. O problema ocorre porque as rotinas que manipulam os blocos de memória devem lidar com blocos de tamanhos diferentes, e isso significa trabalhar com listas encadeadas, encontrar blocos de tamanho adequado, fragmentação etc. Nesse link há uma pequena introdução sobre o assunto.

O programa a seguir aloca e desaloca objetos freneticamente. Não quero discutir o que o programa faz, na verdade ele foi copiado daqui (uma comparação de desempenho entre Java, C++ e outras linguagens…) com duas pequenas alterações: 1) eliminei a chamada a gettimeofday e meço o tempo pelo SO; 2) o programa original tinha um leak de memória. Quero apenas mostrar como esse programa roda usando o new e delete padrão, e como uma abordagem não intrusiva para redefinir esses operadores consegue fazer com que esse programa rode 10x mais rápido…

Código original:

#include <stdio.h>
#include <iostream>

using namespace std;

class Person {
  public:
    Person( int id, int count ): _next(NULL), _prev(NULL), _count(count), _id(id) {}

    int shout( int shout, int nth ) {
      if( shout < nth )
        return shout + 1;

      _prev->_next = _next;
      _next->_prev = _prev;

      return 1;
    }

    int count() const { return _count; }
    Person* next() const { return _next; }
    Person* prev() const { return _prev; }

    void next(Person* person) { this->_next = person ; }
    void prev(Person* person) { this->_prev = person; }

   private:
     int _count;
     int _id;
     Person* _next;
     Person* _prev;
};

class Chain {
  public:
    Chain(const int id, const int size) : _first(NULL), _id(id) {
      Person* current = NULL;
      Person* last = NULL;

      for( int i = 0 ; i < size ; i++ )
      {
        current = new Person( id + i, i );

        if( _first == NULL )
          _first = current;

        if( last != NULL ) {
          last->next(current);
          current->prev(last);
        }

        last = current;
      }

      _first->prev(last);
      last->next(_first);
    }

    Person* kill( const int nth ) {
      Person* current = _first;
      int shout = 1;

      while( current->next() != current )
      {
        Person* tmp = current;

        shout = current->shout( shout,nth );
        current = current->next();

        if( shout == 1 )
          delete tmp;
      }

      _first = current;

      return current;
    }

    Person* first() const  { return _first; }

    ~Chain() { delete _first; }

  private:
      Person* _first;
      int _id;
};

int main( int argc, char* argv[] )
{
  const int ITER = 10000000;

  for( int i = 0 ; i < ITER ; ++i ) {
    Chain* chain = new Chain(i, 40);

    chain->kill(3);
    delete chain;
  }

  return 0;
}

Ok, o código acima é meio doido. É sobre a história de Flávio Josefo, por vezes designado como problema de Josefo ou Roleta Romana. Mas o interessante é que ele aloca e libera 410 milhões de pequenos objetos com dois tamanhos diferentes e de forma intercalada, gerando um estresse nas rotinas de gerência de memória. Apesar desse número, o consumo de memória do programa é mínimo: a cada instante, o número máximo de objetos alocados é 41. De certa forma, esse programa mimetiza o comportamento de um programa que executa sequencialmente milhares de pequenas tarefas por minuto em transações curtas: para cada tarefa é alocado um pequeno número de objetos de tamanhos distintos e após a transação estes objetos são liberados.  O tempo de execução e opções de compilação são mostrados a seguir:

Máquina          : Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
Sistema          : Windows XP SP2
Compilador       : gcc version 4.4.0 (mingw32)
Linha de comando : g++ -O3 -funroll-loops -fprefetch-loop-arrays -march=core2 -msse4 ChainOriginal.cpp -o ChainOriginal.exe
Tempo de execução: 71.88 segundos

Pois bem, o que há de errado com esse código? Nada, exceto que os operadores new e delete fazem uma série de operações internas sobre listas encadeadas de espaços de memória livre que os tornam um pouco lentos. A gerência da memória dinâmica é um tópico complexo de estudo. Há vários substitutos específicos das rotinas padrão do C++ que gerenciam memória e que são mais eficientes para determinadas situações do que as rotinas genéricas. E há algumas técnicas para diminuir o tempo gasto com essa gerência – aqui vou mostrar uma variação bem simples de uma técnica conhecida como slab allocation e que é utilizada por exemplo pelo kernel do Linux. Essa técnica funciona com buffers ou caches de áreas de memória, uma para cada determinado tipo de objeto, e se adequa bem para a situação acima. Ela é muito boa quando o programa possui um número qualquer de objetos de classes distintas sendo alocados e liberados frequentemente. A implementação a seguir funciona apenas quando a não há hierarquia de classes – ou seja, não há subclasses. Para funcionar com subclasses é necessária uma outra implementação, um pouco menos eficiente pois terá de lidar com destrutores virtuais e sobrecarga de operadores. Mas vamos por partes.

Non-Virtual Slab Allocation:

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

class Cache {
  private:
    vector<void*> cache;

  public:
    enum Config { Max = 100 }; // Número máximo de objetos mantido no cache.
                               // Quando esse número é atingido, as chamadas
                               // a "free" realmente liberam os objetos.

    Cache(): cache() {
      cache.reserve( Max );
    }

    void *alloc( size_t size ) {
      if( cache.size() > 0 ) {
        void* aux = cache.back();

        cache.pop_back();
        return aux;
      }
      else
        return new char[size];
    }

    void free( void* ptr ) {
      if( cache.size() < Max )
        cache.push_back( ptr );
      else
        delete[] (char *) ptr;
    }
};

template <class C>
class NonVirtualSlab {
  private:
    static Cache cache;

  public:
    void* operator new ( size_t size ) {
      return cache.alloc( size );
    }

    void operator delete ( void* ptr, size_t ) {
      cache.free( ptr );
    }
};

template <class C>
Cache NonVirtualSlab<C>::cache;

class Person: public NonVirtualSlab<Person> {
  public:
    Person( int id, int count ): _next(NULL), _prev(NULL), _count(count), _id(id) {}

    int shout( int shout, int nth ) {
      if( shout < nth )
        return shout + 1;

      _prev->_next = _next;
      _next->_prev = _prev;

      return 1;
    }

    int count() const { return _count; }
    Person* next() const { return _next; }
    Person* prev() const { return _prev; }

    void next(Person* person) { this->_next = person ; }
    void prev(Person* person) { this->_prev = person; }

   private:
     int _count;
     int _id;
     Person* _next;
     Person* _prev;
};

class Chain: public NonVirtualSlab<Chain> {
  public:
    Chain(const int id, const int size) : _first(NULL), _id(id) {
      Person* current = NULL;
      Person* last = NULL;

      for( int i = 0 ; i < size ; i++ )
      {
        current = new Person( id + i, i );

        if( _first == NULL )
          _first = current;

        if( last != NULL ) {
          last->next(current);
          current->prev(last);
        }

        last = current;
      }

      _first->prev(last);
      last->next(_first);
    }

    Person* kill( const int nth ) {
      Person* current = _first;
      int shout = 1;

      while( current->next() != current )
      {
        Person* tmp = current;

        shout = current->shout( shout,nth );
        current = current->next();

        if( shout == 1 )
          delete tmp;
      }

      _first = current;

      return current;
    }

    Person* first() const  { return _first; }

    ~Chain() { delete _first; }

  private:
      Person* _first;
      int _id;
};

int main( int argc, char* argv[] )
{
  const int ITER = 10000000;

  for( int i = 0 ; i < ITER ; ++i ) {
    Chain* chain = new Chain(i, 40);

    chain->kill(3);
    delete chain;
  }

  return 0;
}

Tempo total de execução com as mesmas opções do compilador: 7.67 segundos! Aproximadamente 9.4 vezes mais rápido! E a única modificação a ser feita no fonte são nas linhas 57 e 85, onde é acrescentado a herança para NonVirtualSlab<>.

Bom, para herança e métodos virtuais é necessário uma outra implementação. Em breve posto ela aqui.

“Is this the real life? Is this just fantasy?”