BLOG C++

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

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

Expressões Lambda

Para criarmos uma expressão que retorne um functor iremos usar templates. Para isso precisaremos redefinir todos os operadores – aritméticos, lógicos, relacionais etc. Por exemplo, para podermos escrever uma expressão “2*x + 1” precisamos redefinir “*” e “+”. No entanto, embora possamos redefinir “*” para Var e int, o operador “+” precisa ser redefinido para o functor retornado por “2*x” e int. Como a princípio a expressão do lado esquerdo pode ser qualquer coisa (a do lado direito também), não temos como saber a priori qual o seu tipo. Por outro lado, não podemos redefinir o operador “+” para tipos genéricos sob o risco de fazer parar de funcionar outras templates. Assim, precisamos distinguir o que é uma expressão lambda de outros tipos do programa. A melhor forma de fazer isso é criar uma template Lambda que apenas encapsula um functor qualquer, e redefine o operador “()” para um parâmetro qualquer. Pensando dessa forma, a própria variável x pode ser do tipo Lambda, sob a forma de especialização de templates. O tipo Lambda será então apenas um envelope para expressões/functores, repassando para a expressão/functor a tarefa de executar a operação desejada.

template <class Functor>
struct Lambda {
  const Functor f;

  Lambda( const Functor& f ): f(f) {}

  template <class T>
  T operator()( const T& x ) const { return f( x ); }
};

struct Var {
  template <class T>
  T operator()( const T& x ) const { return x; }
};

template <>
struct Lambda< Var > {
  Var f;

  template <class T>
  T operator()( const T& x ) const { return x; }
};

typedef Lambda< Var > ParamX;

ParamX x;

Assim podemos redefinir os operadores para atuarem apenas em tipos Lambda< T >.

Para podermos encadear os operadores devemos primeiro transformá-los em functores com uma interface única, de modo que a chamada a um operador possa ser capturada em uma template (a STL usa essa técnica). Para tanto, criaremos uma struct com uma template para uma função estática (que pode ser chamada sem um objeto) que recebe dois parâmetros e retorna a aplicação do operador a estes parâmetros.

struct Adicao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a + b; }
};

struct Multiplicacao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a * b; }
};

struct Subtracao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a - b; }
};

struct Divisao {
  template <class A, class B>
  static A aplica( A a, B b ) { return a / b; }
};

Dessa forma, com uma única template, que chamaremos de Oper, podemos encadear os operadores:

template <class O, class A, class B>
class Oper {
    private:
      const A a;
      const B b;

    public:
      Oper( const A& a, const B& b ): a(a), b(b) {}

      template <class T>
      T operator()( const T& x ) const { return O::aplica( a(x), b(x) ); }
};

Essa template possui dois campos, a e b, que são eles mesmos functores – e é exatamente isso que irá permitir que uma expressão seja representada por functores encadeados. Por exemplo, para representar x + x podemos escrever o seguinte código:

int main(int argc, char *argv[]) {
  Oper< Adicao, ParamX, ParamX > expr( x, x );

  cout << expr( 10 ) << endl;

  return EXIT_SUCCESS;
}

Esse código produz como saída 20. Mas o que queremos é poder realmente escrever x + x. Para tanto basta escrever uma template para o operador + com parâmetros Lambda< T >.

template <class A, class B>
inline Lambda< Oper< Adicao, A, B > > operator + ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Adicao, A, B  >( a.f, b.f );
}

template <class A, class B>
inline Lambda< Oper< Multiplicacao, A, B > > operator * ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Multiplicacao, A, B  >( a.f, b.f );
}

template <class A, class B>
inline Lambda< Oper< Subtracao, A, B > > operator - ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Subtracao, A, B  >( a.f, b.f );
}

template <class A, class B>
inline Lambda< Oper< Divisao, A, B > > operator / ( const Lambda<A>& a, const Lambda<B>& b ) {
  return Oper< Divisao, A, B  >( a.f, b.f );
}

Com isso podemos já escrever uma expressão mais complexa, como por exemplo x*x + x.

Para um mínimo de funcionalidade, precisamos lidar com constantes nas expressões lambda. Para tanto precisamos de uma classe que guarde o valor de uma constante de qualquer tipo e funcione como um functor para um parâmetro, retornando o valor dessa constante qualquer que seja o valor desse parâmetro. Além disso, precisamos de templates para os operadores lidarem com constantes e variáveis, para todos os operadores (abaixo fizemos apenas para “+”).

