Как улучшить производительность этой программы на Haskell?

Question

Я работаю над проблемами в Project Euler как способ изучения Haskell, и я обнаружил, что мои программы намного медленнее, чем сопоставимая версия C, даже когда они скомпилированы. Что я могу сделать, чтобы ускорить мои программы на Haskell?

Например, мое грубое решение проблемы Задача 14 :

import Data.Int
import Data.Ord
import Data.List

searchTo = 1000000

nextNumber :: Int64 -> Int64
nextNumber n
    | even n    = n `div` 2
    | otherwise = 3 * n + 1

sequenceLength :: Int64 -> Int
sequenceLength 1 = 1
sequenceLength n = 1 + (sequenceLength next)
    where next = nextNumber n

longestSequence = maximumBy (comparing sequenceLength) [1..searchTo]

main = putStrLn $ show $ longestSequence

Это занимает около 220 секунд, в то время как «эквивалентная» версия с перебором в С занимает всего 1,2 секунды.

#include <stdio.h>

int main(int argc, char **argv)
{
    int longest = 0;
    int terms = 0;
    int i;
    unsigned long j;

    for (i = 1; i <= 1000000; i++)
    {
        j = i;
        int this_terms = 1;

        while (j != 1)
        {
            this_terms++;

            if (this_terms > terms)
            {
                terms = this_terms;
                longest = i;
            }

            if (j % 2 == 0)
                j = j / 2;
            else
                j = 3 * j + 1;
        }
    }

    printf("%d\n", longest);
    return 0;
}

Что я делаю не так? Или я наивный, чтобы думать, что Haskell мог даже приблизиться к скорости C?

(Я компилирую версию C с помощью gcc -O2, а версию на Haskell с помощью ghc --make -O).

Answer 1

Для тестирования я только что установил searchTo = 100000. Требуемое время составляет 7,34 с . Несколько модификаций приводят к значительному улучшению:

1. Используйте Integer вместо Int64. Это улучшает время до 1,75 с .

2. Используйте аккумулятор (вам не нужна последовательность длин, чтобы быть ленивой, верно?) 1.54 с .

   seqLen2 :: Int -> Integer -> Int
   seqLen2 a 1 = a
   seqLen2 a n = seqLen2 (a+1) (nextNumber n)
   
   sequenceLength :: Integer -> Int
   sequenceLength = seqLen2 1
   

3. Перепишите nextNumber, используя quotRem, таким образом избегая вычисления деления дважды (один раз в even и один раз в div). 1.27s .

   nextNumber :: Integer -> Integer
   nextNumber n 
       | r == 0    = q
       | otherwise = 6*q + 4
       where (q,r) = quotRem n 2 
   

4. Используйте преобразование Шварца вместо maximumBy. Проблема maximumBy . comparing в том, что функция sequenceLength вызывается более одного раза для каждого значения. 0.32s .

   longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]]
   

---

Примечание:

• Я проверяю время, компилируя с ghc -O и запускаю с +RTS -s)
• Моя машина работает на Mac OS X 10.6. Версия GHC - 6.12.2. Скомпилированный файл в архитектуре i386.)
• Проблема C выполняется при 0.078s с соответствующим параметром. Скомпилировано с gcc -O3 -m32.

Answer 2

Хотя это уже довольно старое, позвольте мне упомянуть, есть один важный момент, который ранее не рассматривался.

Во-первых, время различных программ на моем компьютере.Поскольку я работаю в 64-битной системе linux, они показывают несколько иные характеристики: использование Integer вместо Int64 не повышает производительность, как это было бы с 32-битным GHC, где каждая операция Int64 влечет за собойстоимость C-вызова, в то время как вычисления с подгонкой Integer в знаковых 32-разрядных целых числах не нуждаются во внешнем вызове (так как здесь только несколько операций превышают этот диапазон, Integer - лучший выбор для 32-разрядногоGHC).

• C: 0,3 секунды
• Оригинальный Haskell: 14,24 секунды, используя Integer вместо Int64: 33,96 секунды
• Улучшенная версия KennyTM:5,55 секунды, используя Int: 1,85 секунды
• версия Криса Куклевича: 5,73 секунды, используя Int: 1,90 секунды
• версия FUZxxl: 3,56 секунды, используя quotRem вместо divMod: 1,79 секунды

Так что же у нас?

1. Рассчитать длину с помощью аккумулятора, чтобы компилятор мог преобразовать его (в основном) в цикл
2. Не пересчитывайте последовательностьдля сравнения
3. Не использовать div соотв.divMod когда это не нужно, quot соотв.quotRem намного быстрее

Чего еще не хватает?

if (j % 2 == 0)
    j = j / 2;
