F#vs OCaml: desbordamiento de pila

stack-overflow tail-recursion

Question

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

Hay una hormiga que puede caminar en una cuadrícula plana. La hormiga puede moverse un espacio a la 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 xey son mayores a 25 son inaccesibles para la hormiga. Por ejemplo, el punto (59,79) es inaccesible porque 5 + 9 + 7 + 9 = 30, que es mayor que 25. La pregunta es: ¿a cuántos puntos puede acceder la hormiga si comienza en (1000, 1000), incluyendo (1000, 1000) en sí mismo?

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

Limpio, mi resultado es el mismo que el de la implementación de leonardo, en D y C ++ . Comparando con la implementación de C ++ de leonardo, la versión de OCaml es aproximadamente 2 veces más lenta que C ++. Lo cual está bien, dado que leonardo usó una cola para eliminar la recursión.

Luego traduje el código a F # ... y esto es lo que obtuve:

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 las dos versiones de F # que tengo en mi máquina ... Por curiosidad, tomé el binario generado (ant.exe) y lo ejecuté en 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 la pila), pero lleva 84 segundos, es decir, 587 veces más lento que OCaml, oops.

Entonces este programa ...

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

¿Por qué?

EDITAR: La rareza continúa: al utilizar "--optimize + --checked-", el problema desaparece, pero solo en ArchLinux / Mono ; en Windows XP y Windows 7 / 64bit, incluso la versión optimizada de la pila binaria se desborda.

EDITACIÓN final : descubrí la respuesta yo mismo - ver a continuación.

Answer 1

Déjame intentar resumir la respuesta.

Hay 3 puntos por hacer:

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

Es muy común que una excepción de desbordamiento de pila sea el resultado de un vall recursivo. Si la llamada está en posición de cola, el compilador puede reconocerla y aplicar la optimización del tailcall, por lo tanto, las llamadas recursivas no ocuparán espacio en la pila. La optimización de llamada puede ocurrir en F #, en la CRL o en ambas:

Optimización de la cola CLR 1

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

F # tail calls 3

La explicación correcta para "falla en Windows, no en Linux" es, como otros dicen, el espacio de pila reservado por defecto en los dos sistemas operativos. O mejor, el espacio de pila reservado utilizado por los compiladores en 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 publicación en el blog http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx ) No lo recomendaría, 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 de OCaml en 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 de su código original?

Mi suposición sobre "--optimize +" es que aún causará que el código vuelva a aparecer, por lo tanto, seguirá fallando en Windows, pero mitigará el problema al hacer que el ejecutable se ejecute más rápido.

Finalmente, la solución definitiva es usar recursividad 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.

Answer 2

Resumen ejecutivo:

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

Era entonces hora de virar al F #.

• Traducí el código (traducción directa) a F #.
• Compilé en Windows y lo ejecuté, recibí un desbordamiento de pila.
• Tomé el binario en Linux y lo ejecuté bajo Mono.
• Funcionó, pero funciona muy lentamente (84 segundos).

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

• Intenté compilar con --optimize + --checked-
• La pila binaria aún se desbordó en Windows ...
• ... pero corre bien (y terminó en 0.5 segundos) en Linux / Mono.

Era hora de verificar el tamaño de la pila: en Windows, otra publicación SO señaló que está configurada de forma predeterminada en 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 funciona mucho mejor en Mono que en la no optimizada: 0,5 segundos frente a 84 segundos (aunque la opción --optimize + parece estar configurada de manera predeterminada, vea el comentario de Keith con "Expert F #" extraer). Probablemente tiene que ver con el recolector de basura de Mono, que de alguna manera fue llevado a extremos por la primera versión.

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

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

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

Entonces, moral de la historia:

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

PS Algunos comentarios adicionales del Dr. Jon Harrop:

... tuviste suerte de que OCaml no se desbordara también. Ya has identificado que los tamaños de pila reales varían entre plataformas. Otra faceta del mismo problema es que las diferentes implementaciones de lenguaje consumen espacio de pila a diferentes velocidades y tienen diferentes características de rendimiento en presencia de pilas profundas. OCaml, Mono y .NET usan representaciones de datos diferentes y algoritmos de GC que impactan estos resultados ... (a) OCaml usa enteros etiquetados para distinguir punteros, dando marcos compactos de pila, y recorrerá todo en la pila buscando punteros. El etiquetado esencialmente transmite la información suficiente para el tiempo de ejecución de OCaml para poder atravesar el montón (b) Mono trata las palabras en la pila de manera conservadora como punteros: si, como puntero, una palabra apuntara a un bloque asignado al montón entonces bloque se considera alcanzable. (c) No conozco el algoritmo de .NET, pero no me sorprendería si consumiera más espacio de la pila y aún cruzara cada palabra en la pila (¡sin duda sufre un rendimiento patológico del GC si un hilo no relacionado tiene una pila profunda!) ... Además, el uso de tuplas asignadas a montones significa que estará llenando rápidamente la generación de criaderos (por ejemplo, gen0) y, por lo tanto, haciendo que el GC atraviese esas pilas profundas a menudo ...