template <class C>
class Constante {
  private:
    const C n;

  public:
    Constante( const C& n ): n(n) {}

    template <class T>
    C operator()( const T& ) const { return n; }
};

template <class A, class B>
inline Lambda< Oper< Adicao, A, Constante<B> > > operator + ( const Lambda<A>& a, const B& b ) {
  return Oper< Adicao, A, Constante<B> >( a.f, b );
}

template <class A, class B>
inline Lambda< Oper< Adicao, Constante<B>, A > > operator + ( const A& a, const Lambda<B>& b ) {
  return Oper< Adicao, Constante<B>, A >( a, b.f );
}

Assim, já podemos escrever o seguinte código passando uma expressão lambda para uma função:

template <class Functor>
void imprime( int a, int b, Functor f ) {
  for( int i = a; i <= b; i++ )
    cout << f(i) << " ";

  cout << endl;
}

int main(int argc, char *argv[]) {
  imprime( 0, 10, x*x + x + 1 );

  return EXIT_SUCCESS;
}

Esse programa produz como saída o seguinte: 1 3 7 13 21 31 43 57 73 91 111

Na Parte 3 dessa série veremos como lidar com atribuições. Nesse link aqui você pode baixar o código completo desse post.

“I left alone my mind was blank/I needed time to think to get the memories from my mind”

Criando funções on-the-fly

Expressões lambda e cálculo lambda são abstrações muito utilizadas em teoria da computação. E são uma ótima forma de se definir funções on-the-fly, ou seja, no meio do código. Aqui vou mostrar uma pequena introdução sobre como fazer isso em C++, e em outros posts irei aperfeiçoar a idéia. Na biblioteca Boost existe uma boa implementação de expressões lambda, mas ela é pouco didática para se estudar. Melhor a gente ter uma idéia de como implementar primeiro e depois usar a biblioteca.

Um exemplo de uma expressão lambda é dado a seguir:

λxy.x+y
(λxy.x+y)( 2, 4 )

Na linha 1 está uma expressão que define uma função (sem nome e sem tipos) que recebe dois parâmetros x e y e retorna a soma deles. A idéia central aqui é função sem nome e sem tipos. Na linha 2 essa expressão é avaliada para os argumentos 2 e 4, do tipo int, retornando 6.

A principal utilidade de expressões lambda é para substituir functores nas funções da STL, por exemplo for_each, permitindo que a função a ser passada como parâmetro seja definida on-the-fly. As vantagens desse tipo de definição são duas: a definição da função fica perto do seu uso, e desempenho, pois tudo é expandido inline.

Para se criar expressões lambda em C++ podemos fazer algumas simplificações. A primeira delas é abolir a letra λ e a segunda é fixar os nomes dos parâmetros. Nessa primeira parte do post, irei criar apenas expressões lambda de um parâmetro, que se chamará x. Além disso, as expressões lambda não terão tipo – o que nos indica que serão templates. Uma expressão lambda “x + 1″ deve retornar um functor que soma 1 ao argumento passado na chamada dele. Assim, (x + 1)( 10 ) deve retornar 11. O código a seguir ilustra onde queremos chegar.

#include <iostream>
#include <vector>
#include <lambda>

using namespace std;

struct Imprime {
  ostream& o;

  Imprime( ostream& o ): o(o) {}

  template <class T>
  void operator () ( T n ) {
    o << n << " ";
  }
};

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

  a.push_back( 1 );
  a.push_back( 2 );
  a.push_back( 3 );
  a.push_back( 4 );
  a.push_back( 5 );

  for_each( a.begin(), a.end(), x = x*x+1 );

  for_each( a.begin(), a.end(), Imprime( cout ) );
}

Saída:

2 5 10 17 26

A expressão “x = x*x+1” retornou um functor que calcula esse valor, e ele foi passado como parâmetro para a função for_each, produzindo o efeito desejado nos elementos do vetor. O functor Imprime na verdade não está ali por acaso: ele servirá de idéia base para a construção de expressões lambda. Seu operador de chamada de função é uma template, e pode ser utilizado para qualquer tipo que possa ser passado para um ostream através do operador “<<”. Ou seja, ele é um functor que encapsula a expressão cout << x << ” “.

Se fizermos um operador “<<” para ostream e um tipo novo para representar x (Var por exemplo) e se esse operador ao invés de imprimir retornar um objeto do tipo Imprime, poderemos criar uma expressão lambda.

Primeira Expressão Lambda:

#include <iostream>
#include <vector>
#include <lambda>