else
    j = 3 * j + 1;

Любой использованный мной C-компилятор преобразует тест j % 2 == 0 в битовую маску и не делаетиспользуйте инструкцию деления.GHC этого не делает (пока).Поэтому тестирование even n или вычисление n `quotRem` 2 - довольно дорогая операция.Замена nextNumber в Integer версии KennyTM на

nextNumber :: Integer -> Integer
nextNumber n
    | fromInteger n .&. 1 == (0 :: Int) = n `quot` 2
    | otherwise = 3*n+1

сокращает время его работы до 3,25 секунды (Примечание: для Integer, n `quot` 2 быстрее, чем n `shiftR` 1, что занимает 12,69 секунды!).

То же самое в версии Int сокращает время работы до 0,41 секунды.Для Int с сдвиг битов для деления на 2 немного быстрее, чем операция quot, что сокращает его время выполнения до 0,39 секунды.

Устраняет построение списка (это непоявляется в версии C либо),

module Main (main) where

import Data.Bits

result :: Int
result = findMax 0 0 1

findMax :: Int -> Int -> Int -> Int
findMax start len can
    | can > 1000000 = start
    | canlen > len = findMax can canlen (can+1)
    | otherwise = findMax start len (can+1)
      where
        canlen = findLen 1 can

findLen :: Int -> Int -> Int
findLen l 1 = l
findLen l n
    | n .&. 1 == 0  = findLen (l+1) (n `shiftR` 1)
    | otherwise     = findLen (l+1) (3*n+1)

main :: IO ()
main = print result

приводит к еще небольшому ускорению, в результате чего время работы составляет 0,37 секунды.

Таким образом, версия на Haskell близко соответствует версии Cне занимает много времени, это фактор ~ 1,3.

Ну, давайте будем честными, в C-версии есть неэффективность, которой нет в версиях на Haskell,

if (this_terms > terms)
{
    terms = this_terms;
    longest = i;
}

появляется во внутреннем цикле.Удаление этого из внутреннего цикла в версии C сокращает время его работы до 0,27 секунды, делая коэффициент ~ 1,4.

Answer 3

Сравнение может слишком много пересчитать sequenceLength.Это моя лучшая версия:

type I = Integer
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !I deriving (Eq,Ord,Show)

searchTo = 1000000

nextNumber :: I -> I
nextNumber n = case quotRem n 2 of
                  (n2,0) -> n2
                  _ -> 3*n+1

sequenceLength :: I -> Int
sequenceLength x = count x 1 where
  count 1 acc = acc
  count n acc = count (nextNumber n) (succ acc)

longestSequence = maximum . map (\i -> P (sequenceLength i) i) $ [1..searchTo]

main = putStrLn $ show $ longestSequence

Ответ и время медленнее, чем C, но он использует произвольные целые числа точности (через тип Integer):

ghc -O2 --make euler14-fgij.hs
time ./euler14-fgij
P 525 837799

real 0m3.235s
user 0m3.184s
sys  0m0.015s

Answer 4

Даже если я немного опоздал, вот мое, я удалил зависимость от списков, и это решение вообще не использует кучи.

{-# LANGUAGE BangPatterns #-}
-- Compiled with ghc -O2 -fvia-C -optc-O3 -Wall euler.hs
module Main (main) where

searchTo :: Int
searchTo = 1000000

nextNumber :: Int -> Int
nextNumber n = case n `divMod` 2 of
   (k,0) -> k
   _     -> 3*n + 1

sequenceLength :: Int -> Int
sequenceLength n = sl 1 n where
  sl k 1 = k
  sl k x = sl (k + 1) (nextNumber x)

longestSequence :: Int
longestSequence = testValues 1 0 0 where
  testValues number !longest !longestNum
    | number > searchTo     = longestNum
    | otherwise            = testValues (number + 1) longest' longestNum' where
    nlength  = sequenceLength number
    (longest',longestNum') = if nlength > longest
      then (nlength,number)
      else (longest,longestNum)

main :: IO ()
main = print longestSequence

Я скомпилировал этот кусок с ghc -O2 -fvia-C -optc-O3 -Wall euler.hs ион выполняется за 5 секунд, по сравнению с 80 в начале реализации.Он не использует Integer, но поскольку я на 64-битной машине, результаты могут быть обмануты.

Компилятор может распаковать все Int с в этом случае, что приводит к очень быстройкод.Он работает быстрее, чем все другие решения, которые я видел до сих пор, но C все еще быстрее.

Answer 5

Списки на Haskell основаны на куче, тогда как ваш код на C чрезвычайно сжатый и вообще не использует кучи.Вам необходимо провести рефакторинг для удаления зависимости от списков.