Metaprogramming com constexpr

Até ano passado, quando eu queria fazer algum projetinho onde eu precisava da maior velocidade possível, acabava escolhendo escrevê-lo em C++. Mas a minha vida mudou quando eu conheci o C++0x. Ele é muito superior ao C++ tradicional, adicionando features que faziam muita falta, como lambdas, variáveis auto e range for.

Uma das features novas que mais gosto é o constexpr, uma maneira de avisar ao compilador que o resultado de função pode ser determinado em tempo de compilação. Combinando isso com funções recursivas, nós temos uma maneira nova de fazer metaprogramming em C++, bem melhor que o tradicional template metaprogramming.

Para mostrar a superioridade do constexpr, resolvi escrever de três maneiras diferentes uma função bem simples: o totiente de Euler, cuja definição é a quantidade de inteiros positivos menores que n, e que não possuem fatores em comum com n. Escrito em C++ tradicional, essa função fica assim:

int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

int totient(int x) {
  int sum = 0;
  for (int i = 1; i < x; i++) {
    if (gcd(x, i) == 1) sum++;
  }
  return sum;
}

int main() {
  cout << totient(1000) << endl;
}

O código em si é bem simples de entender e compila em qualquer lugar. Eu calculei o GCD usando o algoritmo de Euclides, que é O(log n), então essa implementação do totiente é O(n log n).

Compare agora com o mesmo algoritmo escrito em template metaprogramming:

template<int a, int b>
struct GCD {
  const static int result = GCD<b, a % b>::result;
};

template<int a>
struct GCD<a, 0> {
  const static int result = a;
};

template<int x, int i>
struct TotientHelper {
  const static int result =
      (GCD<x, i>::result == 1) +
      TotientHelper<x, i - 1>::result;
};

template<int x>
struct TotientHelper<x, 0> {
  const static int result = 0;
};

template<int x>
struct Totient {
  const static int result =
      TotientHelper<x, x - 1>::result;
};

int main() {
  const int x = Totient<1000>::result;
  cout << x << endl;
}

Essa versão é bem mais difícil de entender e é cheia de boilerplate. A vantagem dela é que o cálculo do totiente é feito em tempo de compilação; então, em runtime, o resultado é calculado em O(1).

Por fim, a versão em c++0x usando constexpr:

constexpr int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}

constexpr int totient(int x, int i) {
  return i == 0 ? 0 : (gcd(x, i) == 1) + totient(x, i - 1);
}

constexpr int totient(int x) {
  return totient(x, x - 1);
}

int main() {
  constexpr auto x = totient(NUMBER);
  cout << x << endl;
}

Essa versão não é tão simples quanto a que calcula em runtime, mas também não é excessivamente complexa como a versão com templates.

Para fazer metaprogramming com constexpr, você só precisa seguir algumas regras simples:

• O corpo da função precisa ter um único return.
• Você não pode usar if. Se você precisar de condicionais, tem que usar o operador ternário.
• Você não pode usar for. Se você precisar de loops, tem que usar recursão.
• Você não pode fazer atribuições a variáveis.
• Uma pegadinha: ele só faz o cálculo em compile time se você atribuir o resultado a uma variável constexpr. Se você tentar fazer diretamente cout << totient(100), ele vai calcular em run-time.

Além disso, obviamente, você precisa de um compilador que suporte constexpr. Até onde eu sei, o único que aceita constexpr é o gcc 4.7 ou superior.

Mas a grande vantagem do constexpr sobre os templates não é só a facilidade de programação: é o tempo de compilação. Um programa com constexpr compila muito mais rápido que uma versão com templates. Para comparar o tempo de compilação, eu fiz um script que mede o tempo para vários valores do totiente:

Script em C++ para calcular o totiente em run-time
Script em C++ para calcular o totiente com templates
Script em C++0x para calcular o totiente com constexpr
Script em Python para medir o tempo dos programas acima

Vamos primeiro comparar o tempo de compilação da versão em runtime com a versão em template:

Como esperado, o tempo de compilação da versão em runtime é constante e bem pequeno. Já a versão em template é bem ruinzinha. Eu fiz uma regressão para determinar que curva é essa, e o resultado é que é uma parábola (com coeficiente de determinação R²=0.999, ou seja, com bastante certeza).

Agora a fraqueza do método com templates é evidente: o algoritmo era O(n log n) em runtime, virou O(n²) em compile-time. Veja como isso não acontece com a versão com constexpr:

Ah, agora sim! A versão com constexpr continua sendo O(n log n), só trocou o tempo de run-time pelo tempo de compilação. Comparado o template nem tem graça: para n=30000, a versão com constexpr compila em 1 segundo, e versão em template compila em 2 minutos.

A essa altura já estamos convencidos de que o constexpr é o melhor jeito de implementar metaprogramming, mas ainda falta a pergunta crucial: na prática, pra que isso serve?

Para mim, a utilidade mais imediata é pra conseguir primeiro lugar nos problemas do spoj! Como o spoj só leva em conta o tempo de run-time para ordenar as soluções, se você jogar um pouco do tempo do run-time para a compilação, consegue subir algumas colocações no ranking :)