Haskell - equivalente eficiente de for loop?

Question

He estado haciendo algunos experimentos y aquí hay algo que encontré. Considere el siguiente programa en 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 de time para el programa C por encima de:

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 tanto de los programas, con el número de iteraciones fijados a 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 se puede ver, el Haskell el programa es 10 veces más lento.

Pregunta es: ¿cuál es la alternativa eficiente al lazo 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

En primer lugar, se había traducir el 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. Se mueve el valor final en un registro, se compara contra ella, 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 el funcionamiento:

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

no tiene tiempo.

---

En general, sin embargo, GHC emite equivalent loops to e.g. GCC, para funciones de cola-recursivo. 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 de Haskell, comprobar RWH ch25.

Answer 2

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

Grigory Javadyan ha dicho en un comentario que la versión original se ha optimizado a cabo a -O3, yo esperaría que esta versión se detecta 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