Concepts e templates condicionais

Concepts

O comitê de padronização do C++ox decidiu excluir concepts da proposta de evolução corrente da linguagem. Dessa forma uma importante ferramenta foi deixada de lado.

Na proposta discutida, concepts seria uma forma de garantir que determinado parâmetro de uma template implementa métodos específicos (obedecendo a um padrão) ou possui determinados tipos. Enfim, uma forma de garantir que uma template só irá ser instanciada se o tipo passado possuir certas características. Suponha que uma template necessite de um parâmetro tipo que possua o método mm. Atualmente, como não é possível especificar um concept, o compilador irá dar um erro de compilação durante a instanciação da template reclamando da falta do método mm. O problema é que uma template repassa seus parâmetros e instancia outra que instancia outra e assim por diante, de modo que a mensagem de erro costuma não ser muito clara, e possivelmente em uma template bem distante da original…

Um outro problema relacionado é quando queremos redefinir uma operação para um grupo de classes que não são da mesma hierarquia mas possuem métodos semelhantes – na STL, os containers, por exemplo, possuem sempre os métodos begin() e end() retornando iteradores. Se quisermos redefinir “operator <<” para imprimir um container teremos de fazer um operador para cada um dos tipos: vector, map, list etc. Uma forma mais simples de se fazer isso seria especificando um concept exigindo que os iteradores estejam presentes em uma template mais genérica.

Exemplo

#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <class A, class B>
ostream& operator << ( ostream& o, const pair<A,B>& n ) {
  return o << "(" << n.first << ", " << n.second << ")";
}

