Jak poprawić wydajność tego programu Haskell?

Question

Zajmuję się problemami w Project Euler jako sposobie uczenia się Haskella, i uważam, że moje programy są dużo wolniejsze niż porównywalna wersja C, nawet jeśli zostały skompilowane. Co mogę zrobić, aby przyspieszyć swoje programy Haskell?

Na przykład, mój siłowych rozwiązanie Problem 14 jest:

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 

które trwa około 220 sekund, podczas gdy "równoważne" brute-force wersja C trwa tylko 1,2 sekundy.

#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; 
} 

Co robię źle? Czy może jestem naiwny sądzić, że Haskell może nawet zbliżyć się do prędkości C?

(Kompiluję wersję C z gcc -O2, a wersją Haskella z ghc --make -O).

Answer 1

Do celów testowych właśnie ustawiłem searchTo = 100000. Pobrany czas to 7,34s. Kilka modyfikacja prowadzi do jakiejś wielkiej poprawy:

1. Integer użyć zamiast Int64. To poprawia czas na 1.75s.

2. Użyj akumulatora (nie potrzebujesz sekwencji długości, aby być leniwym w prawo?) 1,54s.

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

3. przepisać nextNumber pomocą quotRem, unikając w ten sposób obliczenie podziału dwukrotnie (raz even i gdy w div). 1,27 s.

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

4. Zastosowanie Schwartzian transform zamiast maximumBy. Problem z maximumBy . comparing polega na tym, że funkcja sequenceLength jest wywoływana więcej niż raz dla każdej wartości. 0.32s.

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

---

Uwaga:

• sprawdzić czas kompilacji z ghc -O i biegać z +RTS -s)
• Moja maszyna działa na Mac OS X 10.6. Wersja GHC to 6.12.2. Skompilowany plik ma architekturę i386).
• Problem z C występuje pod adresem 0.078s z odpowiednim parametrem. Jest skompilowany z gcc -O3 -m32.

Answer 2

Listy Haskella są oparte na sterty, natomiast kod C jest wyjątkowo zwarty i nie używa go wcale. Musisz zmienić, aby usunąć zależność od list.

Answer 3

Porównywanie może powodować zbyt długi czas przetwarzania. To moja najlepsza wersja:

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 

Odpowiedź i terminy są wolniejsze niż C, ale ma wykorzystywać dowolną dokładnością Integer:

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

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

Answer 4

Nawet jeśli jestem trochę późno, tutaj jest moje, Usunąłem zależność od list, a to rozwiązanie w ogóle nie używa żadnych stert.

{-# 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 

Skompilowałem ten kawałek z ghc -O2 -fvia-C -optc-O3 -Wall euler.hs i działa w 5 sekund, w porównaniu do 80 z realizacji początku. Nie używa ona Integer, ale ponieważ jestem na 64-bitowej maszynie, wyniki mogą zostać oszukane.

Kompilator może rozpakować wszystkie pliki Int w tym przypadku, co spowoduje bardzo szybki kod. Działa szybciej niż wszystkie inne rozwiązania, które dotychczas widziałem, ale C jest jeszcze szybsze.

Answer 5

Chociaż jest to już dość stary, pozwól mi zadzwonić, jest jeden kluczowy punkt, który nie był wcześniej omawiany.

Po pierwsze, czasy różnych programów na moim pudełku. Ponieważ jestem w 64-bitowym systemie Linux, mają nieco inne cechy: użycie Integer zamiast Int64 nie poprawia wydajności, tak jak w przypadku 32-bitowego GHC, gdzie każda operacja Int64 wiązałaby się z kosztami wywołania C podczas gdy obliczenia z Integer dopasowaniem w podpisanych 32-bitowych liczbach całkowitych nie wymagają wywołania obcego (ponieważ tylko kilka operacji przekracza ten zakres tutaj, Integer jest lepszym wyborem w 32-bitowym GHC).

• C: 0,3 sekundy
• Original Haskell: 14,24 sekundy, używając Integer zamiast Int64: 33.96 sekund
• KennyTM jest ulepszona wersja: 5.55 sekund, używając Int: 1.85 sekund
• wersja Chrisa którym współpracowali między innymi za: 5,73 sekund, używając Int: 1.90 sekund
• Wersja FUZxxl: 3,56 sekundy, używając quotRem zamiast divMod: 1,79 sekundy

Co więc mamy?

1. Oblicz długość z akumulatora tak kompilator może go przekształcić (zasadniczo) do pętli
2. Nie przeliczyć sekwencja o długości do porównań
3. Nie używaj div wzgl. divMod, gdy nie jest to konieczne, quot lub quotRem są znacznie szybsze

Czego jeszcze brakuje?

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

kompilatora C I stosuje przekształca test j % 2 == 0 do bitów maskowania i nie korzysta z instrukcją podziału. GHC jeszcze tego nie robi.Więc testowanie even n lub obliczanie n `quotRem` 2 jest dość kosztowną operacją. Wymiana nextNumber w KennyTM za Integer wersji z

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

zmniejsza czas pracy do 3,25 sekundy (Uwaga: dla Integer, n `quot` 2 jest szybszy niż n `shiftR` 1, które odbywają 12,69 sekund).

W ten sam sposób w wersji Int skraca się czas jego działania do 0,41 sekundy. Dla s, przesunięcie bitowe dla dzielenia przez 2 jest nieco szybsze niż operacja quot, skracając czas jego działania do 0.39 sekundy.

Wyeliminowanie konstrukcję listy (które nie występuje w wersji albo 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 

daje dalsze małe przyspieszenie, powodując czasie trwania 0,37 sekund.

Tak więc wersja Haskella, która jest w ścisłej korespondencji z wersją C, nie zajmuje dużo dłużej, jest to współczynnik ~ 1,3.

Cóż, bądźmy fair, nie ma nieskuteczność w wersji C, która nie jest obecna w wersjach Haskell,

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

pojawiające się w wewnętrznej pętli. Podnoszenie tego z wewnętrznej pętli w wersji C skraca czas jego działania do 0,27 sekundy, tworząc współczynnik ~ 1,4.