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?”