¿Cómo mejorar el rendimiento de este programa Haskell?

Question

Estoy trabajando en los problemas en Project Euler como una forma de aprender Haskell, y me parece que mis programas son mucho más lentos que una versión C comparable, incluso cuando se compilan. ¿Qué puedo hacer para acelerar mis programas Haskell?

Por ejemplo, mi solución de fuerza bruta para Problem 14 es:

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 

que toma alrededor de 220 segundos, mientras que una versión "equivalente" fuerza bruta C sólo toma 1,2 segundos.

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

¿Qué estoy haciendo mal? ¿O soy ingenuo al pensar que Haskell podría incluso acercarse a la velocidad de C?

(Estoy compilando la versión C con gcc -O2, y la versión Haskell con ghc --make -O).

Answer 1

Para fines de prueba Acabo de configurar searchTo = 100000. El tiempo tomado es 7.34s. Unos pocos modificación conduce a alguna gran mejora:

1. utilizar un Integer en lugar de Int64. Esto mejora el tiempo a 1.75s.

2. Utilice un acumulador (no necesita sequenceLength para ser flojo ¿no?) 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. reescribir el nextNumber usando quotRem, evitando así el cálculo de la división dos veces (una vez en even y una vez en 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 en lugar de maximumBy. El problema de maximumBy . comparing es que la función sequenceLength se llama más de una vez para cada valor. 0.32s.

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

---

Nota:

• comprobar la hora de compilar con ghc -O y correr con +RTS -s)
• Mi máquina está funcionando en Mac OS X 10.6. La versión de GHC es 6.12.2. El archivo compilado está en la arquitectura i386)
• El problema C se ejecuta en 0.078s con el parámetro correspondiente. Se compila con gcc -O3 -m32.

Answer 2

Las listas de Haskell están basadas en montones, mientras que su código C es extremadamente ajustado y no utiliza ningún montón. Necesita refactorizar para eliminar la dependencia de las listas.

Answer 3

La comparación puede estar volviendo a aumentar la secuencia demasiado. Este es mi mejor versión:

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 respuesta y el tiempo son más lentos que C, pero utiliza arbitraria de enteros de precisión:

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

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

Answer 4

Incluso si estoy un poco tarde, aquí es mío, Eliminé la dependencia de las listas y esta solución tampoco usa ningún montón.

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

he recopilado esta pieza con ghc -O2 -fvia-C -optc-O3 -Wall euler.hs y se ejecuta en 5 segundos, en comparación con el 80 de la aplicación que se iniciará. No usa Integer, pero debido a que estoy en una máquina de 64 bits, los resultados pueden ser engañados.

El compilador puede unbox todos los int en este caso, lo que resulta en un código muy rápido. Funciona más rápido que todas las otras soluciones que he visto hasta ahora, pero C es aún más rápido.

Answer 5

Aunque esto ya es bastante antiguo, permítanme decirlo, hay un punto crucial que no se ha abordado anteriormente.

Primero, los tiempos de los diferentes programas en mi caja. Dado que estoy en un sistema Linux de 64 bits, muestran características algo diferentes: usar Integer en lugar de Int64 no mejora el rendimiento como lo haría con un GHC de 32 bits, donde cada operación Int64 incurriría en el costo de una llamada C mientras que los cálculos con Integer s ajustados en enteros de 32 bits con signo no necesitan una llamada externa (dado que solo unas pocas operaciones exceden ese rango aquí, Integer es la mejor opción en un GHC de 32 bits).

• C: 0,3 segundos
• original Haskell: 14,24 segundos, utilizando Integer en lugar de Int64: 33.96 segundos
• versión mejorada de KennyTM: 5.55 segundos, utilizando Int: 1,85 segundos
• versión de Chris Kuklewicz: 5,73 segundos, usando Int: 1.90 segundos
• Versión de FUZxxl: 3.56 segundos, usando quotRem en lugar de divMod: 1.79 segundos

¿Qué tenemos?

1. calcular la longitud de un acumulador por lo que el compilador puede transformarlo (básicamente) en un bucle
2. No volver a calcular la secuencia de longitudes para las comparaciones
3. No utilice div resp. divMod cuando no es necesario, quot resp. quotRem son mucho más rápidos

¿Qué falta?

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

Cualquier compilador de C He utilizado transforma la prueba j % 2 == 0 en un bit de enmascaramiento y no utiliza una instrucción de división. GHC no (todavía) hace eso.Entonces, probar even n o computar n `quotRem` 2 es una operación bastante costosa. Sustitución nextNumber en la versión de KennyTM Integer con

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

reduce su tiempo de ejecución a 3,25 segundos (Nota: para Integer, n `quot` 2 es más rápido que n `shiftR` 1, que se lleva a 12.69 segundos).

Haciendo lo mismo en la versión Int reduce su tiempo de ejecución a 0,41 segundos. Para Int s, el cambio de bit para división por 2 es un poco más rápido que la operación quot, reduciendo su tiempo de ejecución a 0.39 segundos.

La eliminación de la construcción de la lista (que no aparece en la versión C tampoco),

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 

produce un pequeño aumento de velocidad aún más, resultando en un tiempo de funcionamiento de 0,37 segundos.

Así que la versión de Haskell que está en estrecha correspondencia con la versión C no tarda mucho más, es un factor de ~ 1.3.

Bueno, seamos justos, hay una ineficiencia en la versión C que no está presente en las versiones de Haskell,

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

que aparece en el bucle interno. Al levantarlo del lazo interno en la versión C, se reduce su tiempo de funcionamiento a 0,27 segundos, lo que hace que el factor sea ~ 1,4.