template <class T>
ostream& operator << ( ostream& o, const vector<T>& v ) {
  o << "[ ";
  for( typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

template <class K, class T>
ostream& operator << ( ostream& o, const map<K,T>& m ) {
  o << "[ ";
  for( typename map<K,T>::const_iterator i = m.begin(); i != m.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

int main(int argc, char *argv[])
{
  vector<int> v;
  map<int, string> m;

  v.push_back( 0 );
  v.push_back( 1 );
  v.push_back( 2 );

  m[0] = "zero";
  m[1] = "um";
  m[2] = "dois";

  cout << v << endl << m << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Na linha 8 criamos uma template para imprimir o tipo pair<A,B> redefinindo o operador “<<”. Nas linhas 13 e 21 fizemos o mesmo para imprimir vector<T> e map<K,T>. O código acima produz a seguinte saída:

[ 0 1 2 ]
[ (0, zero) (1, um) (2, dois) ]
Pressione qualquer tecla para continuar. . .

Simulando concepts

Podemos simular o uso de um concept. Para tanto, basta entendermos como funciona o compilador na hora de instanciar uma template. Em um primeiro momento, o compilador procura casar os parâmetros passados para a template com as templates candidatas. Há regras para desambiguidade se mais de uma casar, e o compilador só dará uma mensagem de erro se não for possível escolher uma.

Se uma template casa, mas dentro de seu código ela usa algo (um método ou um tipo) que não está definido para o tipo usado na instanciação será gerado um erro de compilação dizendo “mm não definido para tipo T”. Por outro lado, se um cabeçalho de uma template exigir algo do parâmetro que ele não tenha não será gerado um erro: apenas essa template não casará. O nome desse comportamento do compilador é “Substitution Failure Is Not An Error” ou simplesmente SFINAE (grato, Felipe Magno de Almeida).

Portanto, podemos exigir no cabeçalho de uma template que um determinado método (ou tipo) esteja presente para que a template case. As técnicas para fazer isso são um pouco confusas, mas vamos lá. No exemplo anterior gostaríamos de definir uma única template para o operador “<<”  que sirva para qualquer classe que tenha suporte a iteradores. Aqui o pulo do gato: templates de classes e estruturas permitem o uso de parâmetros default (templates de funções não!). Basta portanto criarmos um parâmetro default (que não será nunca usado) e que dependa da existência de um tipo ou método (nesse caso devemos tomar o endereço do método). Por exemplo, podemos criar uma template que só será instanciada se o tipo passado possuir o tipo interno “const_iterator” (todos os containers têm esse tipo interno):

template <class V, class Ok = typename V::const_iterator>
struct CheckItr {};

CheckItr< vector<int> > teste1;
CheckItr< int > teste2;

No código acima, a template CheckItr recebe um parâmetro V e um parâmetro Ok cujo default é V::const_iterator. Se quisermos fazer a verificação, esse parâmetro deve ser sempre preenchido automaticamente, ou seja, não devemos fornecer um tipo para ele. Dessa forma, a linha 4 do exemplo acima irá compilar normalmente instanciando “CheckItr< vector<int>, vector<int>::const_iterator >” ao passo que a linha 5 irá dar um erro de compilação pois int não possui o tipo const_iterator definido internamente – int nem é classe!

Agora a solução do exemplo: o operador “<<” é redefinido o tempo todo para “ostream&” e algum outro tipo. Se criarmos uma template genérica como abaixo teremos um grande problema de ambiguidade:

template <class T>
ostream& operator << ( ostream& o, const T& v );

Mas nós podemos exigir que o parâmetro T da template acima seja capaz de instanciar CheckItr – note que se ele não for capaz de instanciar o compilador irá apenas instanciar ou procurar outro operador “<<”. Dessa forma resolveríamos o problema de ter apenas uma template para todos os tipos que implementam iteradores. Mas como fazer isso? Se fosse uma função, seria simples, pois novamente poderíamos colocar um parâmetro default (parâmetro da função , não da template… template para funções não permitem parâmetros default). Veja:

template <class T>
void imprime( const T& v, CheckItr<T>* p = NULL ) {
  for( typename T::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
}

Se a função imprime for chamada passando-se um vector, map, list ou qualquer outro objeto cuja classe defina const_iterator não haverá problema, ela será instanciada (novamente não se deve passar o parâmetro default). Se o tipo passado não possuir const_iterator, o compilador irá tentar casar com outra função imprime – se não conseguir, aí sim será gerado um erro de compilação. Infelizmente, não podemos definir parâmetros default para o operador “<<”, de modo que teremos de adotar uma outra estratégia para contornar essa limitação. A solução sugerida é colocar a verificação no parâmetro ostream&. Para tanto, definimos em CheckItr um tipo interno “ostream“, e o usamos no cabeçalho do operador “<<”. Segue:

template <class V, class Ok = typename V::const_iterator >
struct CheckItr {
  typedef ::ostream ostream;
};

template <class T>
ostream& operator << ( typename CheckItr<T>::ostream& o, const T& v ) {
  o << "[ ";
  for( typename T::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

Assim essa template somente será instanciada se o parâmetro T puder instanciar CheckItr. Se isso ocorrer, o tipo CheckItr<T>::ostream existe, e a template casou. Ou seja, somente se T possui const_iterator definido que essa template para o operador “<<” será utilizada.

Segue o exemplo completo:

#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <class V, class Ok = typename V::const_iterator >
struct CheckItr {
  typedef ::ostream ostream;
};

template <class A, class B>
ostream& operator << ( ostream& o, const pair<A,B>& n ) {
  return o << "(" << n.first << ", " << n.second << ")";
}

template <class T>
ostream& operator << ( typename CheckItr<T>::ostream& o, const T& v ) {
  o << "[ ";
  for( typename T::const_iterator i = v.begin(); i != v.end(); ++i )
    cout << *i << " ";
  return o << "]";
}

int main(int argc, char *argv[])
{
  vector<int> v;
  map<int, string> m;

  v.push_back( 0 );
  v.push_back( 1 );
  v.push_back( 2 );

  m[0] = "zero";
  m[1] = "um";
  m[2] = "dois";

  cout << v << endl << m << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Dessa forma a template acima atenderá todos os containers da STL e também qualquer classe que tenha definido o tipo const_iterator. Espera-se que se uma classe define const_iterator ela defina também begin() e end() - não fizemos isso no exemplo, mas isso pode ser verificado em CheckItr<T>.  Para verificar se um tipo possui um método a maneira mais simples é obter o endereço desse método usando o operador “&”. O retorno desse operador é uma constante, de modo que pode ser usado como parâmetro de uma template.

template <class V, typename V::const_iterator (V::*begin)() const = &V::begin,
                   typename V::const_iterator (V::*end)() const = &V::end >
struct CheckItr {
  typedef ::ostream ostream;
};

A verificação acima já checa se existe o tipo const_iterator por causa do valor de retorno de begin() e end(). Note que tomamos o cuidado de especificar uma variável ponteiro para membro constante de V, pois begin() é um método sobrecarregado e nesses casos o C++ exige informação de contexto.

“You shall not pass!”

Bookmark and Share

typenames e templates

Manipulação de tipos em C++

Há uma certa dificuldade para os programadores iniciantes na área de templates que se aventuram a manipular tipos. A primeira delas é quanto ao uso da palavra reservada typename. Essa palavra deve ser utilizada para informar ao compilador que o nome que vem em seguida é um tipo, e não um membro de uma estrutura ou uma variável. No código abaixo podemos ver isso. Esse é um exemplo onde criamos uma função que recebe um vetor e calcula a soma dos elementos desse vetor.

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

template <class V>
V soma( const vector<V>& v ) {
  V aux = 0;

  for( typename vector<V>::const_iterator i = v.begin(); i != v.end(); ++i )
    aux += *i;

  return aux;
}

int main(int argc, char *argv[])
{
  vector<double> v;

  v.push_back( 1.1 );
  v.push_back( 2.1 );
  v.push_back( 3.1 );

  cout << soma( v ) << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Sem a palavra typename na linha 11 temos as seguintes mensagens de erro:

main.cpp: In function `V soma(const std::vector<V, std::allocator<_CharT> >&)':
main.cpp:11: error: expected `;' before "i"
main.cpp:11: error: `i' undeclared (first use this function)
main.cpp:11: error: (Each undeclared identifier is reported only once for each function it appears in.)
main.cpp: In function `V soma(const std::vector<V, std::allocator<_CharT> >&) [with V = double]':
main.cpp:25:   instantiated from here
main.cpp:11: error: dependent-name ` std::vector<V,std::allocator<_CharT> >::const_iterator' is parsed as a non-type, but instantiation yields a type
main.cpp:11: note: say `typename  std::vector<V,std::allocator<_CharT> >::const_iterator' if a type is meant

Ocorre que o compilador assume que const_iterator é um nome de um membro (variável ou método) da classe vector<V>, e não um nome de tipo (nesse caso específico, um tipo definido através de um typedef). De uma forma geral, toda expressão envolvendo um parâmetro da template (no exemplo, o V) onde ocorre acesso à um campo de uma estrutura (uso do “::”) será encarado pelo compilador não como um tipo mas sim como um membro dessa estrutura. Se quisermos que o compilador veja ali um tipo devemos preceder a declaração com a palavra reservada typename. Pelo menos o compilador nos dá uma boa dica do problema na mensagem de erro nº 8:  ”note: say `typename  std::vector<V,std::allocator<_CharT> >::const_iterator’ if a type is meant“.

Note que no fonte, na linha 9 temos a declaração da variável aux sem a necessidade do typename, pois nesse caso o compilador assume que V é um tipo.

Lidando com tipos internos

Porém há situações onde alguns tipos são informados como typedefs internos à uma estrutura (classe). É o caso de todos os containers da stl, que possuem o tipo value_type definido como o tipo do objeto que o container armazena. Essa informação é útil para a construção de rotinas mais genéricas, onde não se sabe o tipo do container. A função soma do exemplo acima lida apenas com vectors.  Mas ela pode ser redefinida para lidar com qualquer classe container (ou compatível) da seguinte forma: ao invés de receber o parâmetro const vector<V>& v ela passa a receber const V& v. O problema é que nesse caso não sabemos o tipo do elemento armazenado no container. É para isso que serve o tipo value_type. E aí, dessa vez precisaremos usar typename antes de V::value_type.

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

template <class V>
typename V::value_type soma( const V& v ) {
  typename V::value_type aux = 0;

  for( typename V::const_iterator i = v.begin(); i != v.end(); ++i )
    aux += *i;

  return aux;
}

int main(int argc, char *argv[])
{
  vector<double> v;

  v.push_back( 1.1 );
  v.push_back( 2.1 );
  v.push_back( 3.1 );

  cout << soma( v ) << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Na linha 8 temos o tipo de retorno da função: V::value_type, devidamente precedido por typename para informar ao compilador que se trata de um tipo (de modo análogo na linha 9 temos a declaração da variável aux).

“Hasta la vista, baby!”

Bookmark and Share

Namespaces: colocando cada coisa em seu lugar

Evitando conflitos de nomes

namespace é uma palavra reservada do C++ que implementa um mecanismo capaz de expressar agrupamento lógico. Em outras palavras, se um conjunto de declarações estão logicamente associadas de acordo com algum critério, elas podem ser colocadas juntas no mesmo namespace para expressar este fato. Um namespace também pode ser chamado de um contexto. O uso de namespaces, além de proporcionar agrupamento lógico,  serve para evitar o conflito de nomes: dois identificadores podem ter o mesmo nome se estiverem em namespaces diferentes. Como é um mecanismo que define escopo, o nome de um identificador fora de seu namespace deve ter o nome do namespace na frente, seguido do operador de escopo “::”.  Namespaces também afetam o mecanismo de mangling que o C++ usa.

A sintaxe para namespace é bem intuitiva, semelhante à de uma classe. No entanto, um namespace define apenas escopo, e não um tipo em si. Funções declaradas dentro de um namespace não são métodos, são apenas funções.

Exemplo:

#include <cstdlib>
#include <iostream>

namespace Teste {
  void escreveMensagem() {
    std::cout << "Uma mensagem qualquer!" << std::endl;
  }
}

int main(int argc, char *argv[])
{
  Teste::escreveMensagem();

  system("PAUSE");
  return EXIT_SUCCESS;
}

No exemplo acima, declaramos um namespace Teste e dentro deste, a função escreveMensagem(). Note na linha 6 o uso de identificadores declarados em outro namespace: std::cout e std::endl. cout e endl são variáveis declaradas dentro do namespace std. O uso de um identificador com o seu namespace é chamado de nome qualificado ou completo.

Usando Namespaces

Em um determinado ponto pode se tornar tedioso ter de repetir o nome do namespace sempre que se quer utilizar um determinado identificador de um outro namespace. Para estas situações existem duas abordagens previstas no C++.

1) using namespace std;

Essa construção, chamada de global using-directive, é mais geral pois importa todos os identificadores do namespace std, e por isso deve ser utilizada com bastante parcimônia: tem como consequência justamente anular o mecanismo de separação de escopos proposto pelo namespace.

Há autores inclusive que defendem que seu uso deve ser limitado apenas a código herdado, ou seja, sistemas e bibliotecas antigos, escritos antes da introdução desse mecanismo em C++. Não sou tão radical, para pequenos programas acho essa sintaxe bastante conveniente. Deve ser porque programo em C++ desde 1989, quando não havia namespaces (nem templates, nem exceções, nem herança múltipla… é, pode me chamar de velho! :) ). Para sistemas grandes porém, é melhor realmente não utilizar essa opção. Em seu livro “The C++ Programming Language” Bjarne Stroustrup recomenda o seguinte (tradução livre): “Diretivas globais de using são uma ferramenta de transição e de outra forma devem ser evitadas. Em um namespace, a diretiva using é uma ferramenta para a composição de namespaces.  Em uma função (somente), uma diretiva using pode ser seguramente utilizada como uma conveniência notacional”.

2) using std::cout;

Essa construção importa apenas o identificador cout, sendo bem mais seletiva. Nesse caso o identificador endl não foi importado, sendo necessário para o seu uso o nome completo: std::endl.

Cabe dizer que uma diretiva using (global ou não) pode ser colocada nos seguintes  escopos: global, dentro de um namespace, dentro de uma função, dentro um método ou mesmo dentro de um bloco. Não é permitido colocar using diretamente dentro de uma classe ou estrutura. Esse posicionamento por si só define o escopo da importação em questão. Via de regra, deve-se utilizar o menor escopo possível, pesando-se sempre a conveniência da notação com a violação da separação de escopos.

Boas práticas

Um namespace não precisa declarar tudo o que será utilizado de uma só vez, e embora seja confuso ter mais de uma declaração com o mesmo namespace isso é permitido (porém desaconselhável). No entanto, é razoável ter em um lugar (um arquivo “.h”, por exemplo) apenas as declarações e em outro lugar a implementação propriamente dita. Há duas formas de se fazer isso, ilustradas a seguir. A primeira faz uma extensão na declaração do namespace, a segunda usa o nome qualificado do identificador sendo definido. Particularmente acho perigosa a primeira opção, prefiro a segunda.

Dividindo namespaces

#include <cstdlib>
#include <iostream>

namespace Teste {
  void escreveMensagem();
}

int main(int argc, char *argv[])
{
  Teste::escreveMensagem();

  system("PAUSE");
  return EXIT_SUCCESS;
}

// em qualquer outro lugar ou arquivo!!

namespace Teste {
  void escreveMensagem() {
    using namespace std;

    cout << "Uma mensagem qualquer!" << endl;
  }
}

Implementação usando nomes qualificados

#include <cstdlib>
#include <iostream>

namespace Teste {
  void escreveMensagem();
}

int main(int argc, char *argv[])
{
  Teste::escreveMensagem();

  system("PAUSE");
  return EXIT_SUCCESS;
}

// Em qualquer outro lugar ou arquivo!!

void Teste::escreveMensagem() {
  using std::cout;
  using std::endl;

  cout << "Uma mensagem qualquer!" << endl;
}

Um namespace pode conter outros namespaces. Nesse caso teremos um namespace aninhado a outro namespace. O conceito é o mesmo de aninhamento de blocos ou aninhamento de classes. Inclusive, se o namespace A contém o namespace B que por sua vez contém o identificador X, o nome qualificado de X é A::B::X. Por outro lado, um namespace somente pode ser declarado no escopo global ou dentro de outro namespace. Não é permitido que um namespace seja declarado dentro de uma função, classe ou método.

Podemos também definir aliases para namespaces. O escopo é semelhante ao de uma declaração using: global, dentro de funções, métodos ou blocos. Um alias é uma forma conveniente de dar outro nome a um namespace. A vantagem é poder trocar rapidamente um pacote de uma biblioteca por outro (desde que as interfaces sejam compatíveis, lógico). A sintaxe é:

void foo() {
  namespace NovoNome = std;

  NovoNome::cout << "Uma mensagem" << NovoNome::endl;
}

Por último, por mais estranho que pareça, é permitido declarar um namespace sem nome. Nesse caso o compilador cria um nome temporário, que não pode ser acessado de nenhum outro lugar a não ser a unidade sendo compilada – esta inclusive pode acessar livremente qualquer identificador dentro desse namespace. Ou seja, funciona como uma restrição de escopo no estilo static functions.

“In my place, in my place / Were lines that I couldn’t change

Bookmark and Share

O mistério do sizeof – parte 3

Código Fonte:

#include <cstdlib>
#include <iostream>

using namespace std;

struct A {
  void funcaoA() {}
};

struct B {
  void funcaoB() {}
};

struct C {
  void funcaoC() {}
};

struct ABC1 {
  A a;
  B b;
  C c;
};

struct ABC2: public A, public B, public C {
};

int main(int argc, char *argv[])
{
  cout << "sizeof( A ): " << sizeof( A ) << endl;
  cout << "sizeof( B ): " << sizeof( B ) << endl;
  cout << "sizeof( C ): " << sizeof( C ) << endl;
  cout << "---" << endl;
  cout << "sizeof( ABC1 ): " << sizeof( ABC1 ) << endl;
  cout << "sizeof( ABC2 ): " << sizeof( ABC2 ) << endl;

  ABC1 x;
  ABC2 y;

  x.a.funcaoA();
  y.A::funcaoA();

  system("PAUSE");
  return EXIT_SUCCESS;
}

Saída:

sizeof( A ): 1
sizeof( B ): 1
sizeof( C ): 1
---
sizeof( ABC1 ): 3
sizeof( ABC2 ): 1
Pressione qualquer tecla para continuar. . .

Como vimos neste outro post, mesmo que uma classe ou estrutura não contenha atributos ela deve ocupar pelo menos um byte. Normalmente, classes sem atributos são para declarar ou implementar interfaces,ou para o reaproveitamento organizado de código. Uma outra utilidade é na composição de templates, em particular para o caso de expressões lambda. (link).

Qualquer que seja a situação, se uma classe possui um campo que é uma classe vazia (sem atributos), esse campo terá de ocupar pelo menos um byte. Com a composição de templates no caso das expressões lambda podemos chegar a ter uma composição de classes vazias ocupando uma grande quantidade de bytes no final.

Esse exemplo acima ilustra uma possibilidade de reduzirmos ou eliminarmos a quantidade de espaços vazios alocados inutilmente para este tipo de classe.  A classe ABC1 ocupou 3 bytes, enquanto a classe ABC2 ocupou apenas um byte. Semanticamente não é a mesma coisa, porém para o caso de templates normalmente isso não fará diferença pois estaremos mais interessados no código dos métodos do que em outra coisa.

Essa abordagem no entanto apresenta algumas dificuldades, na medida em que utiliza herança múltipla. Por exemplo, se as classes possuírem métodos virtuais não haverá nenhum ganho de espaço devido às VMTs.

Além disso, a sintaxe muda um pouco na hora de chamar os métodos como podemos observar na linha 40.

“So this is Christmas/And what have you done/Another year over/And a new one just begun.”

Bookmark and Share

Gerência de memória lenta em C++? Redefinido os operadores new e delete

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

Bookmark and Share