Eu estava lendo um artigo dequão lento Haskell é em brincar com a conjectura de Collatz, que basicamente afirma que se você continuar multiplicando três e mais um por um número ímpar ou dividindo um número par por dois, você receberá um. Por exemplo, 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

O programa fornecido neste artigo é calcular a sequência Collatz mais longa em um determinado intervalo. A versão C é:

#include <stdio.h>

int main(int argc, char **argv) {
   int max_a0 = atoi(argv[1]); 
   int longest = 0, max_len = 0;
   int a0, len;
   unsigned long a;

   for (a0 = 1; a0 <= max_a0; a0++) {
      a = a0;
      len = 0;

      while (a != 1) {
         len++;
         a = ((a%2==0)? a : 3*a+1)/2;
      }

      if (len > max_len) {
         max_len = len;
         longest = a0;
      }
   }
   printf("(%d, %d)\n", max_len, longest);
   return 0;
}

Compilando com o Clang O2, ele roda no meu computador por 0,2s.

A versão Haskell fornecida nesse artigo gera explicitamente a sequência inteira como uma lista e calcula o comprimento da lista intermediária. É 10x mais lento que a versão C. No entanto, como o autor usou o LLVM como back-end, que eu não instalei, não consegui reproduzir isso. Usando o GHC 7.8 e o back-end padrão, ele executa 10s no meu Mac, que é 50x mais lento que a versão C.

Então, escrevo uma versão usando recursão de cauda e não gerando uma lista intermediária:

collatzNext :: Int -> Int
collatzNext a
  | even a    = a `div` 2
  | otherwise = (3 * a + 1) `div` 2

collatzLen :: Int -> Int
collatzLen n = collatzIter n 0
  where
    collatzIter 1 len = len
    collatzIter n len = collatzIter (collatzNext n) (len + 1)

main = do
  print $ maximum $ [collatzLen x | x <- [1..1000000]]

Compilado com GHC 7.8 e O2, é executado por 2s, 10x mais lento que a versão C.

Curiosamente, quando eu mudeiInt na anotação de tipo paraWord, gastou apenas 1s, 2x mais rápido!

Eu tentei o BangPatterns para uma avaliação estrita explícita, mas nenhum ganho significativo de desempenho pôde ser observado - acho que a análise estrita do GHC é inteligente o suficiente para lidar com um cenário tão simples.

Minhas perguntas são:

Porque é oWord versão tão mais rápida em comparação com oInt 1?Por que esse programa Haskell é tão lento em comparação com o C?