Archive for September 2009

Lendo o código de funções em arquivos e executando…

Continuando o post anterior…

Uma vez que temos o código de uma função gravado em um arquivo, para executá-la devemos tomar algumas precauções:

1) Garantir que o cabeçalho da função é o mesmo – isso vale para tipos de parâmetros e tipos de valor de retorno, especialmente quando se usa um tipo definido pelo usuário – nesse exemplo, a struct Matrizes.

2) Lembrar que a função sendo lida do arquivo não foi linkeditada com este programa, logo ela não pode usar nada que não seja local. Se houver a necessidade de se chamar uma função externa (por exemplo, chamar a função sin), devemos passar um ponteiro para função.

3) Constantes podem ser utilizadas desde que tenham o mesmo valor, obviamente.

Segue o programa para ler o código de uma função em um arquivo e executá-la. A função que faz a leitura é leFuncao. Ela recebe um nome de arquivo e uma referência para CodigoFuncao, que nada mais é do que um ponteiro para void. Logo, ela recebe uma referência para um ponteiro, já que ela irá alocar uma área para receber a função a ser lida. Essa área deve ser alocada, no Windows, via uma chamada à função da API VirtualAlloc. No Linux não testei, mas pelo que sei seria utilizando a função mmap. O Windows, assim como o Linux e diversos outros SO’s, dividem a memória em áreas de código e de dados, de modo que não é permitido escrever na área de código e nem executar algo a partir da área de dados. Para contornar isso, é necessário informar ao SO que queremos uma área de memória com permissão de escrita e de execução, daí a necessidade de uma chamada a API passando o parâmetro PAGE_EXECUTE_READWRITE. Feito isso, basta obter o tamanho da função (no caso, o mesmo do arquivo), alocar o espaço com o tamanho desejado e ler a função para este espaço. No programa principal, o ponteiro para o código (que é void*) é convertido para ponteiro para função, com os tipos corretos (responsabilidade do programador…). O programa recebe o nome do arquivo a ser lido como primeiro parâmetro da linha de comando.

Código Fonte do programa que lê e executa uma função:

#include <cstdlib>
#include <iostream>
#include <windows.h>
#include <winbase.h>

using namespace std;

typedef void* CodigoFuncao;

const int N = 1000;

struct Matrizes {
  double a[N][N], b[N][N], c[N][N];
};

typedef void (*PtrFuncao)( Matrizes& );

int tamanhoArquivo( FILE* fp ) {
  int tamanho;

  fseek( fp, 0L, SEEK_END );
  tamanho = ftell( fp );
  fseek( fp, 0L, SEEK_SET );

  return tamanho;
}

void leFuncao( const char* nomeArquivo, CodigoFuncao& codigo ) {
  FILE *arquivo = fopen( nomeArquivo, "rb" );
  int tamanhoFuncao = 0;

  if( arquivo == NULL ) {
    cout << "Erro ao abrir arquivo " << nomeArquivo << endl;
    exit( 0 );
  }

  tamanhoFuncao = tamanhoArquivo( arquivo );
  codigo = (CodigoFuncao) VirtualAlloc( NULL, tamanhoFuncao, MEM_COMMIT | MEM_RESERVE, PAGE_EXECUTE_READWRITE);
  fread( codigo, 1, tamanhoFuncao, arquivo );
  fclose( arquivo );

  cout << "Leu funcao do arquivo: " << nomeArquivo << "." << endl;
  cout << "Tamanho da funcao: " << tamanhoFuncao << " bytes." << endl << endl;
}

int main(int argc, char *argv[])
{
  Matrizes& m = *new Matrizes;
  PtrFuncao funcao = NULL;

  if( argc != 2 ) {
    cout << "Uso: lefuncao nomeArquivo" << endl;
    exit(0);
  }

  srand(1);
  for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ ) {
      m.a[i][j] = rand()/(rand()+0.1);
      m.b[i][j] = rand()/(rand()+0.1);
      m.c[i][j] = 0;
    }

  leFuncao( argv[1], (CodigoFuncao&) funcao );

  funcao( m );    

  delete &m;  

  return 0;
}

Saída para a linha de comando “lefuncao funcao1.dat” :

