Haciendo Números eficientes en Haskell

Question

Me inspiré en esta publicación llamada "Only fast languages are interesting" para ver el problema que sugiere (sumando un par de millones de números de un vector) en Haskell y compararlo con sus resultados.

Soy un novato en Haskell, así que no sé realmente cómo sincronizar correctamente o cómo hacerlo de manera eficiente, mi primer intento de este problema fue el siguiente. Tenga en cuenta que no estoy usando números aleatorios en el vector ya que no estoy seguro de cómo hacerlo de una buena manera. También estoy imprimiendo cosas para asegurar una evaluación completa.

import System.TimeIt 

import Data.Vector as V 

vector :: IO (Vector Int) 
vector = do 
    let vec = V.replicate 3000000 10 
    print $ V.length vec 
    return vec 

sumit :: IO() 
sumit = do 
    vec <- vector 
    print $ V.sum vec 

time = timeIt sumit 

Cargando esto en GHCi y funcionando time me dice que tomó cerca de 0.22s a una duración de 3 millones de números y 2.69s por 30 millones de números.

En comparación con los resultados de los autores del blog de 0.02s y 0.18s en Lush, es bastante peor, lo que me lleva a pensar que esto se puede hacer de una mejor manera.

Nota: El código anterior necesita el paquete TimeIt para ejecutarse. cabal install timeit lo obtendrá por usted.

Answer 1

Antes que nada, tenga en cuenta que GHCi es un intérprete y no está diseñado para ser muy rápido. Para obtener resultados más útiles, debe compilar el código con las optimizaciones habilitadas. Esto puede hacer una gran diferencia.

Además, para cualquier referencia seria de código Haskell, recomiendo usar criterion. Utiliza varias técnicas estadísticas para garantizar que obtenga mediciones confiables.

Modifiqué su código para usar el criterio y eliminé las instrucciones de impresión para que no estuviéramos sincronizando la E/S.

import Criterion.Main 
import Data.Vector as V 

vector :: IO (Vector Int) 
vector = do 
    let vec = V.replicate 3000000 10 
    return vec 

sumit :: IO Int 
sumit = do 
    vec <- vector 
    return $ V.sum vec 

main = defaultMain [bench "sumit" $ whnfIO sumit] 

Compilación esto con -O2, consigo este resultado en un netbook bastante lento:

$ ghc --make -O2 Sum.hs 
$ ./Sum 
warming up 
estimating clock resolution... 
mean is 56.55146 us (10001 iterations) 
found 1136 outliers among 9999 samples (11.4%) 
    235 (2.4%) high mild 
    901 (9.0%) high severe 
estimating cost of a clock call... 
mean is 2.493841 us (38 iterations) 
found 4 outliers among 38 samples (10.5%) 
    2 (5.3%) high mild 
    2 (5.3%) high severe 

benchmarking sumit 
collecting 100 samples, 8 iterations each, in estimated 6.180620 s 
mean: 9.329556 ms, lb 9.222860 ms, ub 9.473564 ms, ci 0.950 
std dev: 628.0294 us, lb 439.1394 us, ub 1.045119 ms, ci 0.950 

Así que estoy recibiendo un promedio de poco más de 9 m con una desviación estándar de menos de una milésima de segundo . Para el caso de prueba más grande, obtengo unos 100 ms.

optimizaciones de Habilitación es especialmente importante cuando se utiliza el paquete vector, ya que hace un uso intensivo de fusión corriente, que en este caso es capaz de eliminar la estructura de datos completamente, convirtiendo su programa en un bucle eficiente, apretado.

También puede valer la pena experimentar con el nuevo generador de código basado en LLVM utilizando la opción -fllvm. It is apparently well-suited for numeric code.

Answer 2

Intente utilizar un vector sin caja, aunque no estoy seguro de si hace una diferencia notoria en este caso. Tenga en cuenta también que la comparación es ligeramente injusta, porque el paquete vector debe optimizar completamente el vector (esta optimización se llama fusión de secuencia).

Answer 3

El archivo original, sin compilar, entonces compilado sin optimización, entonces compilado con un simple indicador de optimización:

$ runhaskell boxed.hs 
3000000 
30000000 
CPU time: 0.35s 

$ ghc --make boxed.hs -o unoptimized 
$ ./unoptimized 
3000000 
30000000 
CPU time: 0.34s 



$ ghc --make -O2 boxed.hs 
$ ./boxed 
3000000 
30000000 
CPU time: 0.09s 

su archivo con import qualified Data.Vector.Unboxed as V en lugar de import qualified Data.Vector as V (Int es un tipo unboxable) - primero sin optimización luego con:

$ ghc --make unboxed.hs -o unoptimized 
$ ./unoptimized 
3000000 
30000000 
CPU time: 0.27s 


$ ghc --make -O2 unboxed.hs 
$ ./unboxed 
3000000 
30000000 
CPU time: 0.04s 

Así, compilar, optimizar ... y en lo posible el uso Data.Vector.Unboxed

Answer 4

Si utiliza suficientes vectores grandes, vectorial Sin Embalaje podría llegar a ser poco práctico. Para mí (perezoso) listas puras son más rápidos, si el tamaño del vector> 50000000:

import System.TimeIt 

sumit :: IO() 
sumit = print . sum $ replicate 50000000 10 

main :: IO() 
main = timeIt sumit 

consigo estos tiempos:

Unboxed Vectors 
CPU time: 1.00s 

List: 
CPU time: 0.70s 

Editar: He repetido el punto de referencia aplicando el Criterio y haciendo sumit puro. Código y los resultados de la siguiente manera:

Código:

import Criterion.Main 

sumit :: Int -> Int 
sumit m = sum $ replicate m 10 

main :: IO() 
main = defaultMain [bench "sumit" $ nf sumit 50000000] 

Resultados:

warming up 
estimating clock resolution... 
mean is 7.248078 us (80001 iterations) 
found 24509 outliers among 79999 samples (30.6%) 
    6044 (7.6%) low severe 
    18465 (23.1%) high severe 
estimating cost of a clock call... 
mean is 68.15917 ns (65 iterations) 
found 7 outliers among 65 samples (10.8%) 
    3 (4.6%) high mild 
    4 (6.2%) high severe 

benchmarking sumit 
collecting 100 samples, 1 iterations each, in estimated 46.07401 s 
mean: 451.0233 ms, lb 450.6641 ms, ub 451.5295 ms, ci 0.950 
std dev: 2.172022 ms, lb 1.674497 ms, ub 2.841110 ms, ci 0.950 

Parece que print hace una gran diferencia, ya que se debe esperar!