Archive for the ‘Estilos de programação’ Category.

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

Realmente otimizando C++

Otimização Final – g++

No post Quer velocidade no C++? Faça a coisa certa…, mostrei como podemos ajudar o otimizador do g++ sem escovar bits. Agora, mostro que tipo de escovação de bits é aceitável, e produz bons resultados. Note que ainda assim, o tempo final continua maior que o do compilador Intel.

Basicamente, podemos ajudar o compilador a identificar partes dos loops que contém dados invariantes. O novo programa, ao invés de ter os três loops aninhados, possui uma chamada a uma função para fazer a multiplicação por linha. No entanto, essa função é inline, de modo que é expandida no código. A princípio, isso não deveria melhorar o desempenho, porém o fato de passarmos parâmetros dá uma dica importante ao compilador: os parâmetros não mudam. Nem sempre o otimizador consegue descobrir isso.

#include <cstdlib>

const int N = 1000;
typedef double Linha[N];

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

int main(int argc, char *argv[])
{
  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 k = 0; k < N; k++ )
      multiplicaPorLinha( c[i], a[i][k], b[k] );

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

Essa otimização sozinha já reduz o tempo de 2.79 segundos para 2.22 segundos. Mas além disso, se estivermos amarrados ao Dev-Cpp, podemos trocar a linha de comando para otimizar para o K8 ao invés do Pentium 4 – o motivo é que quase todas as novas CPUs, mesmo as Intel, são compatíveis com o K8, e o código que o g++ gera para o K8 é melhor que o gerado para o Pentium 4, especialmente por causa do conjunto de instruções sse3. Linha de comando:

-O3 -funroll-loops -fprefetch-loop-arrays -march=k8 -msse3

Resultado: 1.80 segundos. Por último, se você instalar o g++ 4.40 (para Windows, MingW), pode usar a seguinte linha de argumentos:

-O3 -funroll-loops -fprefetch-loop-arrays -march=core2 -msse4

Agora sim para Intel Core 2. Resultado: 1.62 segundos… 10x mais rápido que o programa com opção -O3, 1.62 x mais rápido que o post anterior, e 11% mais rápido que para o K8.

Infelizmente essa otimização faz com que o compilador Intel perca umpouco de desempenho: agora fica com 1.2 segundos, o dobro do tempo anterior, embora ainda mais rápido que o g++. Não consegui descobrir porque isso ocorreu… :(

Rio 2016!!!!

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!