BLOG C++

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

Soluções simples quase sempre são as melhores

Outro dia estava com um problema onde precisa de um map que pudesse ser indexado por mais de um tipo de dado diferente. Chamei isso de map heterogêneo.

Pra quem não sabe, a template map da stl recebe dois tipos de dados e faz um dicionário. A hash_map faz a mesma coisa, porém mais rápido – mas o meu principal problema não era velocidade.

Exemplo de uso da map em C++

#include <iostream>
#include <map>

using namespace std;

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

  dic["abacate"] = 3;
  dic["maçã"] = 2;

  cout << dic["abacate"] << endl;
  cout << dic["maçã"] << endl;
  cout << dic["banana"] << endl;

  return 0;
}

(Gostei dessa formatação acima!)

O caso é que o tipo do índice do map tem de ser um só, e eu queria misturar int, double, char* e string. Lógico que poderia usar quatro maps diferentes, mas isso significaria passar quatro parâmetros a mais para várias funções. Antes de partir pra fazer uma classe com quatro maps diferentes (ou mais, veio logo essa dúvida!) e sobrecarregar o operador [], me ocorreu a seguinte idéia: e se um campo membro da classe pudesse ser template? Bom, isso não funciona – apenas métodos podem ser templates. Mas consegui um workaround que, se não é a coisa mais linda nem eficiente do mundo, resolveu bem o problema com um mínimo de esforço.

Um método pode ser template, e um método pode ter uma variável local do tipo do parâmetro da template. O problema é que uma variável local morre quando se sai do método. Mas e se essa variável fosse estática? Nesse caso surgiria outro problema – teria apenas uma instância da variável para todos os objetos da classe. O código abaixo ilustra isso.

Versão 0.1 da solução para map heterogêneo

#include <iostream>
#include <map>

using namespace std;

template <class T>
struct Map {
  template <class I>
  int& operator [] ( I i ) {
    static map<I,int> m;

    return m[i];
  }
};

int main(int argc, char *argv[])
{
  Map<int> dic, outroDic;

  dic["abacate"] = 3;
  dic["maçã"] = 2;
  dic[0] = 1;
  dic[0.0] = 5;

  cout << dic["abacate"] << endl;
  cout << outroDic["maçã"] << endl;
  cout << dic["banana"] << endl;
  cout << dic[0] << endl;
  cout << dic[0.0] << endl;

  return 0;
}

Saída:

3
2
0
1
5

Na linha 26, embora esteja usando a variável outroDic, o resultado não foi zero: as duas variáveis, dic e outroDic, copartilham o mesmo map, pois ele é estático. Daí veio a seguinte idéia: e se tivesse um map para o próprio objeto, ou seja, this? Bingo! resolvido o problema (já disse, é apenas uma solução simples – para ser eficiente teria de usar hash_map, e para ser elegante… bem, aí é outra estória…).

Versão 0.2 da solução para map heterogêneo

#include <iostream>
#include <map>

using namespace std;

template <class T>
struct Map {
  template <class I>
  int& operator [] ( I i ) {
    static map<Map*, map<I,int> > m;

    return m[this][i];
  }
};

int main(int argc, char *argv[])
{
  Map<int> dic, outroDic;

  dic["abacate"] = 3;
  dic["maçã"] = 2;
  dic[0] = 1;
  dic[0.0] = 5;

  cout << dic["abacate"] << endl;
  cout << outroDic["maçã"] << endl;
  cout << dic["banana"] << endl;
  cout << dic[0] << endl;
  cout << dic[0.0] << endl;

  return 0;
}

Saída:

3
0
0
1
5

Dessa vez a linha 26 corretamente produziu zero como saída, pois o dado foi armazenado associado ao ponteiro this, ou seja, ao próprio objeto. O que me deixou surpreso e satisfeito foi realmente a simplicidade da solução – apenas 6 linhas de código. E muito fácil de adaptar para hash_map para não ficar tão ineficiente…

