Estaba leyendo un artículo decuán lento es Haskell jugando con la conjetura de Collatz, que básicamente dice que si sigues multiplicando tres y más uno por un número impar, o dividiendo uno par por dos, eventualmente obtendrás uno. Por ejemplo, 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

El programa dado en este artículo es calcular la secuencia de Collatz más larga en un rango dado. La versión C es:

#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 con Clang O2, se ejecuta en mi computadora durante 0.2s.

La versión de Haskell dada en ese artículo genera la secuencia completa como una lista explícitamente, y luego calcula la longitud de la lista intermedia. Es 10 veces más lento que la versión C. Sin embargo, dado que el autor utilizó LLVM como back-end, que no he instalado, no pude reproducir esto. Usando GHC 7.8 y el backend predeterminado, ejecuta 10 segundos en mi Mac, que es 50 veces más lento que la versión C.

Luego, escribo una versión usando recursión de cola y no generando una lista intermedia:

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 con GHC 7.8 y O2, funciona durante 2 segundos, 10 veces más lento que la versión C.

Curiosamente, cuando cambiéInt en la anotación de tipo aWord, ¡solo pasó 1s, 2 veces más rápido!

He probado BangPatterns para una evaluación estricta y explícita, pero no se pudo notar un aumento significativo en el rendimiento; supongo que el análisis estricto de GHC es lo suficientemente inteligente como para manejar un escenario tan simple.

Mis preguntas son:

Porque es elWord versión tan rápida en comparación con elInt ¿uno?¿Por qué este programa de Haskell es tan lento en comparación con el de C?