F # vs OCaml: Desbordamiento de pila

Question

F # vs OCaml: Desbordamiento de pila

Recientemente encontré una presentación sobre F# para programadores de Python, y después de verla, decidí implementar una solución para el "rompecabezas de hormigas" por mi cuenta.

Hay una hormiga que puede caminar en una cuadrícula plana. La hormiga puede mover un espacio a la vez izquierda, derecha, arriba o abajo. Es decir, desde la celda (x, y) la hormiga puede ir a las células (x+1, y), (x-1, y), (x, y+1), y (x, y-1). Los puntos donde la suma de los dígitos de las coordenadas x e y es mayor que 25 son inaccesibles a la hormiga. Por ejemplo, el punto (59,79) es inaccesible porque 5 + 9 + 7 + 9 = 30, que es mayor que 25. La pregunta es: ¿Cuántos puntos puede acceder la hormiga si comienza en (1000, 1000), incluyendo (1000, 1000) en sí?

Implementé mi solución en 30 líneas de OCaml primero , y lo probé:

$ ocamlopt -unsafe -rectypes -inline 1000 -o puzzle ant.ml
$ time ./puzzle
Points: 148848

real    0m0.143s
user    0m0.127s
sys     0m0.013s

Neat, mi resultado es el mismo que el de la implementación de leonardo, en D y C++. En comparación con la implementación de C++ de leonardo, la versión OCaml se ejecuta aproximadamente 2 veces más lento que C++. Lo cual está bien, dado que Leonardo usó una cola para eliminar la recursividad.

Entonces traduje el código a F# ... y esto es lo que tengo:

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/FSharp-2.0.0.0/bin/fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 2.0.0.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException.
Quit

Thanassis@HOME /g/Tmp/ant.fsharp
$ /g/Program\ Files/Microsoft\ F#/v4.0/Fsc.exe ant.fs
Microsoft (R) F# 2.0 Compiler build 4.0.30319.1
Copyright (c) Microsoft Corporation. All Rights Reserved.

Thanassis@HOME /g/Tmp/ant.fsharp
$ ./ant.exe

Process is terminated due to StackOverflowException

Desbordamiento de pila... con ambas versiones de F# tengo en mi máquina... Por curiosidad, entonces tomé el binario generado (ant.exe) y ejecutarlo bajo Arch Linux/Mono:

$ mono -V | head -1
Mono JIT compiler version 2.10.5 (tarball Fri Sep  9 06:34:36 UTC 2011)

$ time mono ./ant.exe
Points: 148848

real    1m24.298s
user    0m0.567s
sys     0m0.027s

Sorprendentemente, se ejecuta bajo Mono 2.10.5 (es decir, sin desbordamiento de pila), pero tarda 84 segundos, es decir, 587 veces más lento que OCaml-oops.

Así que este programa...

funciona bien bajo OCaml
no funciona en absoluto con. NET/F #
funciona, pero es muy lento, bajo Mono/F#.

¿Por qué?

EDIT: Weirdness continues - Using "optimize optimize+ checked checked-" makes the problem disappear, but only under ArchLinux/Mono; under Windows XP and Windows 7/64bit, even the optimized version of the binary stack overflows.

Final EDIT : Encontré la respuesta yo mismo - ver más abajo.

60

stack-overflow tail-recursion f#ocaml

Author: ttsiodras, 2011-09-24

Source

2 answers

Permítanme tratar de resumir la respuesta.

Hay 3 puntos a hacer:

problema: el desbordamiento de pila ocurre en una función recursiva
solo sucede bajo Windows: en Linux, para el tamaño proble examinado, funciona
el mismo (o similar) código en OCaml funciona
optimize + compiler flag, para el tamaño proble examinado, funciona

Es muy común que una excepción de Desbordamiento de pila sea el resultado de una vall recursiva. Si la llamada está en cola position, el compilador puede reconocerlo y aplicar la optimización tailcall, por lo tanto, las llamadas recursivas no ocuparán espacio en la pila. La optimización de Tailcall puede ocurrir en F#, en la CRL, o en ambos:

Optimización de cola de CLR1

F # recursión( más general) 2

F # llamadas de cola3

La explicación correcta para "falla en windows, no en linux" es, como se dijo, el espacio de pila reservado por defecto en los dos sistemas operativos. O mejor, el espacio de pila reservado utilizado por los compiladores bajo los dos sistemas operativos. Por defecto, VC++ reserva solo 1MB de espacio de pila. El CLR es (probablemente) compilado con VC++, por lo que tiene esta limitación. El espacio reservado de la pila se puede aumentar en tiempo de compilación, pero no estoy seguro de si se puede modificar en ejecutables compilados.

