Haskell: equivalente eficiente de for loop?

loops recursion

Question

He estado haciendo algunos experimentos y aquí hay algo que encontré. Considere el siguiente programa C:

int main()
{
for(int i = 0;
i < 1000000;
++i)
{}
}

y el siguiente programa Haskell:

import System.IO
loop :: Int -> IO ()
loop n = if 0 == n then return () else loop (n-1)
main = loop 1000000

Aquí está la salida del time para el programa C anterior:

real 0m0.003s
user 0m0.000s
sys 0m0.000s

... y para el programa Haskell:

real 0m0.028s
user 0m0.027s
sys 0m0.000s

Al principio pensé que gcc detectó un bucle vacío y lo optimizó, pero después de aumentar el número de iteraciones, el tiempo de ejecución del programa también aumentó. Aquí están las salidas de time para ambos programas, con el número de iteraciones establecido en 10000000:

Versión C

real 0m0.024s
user 0m0.023s
sys 0m0.000s

Versión Haskell

real 0m0.245s
user 0m0.247s
sys 0m0.000s

Como puede ver, el programa Haskell es 10 veces más lento.

La pregunta es: ¿cuál es la alternativa eficiente al ciclo for en Haskell? Como acabamos de ver, la recursión simple ralentiza el programa unas 10 veces (y esto es probablemente con las optimizaciones de recursión de cola hechas).

Answer 1

Para las construcciones de bucle, a menudo tiene que escribir en el estilo Trabajador / Contenedor para ayudar a las optimizaciones de puntos de GHC en lugar de recurrir en el nivel de función externo.

Grigory Javadyan dijo en un comentario que la versión original se optimiza en -O3, espero que esta versión se detecte en -O2:

import System.IO
loop :: Int -> IO ()
loop n = go n
where
go n | n <= 0 = return ()
go n = go (n-1)
main = loop 1000000

Answer 2

En primer lugar, traducirías tu código C a esto,

main = go 0
where
go :: Int -> IO ()
go i | i < 1000000 = go (i+1)
| otherwise = return ()

que ghc optimiza para el programa vacío. Mueve el valor final a un registro, se compara con él y devuelve () :

Main_zdwa_info:
cmpq $1000000, %r14 # imm = 0xF4240
movl $1000000, %eax # imm = 0xF4240
cmovlq %rax, %r14
movq (%rbp), %rax
movl $ghczmprim_GHCziUnit_Z0T_closure+1, %ebx
jmpq *%rax # TAILCALL

que cuando se ejecuta:

$ time ./A
./A 0.00s user 0.00s system 88% cpu 0.004 total

no lleva tiempo

En general, sin embargo, GHC emite bucles equivalentes a , por ejemplo , GCC , para las funciones recursivas de cola. En particular, querrá compilar sus puntos de referencia numéricos con ghc -O2 -fllvm para obtener mejores resultados. Si no desea que sus programas estén optimizados, entonces ghc ejecutará felizmente exactamente el programa que especifique, que, en este caso, implica mucho trabajo redundante que se eliminaría con niveles de optimización más altos.

Para obtener más información sobre el análisis del rendimiento de bajo nivel de los programas Haskell, verifique RWH ch25.