Resolvi o meu problema imediato. Mas é a versão 0.2 ainda porque não tem iteradores… não parei ainda para pensar em uma forma de fazer um iterador único para cada variável, na verdade me ocorreu que somente seria possível ter um iterador para cada tipo de índice por causa do campo first. Uma pena… mas pelo menos para o meu problema o código acima já serve.

E para quem for mais atento, falta um destrutor para remover da variável estática m (linha 10) os Maps locais quando eles forem destruídos… é, talvez versão 0.2–

“Veni, vidi, vici”

Esse é o verdadeiro Fibonacci em C++…

Lógico que no post anterior sobre o desempenho do Java o objetivo não era calcular Fibonacci, mas mostrar que em chamadas recursivas o otimizador do Java leva a melhor. Uma implementação de Fibonacci em C++ usando este algoritmo recursivo,  sem passar para outros algoritmos mais óbvios como manter os dois últimos valores ou somar em um vetor, deve usar uma característica funcional da linguagem C++: a metaprogramação.

Este é o primeiro  post sobre metaprogramação que faço, mas é o exemplo clássico, muito simples e que causa um impacto enorme…

#include <iostream>;

using namespace std;

template<int n>
struct Fib {
  enum X { value = Fib<n-1>::value + Fib<n-2>::value };
};
template <>
struct Fib<1> {
  enum X { value = 1 };
};

template <>
struct Fib<0> {
  enum X { value = 0 };
};

int main(int argc, char *argv[]) {
  cout << Fib<45>::value << endl;
  return 0;
}

Tempo de execução: 0.01 segundo!

Às vezes 0.00 segundo (o sistema não conseguiu medir…). E o tempo de compilação foi normal, 0.58 segundos. Bom, esse programa não é genérico o suficiente para calcular para n, apenas para uma constante conhecida a tempo de compilação. Mas é um recurso do C++, e a gente programa em C++ para usar todos os recursos que a linguagem oferece.  É rápido por que é calculado em tempo de compilação. Não torna a compilação mais lenta pois o compilador instancia Fib<x> apenas uma vez e reaproveita o valor nas vezes seguintes.

Mas também é possível fazer um Fibonacci recursivo para qualquer n mesmo que ele não seja conhecido durante a compilação.

using namespace std;

template <int n>
struct FIB {
  enum X { value = FIB<n-1>::value + FIB<n-2>::value };

  static int generico( int k ) {
    return k > n ? FIB<n>::generico( k-1 ) + FIB<n>::generico( k-2 ) : especifico( k );
  }

  static int especifico( int k ) {
    return k == n ? value : FIB<n-1>::especifico( k );
  }
};

template <>
struct FIB<0> {
  enum X { value = 0 };

  static int especifico( int k ) { return 0; }
};

template <>
struct FIB<1> {
  enum X { value = 1 };

  static int especifico( int k ) {return k == 1 ? value : FIB<0>::especifico( k ); }
};

inline int fib( const int n ) {
  return FIB<15>::generico( n );
}

int main(int argc, char *argv[])
{
  cout << fib( 45 ) << endl;
  return 0;
}

No exemplo acima o tempo de execução foi de 0.03 segundo. O pulo do gato é o 15 na função fib. Ele instancia a série para os 15 primeiros elementos. Detalhe que esse número é configurável durante a compilação somente. Mas de qualquer forma o programa funciona usando o mesmo algoritmo original – só que muito mais rápido.

Foi uma mistura de metaprogramação com programação. Uma possibilidade do C++, que a gente usa de acordo com o problema em questão…

“Nunca diga nunca!”

Pois é… o temido dia chegou!

Em algum momento isso ia acontecer… ia aparecer algum código Java específico que rodasse mais rápido que o equivalente em C++. E não adianta nada, nem escovar bits, nem reza braba, nem compilador Intel… esse código aí embaixo roda bem mais rápido em Java!!!!

Código Fonte Java:

public class Teste {

  static int fib( int n ) {
    return n > 1 ? fib(n-1)+fib(n-2) : n;
  }

  public static void main(String[] args) {
    System.out.println(fib(45));
  }
}

Código Fonte C++:

#include <iostream>

using namespace std;

inline int fib( int n ) {
  return n > 1 ? fib(n-1)+fib(n-2) : n;
}

