Haskell: Почему Int работает хуже, чем Word64, и почему моя программа намного медленнее, чем C?

Я читал статьюкак медленно Хаскелл играет с гипотезой КоллатцаЭто означает, что если вы продолжите умножать три и плюс один на нечетное число или делите четное число на два, вы в конечном итоге получите единицу. Например, 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

Программа, приведенная в этой статье, предназначена для расчета самой длинной последовательности Коллатца в заданном диапазоне. Версия 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;
}

Компилируясь с Clang O2, он работает на моем компьютере в течение 0,2 с.

Версия на Haskell, приведенная в этой статье, генерирует всю последовательность в виде списка в явном виде, а затем вычисляет длину промежуточного списка. Это в 10 раз медленнее, чем версия на C. Однако, поскольку автор использовал LLVM в качестве бэкэнда, который я не установил, я не смог воспроизвести это. Используя GHC 7.8 и бэкэнд по умолчанию, он работает 10 секунд на моем Mac, что в 50 раз медленнее, чем версия C.

Затем я пишу версию, используя хвостовую рекурсию и не генерируя промежуточный список:

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

Скомпилированный с GHC 7.8 и O2, он работает в течение 2 секунд, в 10 раз медленнее, чем версия C.

Интересно, когда я изменилсяInt в аннотации типаWord, он потратил только 1с, в 2 раза быстрее!

Я попробовал BangPatterns для явной строгой оценки, но заметного прироста производительности заметить не удалось - я думаю, строгий анализ GHC достаточно умен, чтобы справиться с таким простым сценарием.

Мои вопросы:

ПочемуWord версия так быстрее по сравнению сInt один?Почему эта программа на Haskell такая медленная по сравнению с C?

Ответы на вопрос(1)

Ваш ответ на вопрос