Leu funcao do arquivo: funcao1.dat.
Tamanho da funcao: 160 bytes.

Saída para a linha de comando “lefuncao funcao2.dat” :

Leu funcao do arquivo: funcao2.dat.
Tamanho da funcao: 208 bytes.

Detalhes:

A primeira execução leva como era de se esperar 16,03 segundos. Já a segunda, que representa a versão otimizada o algoritmo de multiplicação de matrizes, 2,73 segundos. Note que esse programa está realmente executando a função de um outro programa…Não há nenhum código de multiplicação de matrizes no programa acima!

Na verdade é possível até salvar a função compilada pelo compilador Intel e executá-la através desse programa, que foi compilado no g++… Nesse caso, o tempo dá 1,19 segundos e a função fica com 408 bytes. Um pouco mais lento que na versão original pois o otimizador do compilador Intel não consegue realizar as mesmas otimizações quando a multiplicação de matrizes se torna uma função. Discutirei isso depois, o importante a notar é que pode-se misturar códigos de outros compiladores… desde que a convenção de chamadas de funções e passagem de parâmetros seja a mesma (stack frame), tudo funciona!

Por último, como mencionado no início do post, se quisermos salvar uma função que utiliza outras funções, devemos passar as outras funções como parâmetros (ponteiros). Qualquer tipo de função pode ser passada, mas métodos e objetos não vão funcionar pelo mesmo problema de linkedição – será necessário transformar uma chamada de um método em uma função que recebe o objeto como parâmetro, por exemplo. Por outro lado, funções (e métodos) garantidamente inline vão funcionar – mas usarão a expansão de código existente no arquivo fonte de onde a função foi compilada.

Chamando outras funções:

double formulaSecreta( double x, double (*f)( double ), int printf(const char*, ... ), const char* format ) {
  double total = 0,
  potencia = 1;

  for( int i = 0; i < 5; i++ ) {
    printf( format, i, potencia, total );
    total += f(x)/potencia;
    potencia *= x;
  }

  return total;
}

Note que esta função espera receber um double, um ponteiro para um função que recebe um double e retorna um double, a função printf (usei o mesmo nome de propósito) e a cadeia de formatação para a printf – embora cadeias de caracteres estáticas sejam constantes, elas não são armazenadas junto com o código da função, logo são como variáveis globais e portanto, têm de ser passadas também como parâmetros. Se o número de funções aumentar demais, é melhor passar uma struct com vários ponteiros para as funções…

É… C++… que linguagem é essa que permite uma coisa doida assim!!!

“A inteligência, Deus no-la deu… No-la deu. Que língua, a nossa!”

Gravando o código de funções em arquivos

É possível gravar o código de máquina de uma função de um programa já compilado  em um arquivo, e ler esse arquivo em outro programa e executar essa função?

SIM!

Parece até mágica, mas o curioso é que tudo funciona! Só devemos tomar alguns cuidados para saber onde começa e termina uma função, e lembrarmos que a função gravada não será linkeditada, logo ela só pode acessar parâmetros – nenhum acesso a variáveis ou funções externas é permitido, ou teremos um erro de execução (access violation). Vamos ver como fazer isso. Primeiro, o código de um programa que grava uma função em um arquivo. A função que faz essa mágica é gravaFuncao. Há duas funções que serão gravadas: multiplica e multiplicaOtimizada. São funções para multiplicar matrizes tiradas desse post. Até aqui não há mistério: o endereço de uma função é o endereço do início de seu código. Para saber onde ela termina, basta olhar para o endereço da função imediatamente seguinte a ela no programa fonte. Para saber seu tamanho, basta subtrair os ponteiros (convertendo para const char* pois o C++ não permite aritmética de ponteiros para função).  Sabendo o tamanho da função, basta escrever o seu código em um arquivo!

Código Fonte do programa que grava uma função:

#include <cstdlib>
#include <iostream>

using namespace std;

typedef const char* EnderecoFuncao;