int main(int argc, char *argv[]) {
  cout << fib(45) << endl;
  return 0;
}

Tempos:

Java (client): 14.74 segundos

Java (server): 10.17 segundos

C++  (g++ opção k8): 19.83 segundos

C++  (g++ opção core2): 14.39 segundos

C++ (Intel): 23.83 segundos

Note que dessa vez o compilador Intel perdeu pro g++… pros dois g++, 3.4 e 4.4. Mas todos perderam pro Java -server, e o g++ -core2 empatou com o Java -client. De alguma forma a chamada de funções estáticas no Java é mais otimizada… ou deve ter a ver com recursividade, passagem de parâmetros sei lá. Não entendo de bytecodes pra olhar o código gerado. Só sei que o C++ ficou cerca de 40% mais lento.

Enfim, é uma coisa a se investigar. Mas de qualquer forma, para Fibonacci e outras funçõe recursivas o C++ oferece metaprogramação… e aí… bem e aí o tempo cai pra 1.4 segundos. Mas isso é assunto de outro post.

“Though this be madness, yet there is method in ‘t. Will you walk out of the air, my lord?”

Deixemos as “religiões” de lado…

C++ é mais rápido que Java? É uma briga de foice… quase uma briga de torcida organizada! O defensores de ambas as linguagens estão armados até os dentes com os mais variados argumentos. O assunto suscita discussões apaixonadas e intermináveis, com acusações de ambos os lados de imparcialidade nos testes. É possível encontrar diversos benchmarks que fazem a vantagem pender para uma ou outra linguagem. Nesse aqui, por exemplo, o vencedor é o Java. Nesse outro, usando os mesmos testes os resultados são francamente favoráveis ao C++.

O que quero passar aqui é que essa pergunta praticamente não procede. Já vai longe o tempo em que Java era somente interpretado. Hoje existe o JIT, o que torna Java uma linguagem compilada. E comparar duas linguagens compiláveis significa comparar compiladores, mais especificamente, otimizadores de código. São poucas as construções que podem interferir no desempenho e que não podem ser otimizadas. A verdadeira discussão é sobre qual é o melhor otimizador.

E aí as notícias não são nada boas para os defensores do desempenho superior do C++. SUN e IBM derramaram milhões de dólares em suas máquinas virtuais, cuja parte mais importante é justamente o otimizador. O resultado foi surpreendente. As últimas JVMs da IBM e da SUN conseguem executar algunas exemplos de programas Java com desempenho superior aos compiladores C++ disponíveis, em particular o tão popular e querido g++. Em algumas situações específicas conseguem até superar o compilador Intel, reconhecidamente um dos compiladores mais otimizados do mercado.

Mas se agora a discussão é somente sobre qual é o melhor otimizador, faz sentido falar em C++ mais rápido que Java? A verdade é que sim, faz sentido. Java possui algumas características que tornam determinadas construções mais lentas do que as equivalentes em C++. Por outro lado, C++ não possui nenhuma característica que o torne obrigatoriamente mais lento que nenhuma linguagem – pelo contrário, inlines, templates e functores acabam tornando o código mais fácil de ser otimizado. Por outro lado, o abuso de ponteiros e aliases torna o trabalho do otimizador bem mais difícil – problema que o Java não possui.

Mas que características são essas que tornam o Java mais lento? Não são muitas. Mas a verificação de limites de índices de array é uma que realmente faz diferença. O Java, por definição da linguagem, não deve permitir acesso fora dos limites de um array. C++, ao contrário, estabelece claramente que nenhuma verificação é feita neste caso, ficando a cargo do programador garantir que nenhum acesso ilegal será feito. Essa é uma situação onde não há nenhum otimizador que dê jeito, pois os testes para verificar se os índices estão dentro dos limites do array têm de ser feitos em tempo de execução e consomem ciclos de CPU. O Java somente pode dispensar os testes de limites de array se o compilador puder deduzir que não haverá acesso fora dos limites.