using namespace std;

struct Imprime {
  ostream& o;

  Imprime( ostream& o ): o(o) {}

  template <class T>
  void operator () ( T n ) {
    o << n << " ";
  }
};

struct Var {};
Var x;

Imprime operator << ( ostream& o, Var ) {
  return Imprime( o );
}

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

  a.push_back( 1 );
  a.push_back( 2 );
  a.push_back( 3 );
  a.push_back( 4 );
  a.push_back( 5 );

  for_each( a.begin(), a.end(), x = x*x+1 );

  for_each( a.begin(), a.end(), cout << x );
}

É essa a idéia central: representar através de functores sem tipo as operações que compõem uma expressão lambda. A expressão é montada através de operadores
redefinidos, conforme podemos ver nas linhas 21 e 36.

No próximo post, mostro como encadear as expressões.

“Se a experiência funcionou na primeira tentativa, tem algo errado.”

Adiando a definição de uma template interna a uma classe template

Às vezes devido às dependências do código precisamos adiar a definição de uma template até um determinado ponto do programa fonte – por exemplo se no código dessa template for necessário uma declaração feita mais a frente. Outro motivo seria simplesmente manter a declaração da classe pequena, deixando a definição em outra parte do código – sem contar que qualquer declaração dentro de uma classe será automaticamente considerada inline sempre que possível.

A sintaxe para isto é estranha. Veja os trechos de código a seguir.

Declaração:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

template <class T>
class Estado {
  private:
    string nome;
    T t;

  public:
    Estado( string nome );

    template <class U> class Municipio {
      private:
        string nome;

      public:
        Municipio( string nome );

        int praias();

        template <class V> void hotel( V v );
    };

    template <class W> void cobertura( W w );

};

A classe Estado é uma template com um construtor e um método template (cobertura), e a classe Municipio é uma template interna à classe Estado, e possui um método comum (praias) e um outro método template (hotel). O método hotel depende de três parâmetros template: T, U e V.

Não há mistério na definição fora da classe do construtor Estado. A coisa começa a ficar estranha para o método cobertura, pois este precisa de dois parâmetros.

template <class T>
Estado<T>::Estado( string nome ): nome(nome), t(0) {
  // Um código qualquer aqui
}

template <class T, class W>
void Estado<T>::cobertura( W w ) {
  t = w;
  // Um código qualquer aqui
}

A saída para esta compilação é:

38 main.cpp: prototype for `void Estado<T>::cobertura(W)' does not match any in class `Estado<T>'
38 main.cpp: template<class T> template<class W> void Estado::cobertura(W)
38 main.cpp: template definition of non-template `void Estado<T>::cobertura(W)'
[Build Error] [main.o] Error 1

A linha 2  já nos indica qual a solução: template <class T> template<class W>

A sintaxe para a declaração de templates aninhadas é essa. Com qualquer nível de aninhamento. Assim, o código final para a declaração das templates externamente à classe é mostrado a seguir.

Código final:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

template <class T>
class Estado {
  private:
    string nome;
    T t;

  public:
    Estado( string nome );

    template <class U> class Municipio {
      private:
        string nome;

      public:
        Municipio( string nome );

        int praias();

        template <class V> void hotel( V v );
    };

    template <class W> void cobertura( W w );

};

template <class T>
Estado<T>::Estado( string nome ): nome(nome), t(0) {
  // Um código qualquer aqui
}

template <class T> template <class W>
void Estado<T>::cobertura( W w ) {
  t = w;
  // Um código qualquer aqui
}

template <class T> template <class U>
Estado<T>::Municipio<U>::Municipio( string nome ): nome(nome) {
  // Um código qualquer aqui
}

template <class T> template <class U>
int Estado<T>::Municipio<U>::praias() {
  // Um código qualquer aqui
  return 0;
}

template <class T> template <class U> template <class V>
inline void Estado<T>::Municipio<U>::hotel( V v ) {
  // Um código qualquer aqui
}

int main(int argc, char *argv[])
{
  Estado<int> rio("Rio de Janeiro");
  Estado<int>::Municipio<double> buzios("Búzios");

  rio.cobertura( 4 );
  buzios.hotel( 5 );
  cout << buzios.praias() << endl;

  return EXIT_SUCCESS;
}

Dessa forma, além de podermos contornar as possíveis dependências do código também podemos manter a declaração de uma classe template enxuta – sem comprometer o desempenho, pois nada impede que usemos a opção inline (linha 55).

“All the world’s a stage…”