desbordamiento de pila en OCaml y F #, pero no en Haskell

Question

He estado comparando para los idiomas divertidas diferentes de rapidez en la ejecución del siguiente programa: para i de 1 a 1000000 suma el producto i * (i sqrt)

Una de mis implementaciones (no la única) es construir una lista [1..1000000] y luego plegarla con una función específica.

El programa funciona bien y rápido en Haskell (incluso cuando se usa foldl y no foldl ') pero la pila se desborda en OCaml y F #.

Este es el código Haskell:

test = foldl (\ a b -> a + b * (sqrt b)) 0 

create 0 = [] 
create n = n:(create (n-1)) 

main = print (test (create 1000000)) 

Y aquí es el OCaml uno:

let test = List.fold_left (fun a b -> a +. (float_of_int b) *. (sqrt (float_of_int b))) 0. ;; 

let rec create = function 
    | 0 -> [] 
    | n -> n::(create (n-1)) ;; 

print_float (test (create 1000000));; 

¿Por qué los desbordamientos de pila de ejecución # OCaml/F?

Answer 1

El código de Haskell para create evalúa la lista perezosamente, es decir, como elementos son necesarios por foldl. La lista completa no es necesaria a la vez.

Por el contrario, F # y OCaml evalúan estrictamente la lista create, es decir, el código intenta generar toda la lista de una vez antes de pasarla a fold_left.

Una posibilidad en F # es utilizar una expresión seq en la función create: esto genera la lista perezosamente de la misma manera que Haskell. (No estoy seguro de si OCaml tiene una función equivalente.)

Answer 2

De esta forma, su función create no es recursiva. Puede volver a escribir en una forma recursiva de cola que no causa un desbordamiento de pila:

let rec create n l = 
    match n with 
    | 0 -> l 
    | n -> create (n-1) (n::l) 

print_float (test (create 1000000 []));; 

Answer 3

Otra forma de solucionar el código para que funcione en Fa # es el uso de expresiones de secuencia que también se generan con pereza y en una manera que no causa StackOverflow (esto no funcionará en OCaml, porque las expresiones de secuencia son específicas de F #). Aquí está el código:

let test nums = Seq.fold (fun a b -> 
    a + (float b) * (sqrt (float b))) 0.0 nums 

let rec create count = seq { 
    match count with 
    | 0 -> do() 
    | n -> yield n 
     yield! create (n-1) } 

printf "%f" (test (create 1000000));; 

No estoy seguro sobre el rendimiento, sin embargo, el compilador definitivamente hace una optimización en la función create, de manera que la iteración en la secuencia generada debe ser razonablemente rápido. Sin embargo, el objetivo de las expresiones de secuencia es principalmente legibilidad (ya que F # no es puro, te da mucho espacio para optimizaciones manuales si realmente las necesitas en comparación con Haskell que necesita optimizar el código puro que escribes). De todos modos, si tienes algunas pruebas, ¡puedes intentarlo!

Answer 4

En primer lugar, si está haciendo comparaciones de rendimiento para cosas numéricas, las listas no son la mejor opción. Pruebe un paquete como el vector para arreglos rápidos.

Y tenga en cuenta que puede hacerlo aún mejor en Haskell, gracias a la fusión de bucle. Al escribir la función de creación como una enumeración, el compilador puede combinar el paso de creación y el de plegado, en un solo bucle que no asigna estructuras de datos intermedias. La capacidad de hacer una fusión general como esta es exclusiva de GHC Haskell.

Voy a usar la biblioteca de vectores (fusión bucle basada en secuencias):

import qualified Data.Vector as V 

test = V.foldl (\ a b -> a + b * sqrt b) 0 

create n = (V.enumFromTo 1 n) 

main = print (test (create 1000000)) 

Ahora, antes de que, con su código, el compilador no es capaz de eliminar todas las listas, y terminamos con un interior como:

$wlgo :: Double# -> [Double] -> Double# 

$wlgo = 
    \ (ww_sww :: Double#) (w_swy :: [Double]) -> 
    case w_swy of _ { 
     [] -> ww_sww; 
     : x_aoY xs_aoZ -> 
     case x_aoY of _ { D# x1_aql -> 
     $wlgo 
      (+## 
      ww_sww (*## x1_aql (sqrtDouble# x1_aql))) 
      xs_aoZ 
     } 
    } 

$wcreate :: Double# -> [Double] 

$wcreate = 
    \ (ww_swp :: Double#) -> 
    case ==## ww_swp 0.0 of _ { 
     False -> 
     : 
      @ Double 
      (D# ww_swp) 
      ($wcreate (-## ww_swp 1.0)); 
     True -> [] @ Double 
    } 

Observe cómo hay dos bucles: cree la generación de una lista (diferida) y la vez que la consuma. Gracias a la pereza, el costo de esa lista es barato, por lo que se ejecuta en un respetable:

$ time ./C 
4.000004999999896e14 
./C 0.06s user 0.00s system 98% cpu 0.058 total 

Bajo la fusión, sin embargo, tenemos en cambio un solo bucle solamente!

main_$s$wfoldlM_loop :: Double# -> Double# -> Double# 

main_$s$wfoldlM_loop = 
    \ (sc_sYc :: Double#) (sc1_sYd :: Double#) -> 
    case <=## sc_sYc 1000000.5 of _ { 
     False -> sc1_sYd; 
     True -> 
     main_$s$wfoldlM_loop 
      (+## sc_sYc 1.0) 
      (+## 
      sc1_sYd (*## sc_sYc (sqrtDouble# sc_sYc))) 

GHC redujo nuestros pasos de creación y prueba en un solo bucle sin utilizar listas. Solo 2 dobles en registros. Y con la mitad de los bucles, que recorre casi dos veces más rápido:

$ ghc D.hs -Odph -fvia-C -optc-O3 -optc-march=native -fexcess-precision --make 
$ time ./D 
4.000005000001039e14 
./D 0.04s user 0.00s system 95% cpu 0.038 total 

Este es un buen ejemplo del poder que las garantías de pureza proporcionan - el compilador puede ser muy agresivos en Reording su código.

Answer 5

El programa funciona bien y rápido en Haskell (incluso cuando se usa foldl y no foldl ') pero la pila se desborda en OCaml y F #.

Su Haskell está utilizando listas perezosas pero su OCaml/F # está utilizando listas estrictas, por lo que sus programas son incomparables.

Fwiw, una solución utilizando secuencias en-demanda en F # es:

Seq.sumBy (fun i -> let i = float i in i * sqrt i) (seq {1..1000000})