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

Question

Я читал статью how slow Haskell it is in playing with Collatz conjecture, в которой говорится, что если вы продолжаете умножать три и плюс одно на нечетное число или делить четное на два, вы в конечном итоге получите один. Например, 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

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

Мои вопросы:

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

Answer 1

Производительность программы зависит от нескольких факторов. Если мы получим все правильно, производительность будет такой же, как и в программе C. Проходя через эти факторы:

1. Использование и сравнивающих правильное слово размеры

Опубликованная код C сниппет не совсем верно; он использует 32-битные целые числа на всех архитектурах, а Haskell Int -s - 64-разрядные на 64-битной машине. Прежде всего, мы должны обязательно использовать один и тот же размер слова в обеих программах.

Кроме того, мы должны всегда использовать родной размер интегральных типов в нашем коде Haskell. Поэтому, если мы находимся на 64-битной системе, мы должны использовать 64-битные номера и избегать Int32 -s и Word32 -s, если только для них не существует конкретной потребности. Это связано с тем, что операции с неродными целыми числами в основном реализованы как foreign calls rather than primops, поэтому они значительно медленнее.

2.Отдел в collatzNext

div медленнее, чем quot для Int, потому что div обрабатывает отрицательные числа differently. Если мы используем div и переключаемся на Word, программа становится быстрее, потому что div - это то же самое, что и quot для Word. quot с Int работает так же хорошо. Тем не менее, это все еще не так быстро, как C. Мы можем разделить на два путем смещения битов вправо. По какой-то причине даже LLVM не делает этого конкретного сокращения силы в этом примере, поэтому мы лучше всего это сделаем вручную, заменив quot n 2 на shiftR n 1.

3. Проверка ровности

Самый быстрый способ проверить это путем проверки наименьший значащий бит. LLVM может оптимизировать even, в то время как родной codegen не может. Итак, если мы находимся на родном кодеге, even n может быть заменен на n .&. 1 == 0, и это дает хороший прирост производительности.

Однако, я нашел что-то с ошибкой производительности с GHC 7.10. Здесь мы не получаем inline even для Word, что разрушает производительность (вызов функции с выделенным кучей Word в самой горячей части кода делает это). Поэтому здесь мы должны использовать rem n 2 == 0 или n .&. 1 == 0 вместо even. Однако even для Int получает тонкий тон.

4. Взрыватель прочь списки в collatzLen

Это очень важный фактор. Связанный пост в блоге немного устарел относительно этого. GHC 7.8 не может слить здесь, но 7.10 может. Это означает, что с GHC 7.10 и LLVM мы можем удобно получить C-подобную производительность без существенного изменения исходного кода.

collatzNext a = (if even a then a else 3*a+1) `quot` 2 
collatzLen a0 = length $ takeWhile (/= 1) $ iterate collatzNext a0 
maxColLen n = maximum $ map collatzLen [1..n] 

main = do 
    [n] <- getArgs 
    print $ maxColLen (read n :: Int) 

С ghc-7.10.1 -O2 -fllvm и n = 10000000 выше, программа запускается в 2.8 секунд, в то время как эквивалентная программа на С работает в 2,4 секунд. Если я скомпилирую тот же код без LLVM, то вместо этого я получаю 12.4 второе время выполнения. Это замедление полностью связано с отсутствием оптимизации на even. Если мы используем a .&. 1 == 0, то замедление исчезнет.

5. Соединяя прочь списки при расчете максимальной длины

Даже не GHC 7,10 может сделать это, так что мы должны прибегнуть к ручному петлевой записи.

collatzNext a = (if a .&. 1 == 0 then a else 3*a+1) `shiftR` 1 
collatzLen = length . takeWhile (/= 1) . iterate collatzNext 

maxCol :: Int -> Int 
maxCol = go 1 1 where 
    go ml i n | i > n = ml 
    go ml i n = go (max ml (collatzLen i)) (i + 1) n 

main = do 
    [n] <- getArgs 
    print $ maxCol (read n :: Int) 

Теперь для ghc-7.10.1 -O2 -fllvm и n = 10000000, приведенный выше код работает в 2,1 секунд, в то время как программа работает в C 2,4 секунд. Если мы хотим достичь аналогичной производительности без LLVM и GHC 7.10, мы просто должны вручную применить важные недостающие оптимизации:

collatzLen :: Int -> Int 
collatzLen = go 0 where 
    go l 1 = l 
    go l n | n .&. 1 == 0 = go (l + 1) (shiftR n 1) 
     | otherwise = go (l + 1) (shiftR (3 * n + 1) 1) 

maxCol :: Int -> Int 
maxCol = go 1 1 where 
    go ml i n | i > n = ml 
    go ml i n = go (max ml (collatzLen i)) (i + 1) n 

main = do 
    [n] <- getArgs 
    print $ maxCol (read n :: Int) 

Теперь, с ghc-7.8.4 -O2 и n = 10000000, нашим код работает в 2,6 секунд.