void gravaFuncao( const char* nomeArquivo, EnderecoFuncao funcao, EnderecoFuncao funcaoSeguinte ) {
  FILE *arquivo = fopen( nomeArquivo, "wb" );
  int tamanhoFuncao = funcaoSeguinte - funcao;

  if( arquivo == NULL ) {
    cout << "Erro ao abrir arquivo " << nomeArquivo << endl;
    exit( 0 );
  }

  fwrite( funcao, 1, tamanhoFuncao, arquivo );
  fclose( arquivo );

  cout << "Funcao gravada no arquivo \"" << nomeArquivo << "\"." << endl;
  cout << "Tamanho da funcao: " << tamanhoFuncao << " bytes." << endl << endl;
}

const int N = 1000;

struct Matrizes {
  double a[N][N], b[N][N], c[N][N];
};

void multiplica( Matrizes& m ) {
  for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ )
      for( int k = 0; k < N; k++ )
        m.c[i][j] += m.a[i][k] * m.b[k][j];
}   

void multiplicaOtimizada( Matrizes& m ) {
  for( int i = 0; i < N; i++ )
    for( int k = 0; k < N; k++ )
      for( int j = 0; j < N; j++ )
        m.c[i][j] += m.a[i][k] * m.b[k][j];
}  

void fim() {} 

int main(int argc, char *argv[])
{
  gravaFuncao( "funcao1.dat", (EnderecoFuncao) multiplica, (EnderecoFuncao) multiplicaOtimizada );
  gravaFuncao( "funcao2.dat", (EnderecoFuncao) multiplicaOtimizada, (EnderecoFuncao) fim ); 

  system("PAUSE");
  return 0;
}

Saída:

Funcao gravada no arquivo "funcao1.dat".
Tamanho da funcao: 160 bytes.

Funcao gravada no arquivo "funcao2.dat".
Tamanho da funcao: 208 bytes.

Detalhes:

Note que é preciso uma função vazia chamada fim para podermos obter o final da função multiplicaOtimizada. E obviamente, é necessário um typecast para EnderecoFuncao para podermos chamar gravaFuncao (EnderecoFuncao é apenas um typedef para const char*).

Vale dizer também que as funções gravadas, apesar de muito parecidas, têm tamanhos diferentes. Isso ocorre porque a segunda função é bastante otimizada pelo compilador após a inversão do loop em j com o loop em k.

Pronto! Já temos dois arquivos com o código das funções acima.  Tudo o que temos de fazer agora é ler esse código e executá-lo passando a estrutura com as matrizes. Mostrarei como fazer isso na sequência deste post…

“Don’t tell me what I can’t do”

Quer velocidade no C++? Não faça a coisa errada…

Complementando o post anterior

Uma otimização que um sujeito poderia pensar em fazer no programa original seria, já que i e j não variam no loop mais interno, usar uma variável temporária para acumular a soma eliminando o acesso ao array, como no programa abaixo:

#include <cstdlib>

int main(int argc, char *argv[])
{
  const int N = 1000;
  typedef double Linha[N];
  Linha * const a = new Linha[N],
        * const b = new Linha[N],
        * const c = new Linha[N];

  srand(1);
  for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ ) {
      a[i][j] = rand()/(rand()+0.1);
      b[i][j] = rand()/(rand()+0.1);
      c[i][j] = 0;
    }  

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

  delete [] a;
  delete [] b;
  delete [] c;
}

Resultado:

O tempo de execução no g++ não muda: 15.95 segundos. O g++ já faz essa otimização internamente…

Já no compilador Intel, o tempo passa de 0.62 para 8.02 segundos… mais rápido que o g++,  mas bem mais lento que o programa original. Isso ocorre por que agora o otimizador não pode trocar a ordem dos loops, e daí não consegue nem vetorializar totalmente a multiplicação nem tornar o acesso à memória sequencial para fazer bom uso do cache.

Ou seja: o sujeito que se acha esperto fazendo a “melhoria” acima na verdade está atrapalhando o trabalho do otimizador…

“I drank what?” said Socrates…

Quer velocidade no C++? Faça a coisa certa…

“I want it all and I want it now”

Diversas vezes temos de programar um algoritmo para realizar um processamento e queremos uma resposta rápida. Nesta situação, muitos programadores saem a escovar bits trocando multiplicações por 2 por shifts, enchem o programa de ponteiros e se esquecem das três soluções iniciais que devem ser pensadas:

1) Usar um algoritmo eficiente: por melhor que seja a sua implementação de bubble-sort a complexidade do algoritmo é O(n2) ao passo que existem algoritmos para ordenação com complexidade O(n log n).

2) Esquecem de ligar o otimizador

3) Usam construções que impedem a otimização do código.

Eu diria que hoje em dia, escovar bits é o último recurso, para ser usado somente quando você vai tentar salvar o mundo… :)

No lugar disso, devemos seguir as recomendações anteriores, sempre escrevendo o código de forma que o otimizador consiga dar jeito. Não é difícil: em geral, quanto mais legível é o programa mais fácil é para o otimizador melhorar o código.

Vamos ver um exemplo de uma rotina simples para multiplica matrizes n x n com n grande, digamos 1000 – ou seja, matrizes de um milhão de elementos…

Multiplicação de Matrizes

O primeiro passo é a escolha do algoritmo. O algoritmo básico que aprendemos em Álgebra possui complexidade O(n3). Embora existam algoritmos com complexidade menor, tais como os algoritmos de Strassen (complexidade O(n2.807)) e o de Coppersmith–Winograd (complexidade O(n2.376)), eles só se tornam mais rápidos que o algoritmo comum a partir de n realmente grande, como apontado neste artigo. Portanto, fiquemos com o algoritmo comum, mostrado no código abaixo. As matrizes são inicializadas pseudo-randomicamente, mas nesse caso isso não é importante.

#include <cstdlib>

int main(int argc, char *argv[])
{
  const int N = 1000;
  typedef double Linha[N];
  Linha *a = new Linha[N],
        *b = new Linha[N],
        *c = new Linha[N];

  srand(1);
  for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ ) {
      a[i][j] = rand()/(rand()+0.1);
      b[i][j] = rand()/(rand()+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];

  delete [] a;
  delete [] b;
  delete [] c;
}

O programa acima, compilado no Dev-C++ 4.9.9.2 usando o g++ 3.4.2 (um pouco ultrapassado…) e sem nenhuma modificação nos parâmetros defaults do compilador, roda em 18.50 segundos (média de 4 execuções sem nenhum outro programa executando e descartando a primeira execução – por causa do cache de disco). O problema aqui é que por default o otimizador do g++ fica desligado. Então, vamos ligá-lo passando alguns parâmetros:

-O3 -funroll-loops -fprefetch-loop-arrays -march=pentium4 -msse2

O resultado melhora um pouco: 15.95 segundos – um ganho de 13,7%. Pouco? Eu também acho, mas o interessante é que veio sem trabalho nenhum… Na verdade, ligando apenas o otimizador (-O3) já há um ganho significativo: 16.16 segundos. Para entender o que essas outras opções significam recomendo olhar a documentação do g++.

Para mostrar que escovar bits pura e simplesmente não resolve, fiz duas alterações no programa acima que não resultaram em nenhum ganho de desempenho, na verdade até piorou um pouco…

1) Alocação estática ds matrizes

static double a[N][N],
              b[N][N],
              c[N][N];

// O restante do código não muda, exceto pelo delete do final

Essa opção tem o inconveniente de alocar a memória o tempo todo da execução. Essa versão levou 16.07 segundos…

2) Uso de ponteiros duplos

int main(int argc, char *argv[])
{
  const int N = 1000;
  double **a = new double*[N],
        **b = new double*[N],
        **c = new double*[N];

  for( int i = 0; i < N; i++ ) {
    a[i] = new double[N];
    b[i] = new double[N];
    c[i] = new double[N];
  }

  srand(1);
  for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ ) {
      a[i][j] = rand()/(rand()+0.1);
      b[i][j] = rand()/(rand()+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]; 

  for( int i = 0; i < N; i++ ) {
    delete [] a[i];
    delete [] b[i];
    delete [] c[i];
  }

  delete [] a;
  delete [] b;
  delete [] c;
}

Note que é necessário alocar (e desalocar) espaço para cada uma das linhas da matriz. Essa versão levou 16.95 segundos… E se passarmos para aritmética de ponteiros o resultado só piora: 17.54 segundos. Porque isso ocorre? Por que o otimizador não consegue otimizar muito bem ponteiros…