Antes de sair por aí gritando “urra!” e “ahá! eu não disse?”, vamos analisar alguns pontos. Alguém pode argumentar que esses testes são necessários. De fato, muitas vezes o são, e o C++ possui tipos abstratos de dados que substituem arrays e fazem esse tipo de verificação em tempo de execução. Mas a questão não é essa. É que em C++ é possível usar ou não esse tipo de verificação, ao passo que em Java não se tem essa opção. Em C++ o programador pode decidir se quer ou não realizar testes de limites de array.

Me lembro da época em que programava em Pascal, onde enquanto se estava depurando o programa compilávamos com a opção “range check error” ligada, mas quando os testes indicavam que o programa estava ok, nós a desligávamos. Nesse ponto o Java trata todo programa como se estivesse em fase de testes – ou todo programador como irresponsável. Diferentemente do C++ onde podemos adotar a mesma estratégia que adotávamos em Pascal.

O Java precisa desse teste por uma questão de princípios: um dos objetivos iniciais da linguagem era a criação de applets, pequenos trechos de código que executam no browser. É necessário limitar a possibilidade dos applets causarem danos, de modo que podemos dizer que a JVM não confia no código que lhe é passado.

O preço que se paga por essa decisão podemos avaliar no exemplo abaixo, onde é mostrada uma multiplicação de matrizes 1000×1000 em Java. O código foi feito da maneira mais direta possível, na verdade fora a parte da inicialização os comandos são os mesmos em Java e em C++, tirados dos posts anteriores sobre otimização. Acho que ninguém pode questionar esse código, dizendo que ele favorece uma ou outra linguagem.

Código original sem nenhuma otimização:

public class Teste {

  static final int N = 1000;

  public static void main(String[] args) {
    double a[][] = new double[N][N],
           b[][] = new double[N][N],
           c[][] = new double[N][N];

    java.util.Random rn = new java.util.Random();

    for( int i = 0; i < N; i++ )
      for( int j = 0; j < N; j++ ) {
        a[i][j] = rn.nextInt()/(rn.nextInt()+0.1);
        b[i][j] = rn.nextInt()/(rn.nextInt()+0.1);
        c[i][j] = 0;
      }  

    for( int i = 0; i < N; i++ )
      for( int j = 0; j < N; j++ )
        for( int k = 0; k < N; k++ )
          c[i][j] += a[i][k] * b[k][j];
  }
}

Detalhes:

Esse código foi executado com duas variações de linha de comando:

java Teste
java -server -Xbatch Teste

A primeira roda no modo client, que não realiza muitas das otimizações do JIT e por isso é um pouco mais lenta. Já a segunda usa o modo server, o que se traduz em um maior consumo de memória e de tempo para inicialização, porém executa mais rápido (algumas vezes bem mais rápido!). No nosso teste os resultados estão no gráfico a seguir, mostrando também os resultados obtidos para o C++ nos posts anteriores.

Multiplicação de Matrizes

De cara vemos que o compilador Intel C++ é realmente insuperável… 44.48 x mais rápido que o código Java client. Mas mesmo comparando com o g++, vemos que o código C++ é 1.73x mais rápido que o Java client e 1,64x mais rápido que o Java server. Essa diferença pode ser creditada ao inúmeros testes de limites de array que o Java faz e que o C++ não: a cada acesso a um elemento de um array o Java irá verificar se o(s) índice(s) estão dentro dos limites. Embora que, analisando o programa fonte, ambas as linguagens fazem parte do teste quando comparam “i < N”, “j < N” e “k < N” em cada iteração dos comandos for, pois N é justamente o limite superior do array. Só o teste se i, j e k são maiores que zero (o limite inferior de cada array) é que o C++ não faz – mas esse teste é dispensável se a variável de índice for unsigned int. Ou seja, ainda há espaço para o otimizador do Java recuperar parte do tempo perdido.

Mas que tal se realizarmos as mesmas otimizações que fizemos nos posts anteriores? A primeira delas é inverter a ordem dos loops para tirar proveito da arquitetura do cache da CPU.

Código invertendo a ordem dos loops:

public class Teste {

  static final int N = 1000;