EDITAR: resulta que se puede hacer (ver esta entrada del bloghttp://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx) No lo haría recomiendo, pero en situaciones extremas, al menos es posible.

La versión OCaml puede funcionar porque se ejecutó bajo Linux. Sin embargo, sería interesante probar también la versión OCaml bajo Windows. Sé que el compilador OCaml es más agresivo en la optimización de llamadas de cola que F#.. ¿podría incluso extraer una función de cola recusable de su código original?

Mi conjetura sobre "optimize optimize+" es que todavía hará que el código se repita, por lo tanto, todavía fallará bajo Windows, pero mitigará el problema haciendo que el ejecutable se ejecute más rápido.

Finalmente, la solución definitiva es usar la recursión de cola (reescribiendo el código o realizando una optimización agresiva del compilador); es una buena manera de evitar el problema de desbordamiento de pila con funciones recursivas.

8

Author: Lorenzo Dematté,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-09-30 10:17:17

score 70 · Accepted Answer

Resumen:

Escribí una implementación simple de un algoritmo... eso no era recursivo de cola.
Lo compilé con OCaml bajo Linux.
funcionó bien, y terminó en 0.14 segundos.

Era entonces el momento de portar a F#.

Traduje el código (traducción directa) a F#.
Compilé bajo Windows, y lo ejecuté - tengo un desbordamiento de pila.
Tomé el binario bajo Linux, y lo ejecuté bajo Mono.
It trabajado, pero correr muy lentamente (84 segundos).

Luego publiqué en Stack Overflow, pero algunas personas decidieron cerrar la pregunta (suspiro).

He intentado compilar con optimize optimize + checked checked -
La pila binaria aún se desbordaba bajo Windows...
...pero funciona bien (y terminó en 0.5 segundos) bajo Linux/Mono.

Era hora de comprobar el tamaño de la pila: Bajo Windows, otro post de SO señaló que está configurado por defecto a 1MB. Bajo Linux, "uname-s" y una compilación de un programa de prueba mostraron claramente que es 8MB.

Esto explicaba por qué el programa funcionaba bajo Linux y no bajo Windows (el programa usaba más de 1MB de pila). No explica por qué la versión optimizada se ejecuta mucho mejor bajo Mono que la no optimizada: 0.5 segundos vs 84 segundos (a pesar de que el optimize optimize+ parece estar configurado por defecto, ver comentario de Keith con "Experto F#" extracto). Probablemente tiene que ver con el recolector de basura de Mono, que de alguna manera fue llevado a los extremos por la 1ª versión.

La diferencia entre los tiempos de ejecución de Linux/OCaml y Linux/Mono/F# (0.14 vs 0.5) se debe a la forma sencilla en que lo medí: "tiempo ./binario ..."también mide el tiempo de inicio, lo cual es significativo para Mono/. NET (bueno, significativo para este pequeño problema simple).

De todos modos, para resolver esto de una vez por todas, yo escribí una versión recursiva de cola - donde la llamada recursiva al final de la función es transformado en un bucle (y por lo tanto, no es necesario el uso de la pila - al menos en teoría).

La nueva versión también funciona bien bajo Windows, y terminó en 0.5 segundos.

Entonces, moraleja de la historia:

Tenga cuidado con el uso de su pila, especialmente si usa mucho y se ejecuta bajo Windows. Use EDITBIN con la opción / STACK para establecer sus binarios a tamaños de pila más grandes, o mejor aún, escriba su código de una manera que no dependa de usar demasiado pila.
OCaml puede ser mejor en la eliminación de recursión de cola que F#-o su recolector de basura está haciendo un mejor trabajo en este problema en particular.
No te desesperes...gente grosera cerrando tu Pila de preguntas de desbordamiento, la gente buena las contrarrestará al final - si las preguntas son realmente buenas: -)

P.d. Algunas aportaciones adicionales del Dr. Jon Harrop:

...tuviste suerte de que OCaml no se desbordara también. Usted ya ha identificado que los tamaños reales de la pila varían entre las plataformas. Otra faceta del mismo problema es que diferentes implementaciones de lenguaje coma el espacio de la pila a diferentes velocidades y tenga un rendimiento diferente características en presencia de pilas profundas. OCaml, Mono y. NET todos utilizan diferentes representaciones de datos y algoritmos GC que impactan estos resultados... (a) OCaml utiliza enteros etiquetados para distinguir punteros, dando marcos de pila compactos, y recorrerá todo en la pila buscando consejos. El etiquetado esencialmente transmite la información suficiente para que el tiempo de ejecución de OCaml pueda atravesar el montón (b) Mono trata palabras en la pila de forma conservadora como punteros: si, como puntero, una palabra en un bloque asignado a un montón, ese bloque se considera accesible. (c) No conozco el algoritmo de. NET, pero no me sorprendería si comiera stack espacio más rápido y todavía atravesó cada palabra en la pila (sin duda sufre el rendimiento patológico del GC si un no relacionado el hilo tiene un deep stack!)... Además, el uso de tuplas asignadas a montones significa que llenar la generación del vivero (por ejemplo, gen0) rápidamente y, por lo tanto, causando que el GC atraviese esas pilas profundas a menudo...