Optimización de GHC: Conjetura de Collatz

Question

He escrito el código para Project Euler's Challenge 14, en ambos Haskell y C++ (enlaces de 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 dentro de factor de 2 o 3 de la versión de C++)?

---

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:

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

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

Answer 1

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

• Se utiliza un pliegue para encontrar la longitud máxima de la cadena, para eso la matriz se debe convertir a una lista de asociación, eso requiere tiempo y la asignación de la versión de C++ no es necesaria.
• Usted usa even y div para las pruebas resp dividiendo por 2. Estas son lentas. 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 .
• Utiliza 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.

incorporación que en la puesta en práctica, consigo

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 de 10 millones de dólares):

$ 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: Este código sólo funciona en 64 bits GHC (así, en particular, en Windows, necesita GHC-7.6.1 o posterior, GHCs anteriores eran de 32 bits, incluso en Windows de 64 bits) ya que los elementos de la cadena intermedia exceden el rango de 32 bits. En 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 GHCs de 32 bits (llamadas rápidas extranjeras, pero aún mucho más lentas que las operaciones directas de la máquina).

Answer 2

El sitio de ideone está utilizando un ghc 6.8.2, que se está haciendo bastante viejo. 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 sólo 2,7 veces más lento que el ++ 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)