haskell - pseudocodigo - función collatz

Optimización de GHC: conjetura de Collatz

Question

He escrito el código para el Proyecto Euler''s Challenge 14 , tanto en Haskell como en C ++ (enlaces ideone). Ambos recuerdan cualquier cálculo que hayan hecho previamente en una matriz.

Usando ghc -O2 y g++ -O3 respectivamente, el C ++ funciona 10-15 veces más rápido que la versión de Haskell.

Aunque entiendo que la versión de Haskell puede funcionar más despacio, y que Haskell es un lenguaje más agradable para escribir, sería bueno saber algunos cambios de código que puedo hacer en la versión de Haskell para hacerlo correr más rápido (idealmente en un factor de 2 o 3 de la versión C ++)?

El código Haskell está aquí:

import Data.Array
import Data.Word
import Data.List
collatz_array =
let
upperbound = 1000000
a = array (1, upperbound) [(i :: Word64, f i :: Int) | i <- [1..upperbound]]
f i = i `seq`
let
check_f i = i `seq` if i <= upperbound then a ! i else f i
in
if (i == 1) then 0 else (check_f ((if (even i) then i else 3 * i + 1) `div` 2)) + 1
in a
main =
putStrLn $ show $
foldl1'' (/(x1,x2) (y1,y2) -> if (x2 >= y2) then (x1, x2) else (y1, y2)) $! (assocs collatz_array)

Editar:

Ahora también he hecho una versión usando matrices mutables sin caja. Todavía es 5 veces más lento que la versión C ++, pero una mejora significativa. El código está en ideone aquí .

Me gustaría conocer las mejoras en la versión de matriz mutable que la acerque a la versión de C ++.

Answer 1

El sitio de ideone está usando un ghc 6.8.2, que está envejeciendo bastante. En ghc versión 7.4.1, la diferencia es mucho menor.

Con ghc:

$ ghc -O2 euler14.hs && time ./euler14
(837799,329)
./euler14 0.63s user 0.04s system 98% cpu 0.685 total

Con g ++ 4.7.0:

$ g++ --std=c++0x -O3 euler14.cpp && time ./a.out
8400511 429
./a.out 0.24s user 0.01s system 99% cpu 0.252 total

Para mí, la versión ghc es solo 2.7 veces más lenta que la versión c ++. Además, los dos programas no están dando el mismo resultado ... (no es una buena señal, especialmente para la evaluación comparativa)

Answer 2

Algunos problemas con su código (matriz mutable):

• Usas un pliegue para encontrar la longitud máxima de la cadena, para eso la matriz debe convertirse en una lista de asociación, eso lleva tiempo y no necesita la asignación de la versión de C ++.
• Usas even y div para probar resp dividiendo por 2. Estos son lentos. g ++ optimiza ambas operaciones para las operaciones de bits más rápidas (en plataformas donde supuestamente es más rápido, al menos), pero GHC no hace estas optimizaciones de bajo nivel (todavía), por lo que por el momento, tienen que hacerse a mano .
• readArray y writeArray . La verificación adicional de límites que no se realiza en el código C ++ también lleva tiempo, una vez que se resuelven los otros problemas, eso equivale a una parte significativa del tiempo de ejecución (aproximadamente el 25% en mi caja), ya que están listos muchas lecturas y escrituras en el algoritmo.

Incorporando eso en la implementación, obtengo

import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Data.Bits
collatz_array :: ST s (STUArray s Int Int)
collatz_array = do
let upper = 10000000
arr <- newArray (0,upper) 0
unsafeWrite arr 2 1
let check i
| upper < i = return arr
| i .&. 1 == 0 = do
l <- unsafeRead arr (i `shiftR` 1)
unsafeWrite arr i (l+1)
check (i+1)
| otherwise = do
let j = (3*i+1) `shiftR` 1
find k l
| upper < k = find (next k) $! l+1
| k < i = do
m <- unsafeRead arr k
return (m+l)
| otherwise = do
m <- unsafeRead arr k
if m == 0
then do
n <- find (next k) 1
unsafeWrite arr k n
return (n+l)
else return (m+l)
where
next h
| h .&. 1 == 0 = h `shiftR` 1
| otherwise = (3*h+1) `shiftR` 1
l <- find j 1
unsafeWrite arr i l
check (i+1)
check 3
collatz_max :: ST s (Int,Int)
collatz_max = do
car <- collatz_array
(_,upper) <- getBounds car
let find w m i
| upper < i = return (w,m)
| otherwise = do
l <- unsafeRead car i
if m < l
then find i l (i+1)
else find w m (i+1)
find 1 0 2
main :: IO ()
main = print (runST collatz_max)

Y los tiempos (ambos por 10 millones):

$ time ./cccoll
8400511 429
real 0m0.210s
user 0m0.200s
sys 0m0.009s
$ time ./stcoll
(8400511,429)
real 0m0.341s
user 0m0.307s
sys 0m0.033s

que no se ve tan mal.

Nota importante: ese código solo funciona en GHC de 64 bits (por lo que, en particular, en Windows, necesita ghc-7.6.1 o posterior, los GHC anteriores eran de 32 bits incluso en Windows de 64 bits) ya que los elementos de cadena intermedios exceden 32 rango de bits. En los sistemas de 32 bits, uno debería usar Integer o un tipo entero de 64 bits ( Int64 o Word64 ) para seguir las cadenas, a un costo de rendimiento drástico, ya que las operaciones primitivas de 64 bits (aritmética y cambios) se implementan como llamadas externas a funciones C en GHC de 32 bits (llamadas extranjeras rápidas , pero aún mucho más lentas que las operaciones directas de máquina).