  public static void main(String[] args) {
    double a[][] = new double[N][N],
           b[][] = new double[N][N],
           c[][] = new double[N][N];

    java.util.Random rn = new java.util.Random();

    for( int i = 0; i < N; i++ )
      for( int j = 0; j < N; j++ ) {
        a[i][j] = rn.nextInt()/(rn.nextInt()+0.1);
        b[i][j] = rn.nextInt()/(rn.nextInt()+0.1);
        c[i][j] = 0;
      }  

    for( int i = 0; i < N; i++ )
      for( int k = 0; k < N; k++ )
        for( int j = 0; j < N; j++ )
          c[i][j] += a[i][k] * b[k][j];
  }
}

Ótimas notícias!!! Parece que agora o otimizador Java compreendeu que não precisa testar os limites do array. Usando o Java server o tempo praticamente se iguala ao g++: 2.77 segundos. Na verdade, 0.02 segundos mais rápido que o g++ com opção “-march=pentium4″. Quando compilamos com o g++ usando a opção “-march=k8″, o tempo do g++ cai para 2.30 segundos (o tempo para esta versão do programa com a opção “-march=k8″ não apareceu em nenhum post anterior). Por último, a opção Java client é desastrosa:  11.37 segundos…

Mas vamos terminar o serviço. Nossa última otimização do código C++ foi feita nesse post, e consiste em criar uma função para executar o loop mais interno. A vantagem dessa função é que ela fixa duas linhas  e um elemento das matrizes, facilitando o trabalho do otimizador.

Código com função auxiliar:

public class Teste {

  static final int N = 1000;

  static void multiplicaPorLinha( double[] ci,  double aik, double[] bk ) {
    for( int j = 0; j < N; j++ )
      ci[j] += aik * bk[j];  
  }    

  public static void main(String[] args) {
    double a[][] = new double[N][N],
           b[][] = new double[N][N],
           c[][] = new double[N][N];

    java.util.Random rn = new java.util.Random();

    for( int i = 0; i < N; i++ )
      for( int j = 0; j < N; j++ ) {
        a[i][j] = rn.nextInt()/(rn.nextInt()+0.1);
        b[i][j] = rn.nextInt()/(rn.nextInt()+0.1);
        c[i][j] = 0;
    }  

    for( int i = 0; i < N; i++ )
      for( int k = 0; k < N; k++ )  
        multiplicaPorLinha( c[i], a[i][k], b[k] );
  }
}

Voilà!! Agora o Java ficou realmente competitivo: 2.00 segundos. Essa versão compilada com o g++ apresenta tempos de 1.80 e 1.62 segundos para as opções “-march=k8″ e “-march=core2″, respectivamente (essa última disponível somente a partir de versões mais recentes do g++). Cabe ainda dizer que, se incluirmos manualmente no código do C++ o teste de limite de array o tempo não se altera! O otimizador do g++ saca que o teste é desnecessário…

Nesse quesito específico o otimizador do C++ consegue superar bastante o otimizador do Java, mesmo que seja incluído manualmente o teste de limites de array no código. Não tem muito jeito, é uma restrição da linguagem… embora mesmo assim o impacto tenha sido pequeno após as otimizações (desnecessárias no caso do compilador Intel…). A propósito, essa última otimização surpreendentemente torna o código gerado pelo compilador Intel mais lento.

Conclusão:

Embora o Java tenha algumas restrições na especificação da linguagem que podem prejudicar o desempenho, esse ponto não é tão fraco assim – nada que um pouco de ajuda ao compilador não minimize. No último teste, apenas 14% mais lento que o g++, e no segundo teste se iguala ao g++ opção “-march=pentium4″. Em termos de desempenho, a questão é mesmo uma briga de otimizadores. A linguagem em si não é mais lenta nem mais rápida, apenas o otimizador não está dando conta do recado (ainda). E use sempre que possível a opção “-server” no Java!

Segue um gráfico comparativo dos experimentos:

Multiplicação de Matrizes em C++ e Java - tempo em segundos

Em outro post irei mostrar uma situação onde o Java ganha (e bem!) do C++… pois é, já existe isso!!!

“Fé inabalável só o é a que pode encarar de frente a razão (…)”