Come migliorare le prestazioni di questo programma Haskell?

Question

Sto lavorando ai problemi in Project Euler come metodo per apprendere Haskell, e trovo che i miei programmi siano molto più lenti di una versione C paragonabile, anche quando sono compilati. Cosa posso fare per velocizzare i miei programmi Haskell?

Per esempio, la mia soluzione a forza bruta per Problem 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 

che in circa 220 secondi, mentre una versione "equivalente" a forza bruta C richiede solo 1,2 secondi.

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

Cosa sto facendo male? O sono ingenuo pensare che Haskell potrebbe persino avvicinarsi alla velocità di C?

(Sto compilando la versione C con gcc -O2 e la versione Haskell con ghc --make -O).

Answer 1

Per scopi di test, ho appena impostato searchTo = 100000. Il tempo impiegato è 7.34s. Una modifica poche porta a qualche grande miglioramento:

1. Utilizzare un Integer invece di Int64. Ciò migliora il tempo a 1,75.

2. Utilizzare un accumulatore (non è necessario che sequenceLength sia pigro?) 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. riscrivere il nextNumber utilizzando quotRem, evitando così il calcolo della divisione per due volte (una volta in even e una volta in div). 1.27s.

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

4. Uso Schwartzian transform invece di maximumBy. Il problema di maximumBy . comparing è che la funzione sequenceLength viene chiamata più di una volta per ogni valore. 0,32 secondi.

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

---

Nota:

• ho controllare il tempo per la compilazione con ghc -O e correre con +RTS -s)
• La mia macchina è in esecuzione su Mac OS X 10.6. La versione di GHC è 6.12.2. Il file compilato si trova nell'architettura i386.)
• Il problema C viene eseguito a 0.078s con il parametro corrispondente. È compilato con gcc -O3 -m32.

Answer 2

Gli elenchi di Haskell sono basati su heap, mentre il codice C è estremamente stretto e non consente l'utilizzo di alcun heap. Devi refactoring per rimuovere la dipendenza dagli elenchi.

Answer 3

Il confronto può essere una sequenza di ricalcolo troppo lunga. Questa è la mia migliore versione:

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 

La risposta e tempi sono più lento di C, ma fa uso arbitrario di precisione Integer:

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

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

Answer 4

Anche se sono un po 'in ritardo, qui è il mio, Ho rimosso la dipendenza dalle liste e questa soluzione non utilizza nemmeno l'heap.

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

ho compilato questo pezzo con ghc -O2 -fvia-C -optc-O3 -Wall euler.hs e funziona in 5 secondi, rispetto ai 80 del di attuazione che inizia. Non utilizza Integer, ma poiché sono su una macchina a 64 bit, i risultati potrebbero essere ingannati.

Il compilatore può annullare la posta in arrivo di tutti gli Int in questo caso, risultando in un codice veramente veloce. Funziona più velocemente di tutte le altre soluzioni che ho visto finora, ma C è ancora più veloce.

Answer 5

Anche se questo è già piuttosto vecchio, fammi entrare, c'è un punto cruciale che non è stato affrontato prima.

In primo luogo, i tempi dei diversi programmi sulla mia scatola. Dato che sono su un sistema Linux a 64 bit, mostrano caratteristiche un po 'diverse: usare Integer anziché Int64 non migliora le prestazioni come farebbe con un GHC a 32 bit, dove ogni operazione comporterebbe il costo di una chiamata C mentre i calcoli con l'adattamento Integer in interi a 32 bit con segno non richiedono una chiamata esterna (poiché solo poche operazioni superano tale intervallo qui, Integer è la scelta migliore su un GHC a 32 bit).

• C: 0,3 secondi
• originale Haskell: 14.24 secondi, utilizzando Integer invece di Int64: 33.96 secondi
• versione migliorata del KennyTM: 5.55 secondi, utilizzando Int: 1.85 secondi
• versione di Chris Kuklewicz: 5.73 secondi, utilizzando Int: 1,90 secondi
• versione di FUZxxl: 3,56 secondi, utilizzando quotRem anziché divMod: 1,79 secondi

Allora, che cosa abbiamo?

1. calcolare la lunghezza di un accumulatore in modo che il compilatore può trasformarlo (in pratica) in un ciclo
2. Non ricalcolare la sequenza di lunghezze per i confronti
3. Non utilizzare div resp. divMod quando non è necessario, quot risp. quotRem sono molto più veloci

Cosa manca ancora?

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

Qualunque compilatore C Ho usato trasforma il test j % 2 == 0 in una po-mascheratura e non usa un'istruzione divisione. GHC non lo fa (ancora).Quindi testare even n o calcolare n `quotRem` 2 è un'operazione piuttosto costosa. Sostituzione nextNumber nella versione di KennyTM Integer con

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

riduce il suo tempo di esecuzione a 3,25 secondi (Nota: Per Integer, n `quot` 2 è più veloce di n `shiftR` 1, che prende 12,69 secondi).

Fare lo stesso nella versione Int riduce il tempo di esecuzione a 0,41 secondi. Per Int s, lo spostamento di bit per divisione per 2 è un po 'più veloce rispetto all'operazione quot, riducendo il tempo di esecuzione a 0,39 secondi.

Eliminando la costruzione della lista (che non appare nella versione C o),

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 

cede un ulteriore piccolo aumento di velocità, risultando in un tempo di esecuzione di 0,37 secondi.

Quindi la versione Haskell che è in stretta corrispondenza con la versione C non richiede molto più tempo, è un fattore di ~ 1.3.

Bene, cerchiamo di essere onesti, c'è un inefficienza nella versione C che non è presente nelle versioni Haskell,

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

che appare nel ciclo interno. Sollevandolo dall'anello interno nella versione C si riduce il tempo di esecuzione a 0,27 secondi, rendendo il fattore ~ ​​1,4.