BLOG C++

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

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

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”

Na dúvida entre usar um ponteiro para uma função ou criar um functor?

Antes de mais nada, é preciso deixar claro o que é um functor: um objeto função, também chamado de um functor, é uma construção de programação que permite a um objeto ser invocado ou chamado como se fosse uma função comum, geralmente com a mesma sintaxe. Ou seja, qualquer objeto cuja classe redefina o operador “()” pode ser considerado um functor.

Na STL existem diversas funções (a maioria definidas como templates) que recebem como parâmetro um ponteiro para uma função, que pode ser também um functor. Um exemplo típico é a função for_each, que percorre elementos de uma coleção qualquer aplicando uma determinada função. for_each recebe três parâmetros: dois iteradores, início e fim, e uma função (ou functor) que será chamado para cada elemento da coleção. Segue um exemplo onde é mostrado também o código de uma possível versão da função forEach definida como template.

Código Fonte usando ponteiro para função:

#include <cstdio>

using namespace std;

template <class Itr, class F>
inline void forEach( Itr i, Itr fim, F f ) {
  while( i != fim )
    f( *i++ );
}

inline void print( int n ) {
  printf("%d ", n );
}

int main(int argc, char *argv[])
{
  int tab[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  forEach( tab, tab+10, print );
}

O programa acima imprime os números que estão no array tab. Note que a função forEach é genérica o suficiente par trabalhar tanto com arrays (ponteiros) como com containers da STL. E embora todas as funções estejam definidas como inline, a função print não será expandida inline dentro de forEach – isso ocorre porque está sendo usado um ponteiro para esta função. Por outro lado a função forEach será expandida inline dentro da função main. Observe o código assembly gerado, com as opções de otimização ligadas (-O3).

Código assembly gerado:

	.file	"main.cpp"
	.section .rdata,"dr"
LC0:
	.ascii "%d \0"
	.text
	.align 2
	.p2align 4,,15
.globl __Z5printi
	.def	__Z5printi;	.scl	2;	.type	32;	.endef
__Z5printi:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$8, %esp
	movl	8(%ebp), %eax
	movl	$LC0, (%esp)
	movl	%eax, 4(%esp)
	call	_printf
	leave
	ret
	.def	___main;	.scl	2;	.type	32;	.endef
	.align 2
	.p2align 4,,15
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	$16, %eax
	movl	%esp, %ebp
	pushl	%edi
	pushl	%esi
	pushl	%ebx
	subl	$76, %esp
	andl	$-16, %esp
	call	__alloca
	movl	$__Z5printi, %edi
	leal	-72(%ebp), %ebx
	leal	-32(%ebp), %esi
	call	___main
	movl	$0, -72(%ebp)
	movl	$1, -68(%ebp)
	movl	$2, -64(%ebp)
	movl	$3, -60(%ebp)
	movl	$4, -56(%ebp)
	movl	$5, -52(%ebp)
	movl	$6, -48(%ebp)
	movl	$7, -44(%ebp)
	movl	$8, -40(%ebp)
	movl	$9, -36(%ebp)
	jmp	L11
	.p2align 4,,7
L13:
	movl	(%ebx), %edx
	addl	$4, %ebx
	movl	%edx, (%esp)
	call	*%edi
L11:
	cmpl	%esi, %ebx
	jne	L13
	leal	-12(%ebp), %esp
	xorl	%eax, %eax
	popl	%ebx
	popl	%esi
	popl	%edi
	leave
	ret
	.def	_printf;	.scl	2;	.type	32;	.endef

Detalhes:

Assembly é um porre de se olhar, mas vamos lá… Coloquei em vermelho as partes importantes. A função __Z5printi é como o compilador chamou a função print do programa fonte em C++. Ela é criada, apesar de ser declarada como inline, porque na função main o seu endereço foi passado para a função forEach, como dito acima. Sempre que for necessário, o compilador irá gerar código para uma função declarada inline, por exemplo quando um ponteiro para a função é usado. Mas não se preocupe, a função não deixou de ser inline, nas outras chamadas ela será expandida normalmente. No código dessa função vemos a chamada a printf. __Z5printi é movido para o registrador edi, e logo em seguida no bloco L13 há um call para o endereço nesse registrador.

Agora compare o que ocorre quando usamos um functor no lugar de uma função. Esse functor é bem simples, apenas uma struct com o operador “()” redefinido, e recebendo um int.

Código Fonte usando functor:

#include <cstdio>

using namespace std;

template <class Itr, class F>
inline void forEach( Itr i, Itr fim, F f ) {
  while( i != fim )
    f( *i++ );
}

struct Imprime {
  void operator () ( int n ) {
    printf("%d ", n );
  }
};

int main(int argc, char *argv[])
{
  int tab[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

  forEach( tab, tab+10, Imprime() );
}

Note que na chamada a forEach é passado um objeto temporário do tipo Imprime. Pode-se também declarar uma variável local e passá-la, mas não há necessidade. Por outro lado, o C++ exige que ao se criar um objeto temporário se chame o construtor, nesse caso, o default, sem nenhum parâmetro.

Código assembly gerado:

	.file	"main.cpp"
	.def	___main;	.scl	2;	.type	32;	.endef
	.section .rdata,"dr"
LC0:
	.ascii "%d \0"
	.text
	.align 2
	.p2align 4,,15
.globl _main
	.def	_main;	.scl	2;	.type	32;	.endef
_main:
	pushl	%ebp
	movl	$16, %eax
	movl	%esp, %ebp
	pushl	%esi
	pushl	%ebx
	subl	$64, %esp
	andl	$-16, %esp
	call	__alloca
	leal	-56(%ebp), %ebx
	leal	-16(%ebp), %esi
	call	___main
	movl	$0, -56(%ebp)
	movl	$1, -52(%ebp)
	movl	$2, -48(%ebp)
	movl	$3, -44(%ebp)
	movl	$4, -40(%ebp)
	movl	$5, -36(%ebp)
	movl	$6, -32(%ebp)
	movl	$7, -28(%ebp)
	movl	$8, -24(%ebp)
	movl	$9, -20(%ebp)
	jmp	L11
	.p2align 4,,7
L13:
	movl	(%ebx), %edx
	addl	$4, %ebx
	movl	$LC0, (%esp)
	movl	%edx, 4(%esp)
	call	_printf
L11:
	cmpl	%esi, %ebx
	jne	L13
	leal	-8(%ebp), %esp
	xorl	%eax, %eax
	popl	%ebx
	popl	%esi
	leave
	ret
	.def	_printf;	.scl	2;	.type	32;	.endef

Resumo da ópera:

Agora sim… o compilador não declarou nenhuma função para o operador “()” da struct Imprime, expandido a chamada a printf diretamente no código da função main no bloco L13. Portanto, é mais vantajoso usar um functor do que um ponteiro para uma função, especialmente no caso de templates expandidas inline, que são a grande maioria na prática. O código gerado é menor e se evita uma chamada de função. Claro, em um programa pequeno esse custo é desprezível, mas o objetivo aqui é mostrar que o uso de functores geram um código mais eficiente do que o uso de ponteiros para funções, ao contrário do que o senso comum diz. Novamente, é necessário ajudar o otimizador.

Haveria alguma vantagem em usar um functor se o código da template forEach não fosse inline? Sim, pois mesmo dessa forma uma chamada de função é evitada, pois o operador “()” seria expandido inline dentro de forEach.

E se a função forEach não fosse template? Aí, provavelmente ela receberia um functor por referência e polimórfico, ou seja, com o operador “()” declarado como virtual e toda uma hierarquia de functores… e então talvez empatasse com a opção usando ponteiro para função! Mas eficiência não é a única vantagem dos functores: por serem objetos, podem ter outros campos etc.

“Though his mind is not for rent/Don’t put him down as arrogant“

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!!!!