E agora? Bem, agora é hora de olhar o código e pensar.  De cara, vemos que na linha

c[i][j] += a[i][k] * b[k][j]

apenas k varia no loop mais interno. Porém, isso o otimizador também nota. Olhando para a[i][k], e já  que no loop interno apenas k varia, estamos lendo posições sequenciais na memória. Porém, em b[k][j] isso não ocorre. Acessos sequenciais na memória são muito bons, porque o processador pode utilizar bem o cache L1 e o prefetching. Olhando o comando acima, vemos que se transpusermos a matriz b (bt[j][k] = b[k][j]) , o acesso seria sequencial. Será que isso faz diferença? Faz e muita… não vou colocar o código para transpor a matriz, é simplesmente  dois loops aninhados trocando b[i][j] com b[j][i], e mais para frente veremos que não vamos precisar disso. Assim, a linha mais interna do loop fica:

c[i][j] += a[i][k] * b[j][k]

E o tempo de execução? Pasmem… 2.61 segundos… Inacredtável, não? 7x mais rápido!

Mas transpor a matriz em outros casos pode não ser tão simples. Melhor procurar outra opção. Olhando os índices da linha original, o melhor seria se no loop interno quem variasse fosse o ja[i][k] se tornaria constante e tanto b quanto c seriam acessados sequencialmente. Mas é possível trocar a ordem dos loops? Sim, e isso é uma otimização conhecida de muitos otimizadores, porém não está presente no g++3.4.2 usado pelo Dev-C++. A boa notícia é que está presente nas versões mais recentes do g++, embora não ainda para Windows.

Enquanto essa otimização não vem, trocamos a ordem do loop para ver o resultado:

#include <cstdlib>

int main(int argc, char *argv[])
{
  const int N = 1000;
  typedef double Linha[N];
  Linha *a = new Linha[N],
        *b = new Linha[N],
        *c = new Linha[N];

  srand(1);
  for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ ) {
      a[i][j] = rand()/(rand()+1);
      b[i][j] = rand()/(rand()+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];

  delete [] a;
  delete [] b;
  delete [] c;
}

Tempo: 2.79 segundos, bem semelhante à transposição da matriz. E de qualquer forma, essa modificação não afeta em nada a clareza do código. E o melhor, há compiladores que já a fazem.

Por último, podemos ainda usar outro compilador. Para este exemplo , testei com o compilador Intel C++, reconhecidamente um dos mais rápidos do mercado. No caso do primeiro e do último programa não houve diferença nesses casos pois esse compilador faz essa otimização de trocar a ordem dos loops. Opções:

/O3 /QxHost

Resultado: primeiro programa, 0.62 segundos!!! Quase 30x mais rápido! E dessa vez, sem termos de mudar uma linha no código! Em parte, essa diferença pode ser explicada também pelo fato de que o compilador Intel faz um bom uso das instruções vetoriais presentes nos processadores Intel. Já a versão com ponteiros para ponteiros levou 0.80 segundos… parece pouco, mas ela foi quase 30% mais lenta…

Resumindo:

Sempre é bom olhar as alternativas antes de sair otimizando código na mão para usar ponteiros (que trazem a falsa sensação de velocidade), e principalmente, entender o que o compilador é capaz de otimizar e o que ele não otimiza, o que afeta a velocidade do processador  onde o programa irá executar e quais recursos ele oferece. Uma simples troca de posição dos loops deu um ganho enorme! Uma simples troca de compilador deu um ganho maior ainda…

Até o próximo post!

Método template virtual

Não funciona…

#include <cstdlib>
#include <iostream>

using namespace std;

class MyClass {
  template <class T>
  virtual void foo(T& t) {}
};

int main(int argc, char *argv[])
{
  system("PAUSE");
  return EXIT_SUCCESS;
}

Saída:

invalid use of `virtual' in template declaration of 'virtual void MyClass::foo(T&)'

Detalhes:

Métodos implementados por templates não podem ser virtuais. Que chato, mas a pergunta é: porque alguém iria querer que um método template fosse virtual?

“ô loco, meu…”