F# vs OCaml : Stack overflow

Question

J'ai récemment trouvé une présentation sur F# pour les programmeurs Python et après l'avoir regardé, j'ai décidé de mettre en œuvre une solution au "puzzle des fourmis" par moi-même.

Il existe une fourmi qui peut se déplacer sur une grille planaire. La fourmi peut se déplacer d'un espace à la fois vers la gauche, la droite, le haut ou le bas. Autrement dit, à partir de la cellule (x, y), la fourmi peut se rendre dans les cellules (x+1, y), (x-1, y), (x, y+1) et (x, y-1). Les points où la somme des chiffres des coordonnées x et y est supérieure à 25 sont inaccessibles à la fourmi. Par exemple, le point (59,79) est inaccessible car 5 + 9 + 7 + 9 = 30, ce qui est supérieur à 25. La question est la suivante : combien de points la fourmi peut-elle atteindre si elle commence à (1000, 1000), y compris (1000, 1000) elle-même ?

J'ai implémenté ma solution en 30 lignes de OCaml d'abord et je l'ai essayé :

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

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

Neat, mon résultat est le même que celui de l'implémentation de leonardo, en D et C++ . En comparant avec l'implémentation C++ de Leonardo, la version OCaml fonctionne environ 2 fois plus lentement que C++. Ce qui est correct, étant donné que Leonardo a utilisé une file d'attente pour supprimer la récursion.

Moi, alors. traduit le code en F# ... et voilà ce que j'ai obtenu :

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

Stack overflow... avec les deux versions de F# que j'ai dans ma machine... Par curiosité, j'ai ensuite pris le binaire généré (ant.exe) et l'ai exécuté sous 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

Étonnamment, il fonctionne sous Mono 2.10.5 (c'est-à-dire sans débordement de pile) - mais il prend 84 secondes, c'est-à-dire 587 fois plus lent qu'OCaml - oups.

Donc ce programme...

• fonctionne bien sous OCaml
• ne fonctionne pas du tout sous .NET/F#
• fonctionne, mais est très lent, sous Mono/F#.

Pourquoi ?

EDITAR: La bizarrerie continue - L'utilisation de "--optimize+ --checked-" fait disparaître le problème, mais seulement sous ArchLinux/Mono ; sous Windows XP et Windows 7/64bit, même la version optimisée de la pile binaire déborde.

Final EDIT : J'ai trouvé la réponse moi-même - voir ci-dessous.

Answer 1

Résumé exécutif :

• J'ai écrit une implémentation simple d'un algorithme... qui n'était pas récursif en queue.
• Je l'ai compilé avec OCaml sous Linux.
• Cela a bien fonctionné, et s'est terminé en 0,14 secondes.

Il était alors temps de passer au F#.

• J'ai traduit le code (traduction directe) en F#.
• J'ai compilé sous Windows, et je l'ai exécuté - j'ai eu un débordement de pile.
• J'ai pris le binaire sous Linux, et je l'ai exécuté sous Mono.
• Il a fonctionné, mais s'est exécuté très lentement (84 secondes).

J'ai ensuite posté un message sur Stack Overflow - mais certaines personnes ont décidé de fermer la question (soupir).

• J'ai essayé de compiler avec --optimize+ --checked-
• La pile binaire déborde toujours sous Windows...
• ...mais fonctionnent bien (et se terminent en 0,5 seconde) sous Linux/Mono.

Il était temps de vérifier la taille de la pile : Sous Windows, Un autre message de SO a signalé qu'il est réglé par défaut sur 1 Mo. . Sous Linux, "uname -s" et la compilation d'un programme de test a clairement montré qu'il s'agit de 8MB.

Cela expliquait pourquoi le programme fonctionnait sous Linux et pas sous Windows (le programme utilisait plus de 1MB de pile). Cela n'explique pas pourquoi la version optimisée fonctionne tellement mieux sous Mono que la version non optimisée : 0.5 secondes vs 84 secondes (même si le --optimize+ semble être activé par défaut, voir le commentaire de Keith avec l'extrait "Expert F#"). Cela a probablement à voir avec le garbage collector de Mono, qui a été en quelque sorte poussé à l'extrême par la première version.

La différence entre les temps d'exécution de Linux/OCaml et Linux/Mono/F# (0,14 contre 0,5) est due à la façon simple dont je l'ai mesurée : "time ./binary ..." mesure également le temps de démarrage, ce qui est significatif pour Mono/.NET (enfin, significatif pour ce simple petit problème).

Quoi qu'il en soit, pour résoudre ce problème une fois pour toutes, je a écrit une version récursive de la queue - où l'appel récursif à la fin de la fonction est transformé en une boucle (et donc, aucune utilisation de la pile n'est nécessaire - du moins en théorie).

La nouvelle version fonctionne bien sous Windows également, et se termine en 0,5 seconde.

Donc, morale de l'histoire :

• Faites attention à l'utilisation de votre pile, surtout si vous en utilisez beaucoup et que vous travaillez sous Windows. Utilisez EDITBIN avec l'option /STACK pour régler vos binaires sur des tailles de pile plus importantes, ou mieux encore, écrivez votre code de manière à ne pas dépendre de l'utilisation d'une pile trop importante.
• OCaml est peut-être meilleur que F# pour l'élimination des récursions de queue - ou son ramasseur d'ordures fait un meilleur travail sur ce problème particulier.
• Ne désespérez pas de voir des personnes impolies fermer vos questions sur Stack Overflow, les bonnes personnes finiront par les contrecarrer - si les questions sont vraiment bonnes :-)

P.S. Quelques informations supplémentaires du Dr. Jon Harrop :

...vous avez juste eu la chance qu'OCaml ne déborde pas aussi. Vous avez déjà identifié que la taille réelle des piles varie selon les plateformes. Une autre facette du même problème est que les différentes implémentations de langage consomment l'espace de la pile à des taux différents et ont des performances différentes. de performances différentes en présence de piles profondes. OCaml, Mono et .NET utilisent tous des représentations de données et des algorithmes GC différents qui ont un impact sur ces résultats... (a) OCaml utilise des entiers marqués pour distinguer les pointeurs, ce qui donne des cadres de pile compacts, et va parcourir tout ce qui se trouve sur la pile à la recherche de pointeurs. Le marquage transmet essentiellement juste assez d'informations pour que le moteur d'exécution d'OCaml soit capable de parcourir le tas (b) Mono traite les mots de la pile sur la pile comme des pointeurs : si, en tant que pointeur, un mot pointerait vers un bloc alloué au tas, alors ce bloc est considéré comme atteignable. (c) Je ne connais pas l'algorithme de .NET mais je ne serais pas surpris qu'il consomme plus rapidement de l'espace sur la pile tout en parcourant chaque mot. plus rapidement tout en parcourant chaque mot de la pile (il souffre certainement d'une performance pathologique). performance pathologique de la GC si un thread non lié a une pile profonde ! pile profonde !)... De plus, votre utilisation de tuples alloués au tas signifie que vous allez que vous allez remplir la génération de la pépinière (par exemple gen0) rapidement et, par conséquent, causant le GC à traverser ces piles profondes souvent ...

Answer 2

Permettez-moi d'essayer de résumer la réponse.

Il y a 3 points à souligner :

• problème : débordement de pile sur une fonction récursive
• cela ne se produit que sous Windows : sous linux, pour la taille du problème examiné, cela fonctionne
• le même code (ou un code similaire) en OCaml fonctionne
• Le drapeau du compilateur optimize+, pour la taille du problème examiné, fonctionne

Il est très fréquent qu'une exception Stack Overflow soit le résultat d'un appel récursif. Si l'appel est en position de queue, le compilateur peut le reconnaître et appliquer l'optimisation des appels de queue, de sorte que le ou les appels récursifs n'occupent pas d'espace dans la pile. L'optimisation des appels de queue peut se produire dans F#, dans la LCR, ou dans les deux :

Optimisation de la queue du CLR 1

Récursion en F# (plus général) 2

Appels de queue F# 3

L'explication correcte pour "échoue sous Windows, pas sous Linux" est, comme d'autres l'ont dit, l'espace de pile réservé par défaut sur les deux OS. Ou mieux, l'espace de pile réservé utilisé par les compilateurs sous les deux OS. Par défaut, VC++ ne réserve que 1MB d'espace de pile. Le CLR est (probablement) compilé avec VC++, il a donc cette limitation. L'espace de pile réservé peut être augmenté au moment de la compilation, mais je ne suis pas sûr qu'il puisse être modifié sur les exécutables compilés.

EDIT : il s'avère que c'est possible (voir cet article de blog). http://www.bluebytesoftware.com/blog/2006/07/04/ModifyingStackReserveAndCommitSizesOnExistingBinaries.aspx ) Je ne le recommande pas, mais dans des situations extrêmes, c'est au moins possible.

La version OCaml peut fonctionner car elle a été exécutée sous Linux. Cependant, il serait intéressant de tester également la version OCaml sous Windows. Je sais que le compilateur OCaml est plus agressif que F# pour l'optimisation des appels de queue. Pourrait-il même extraire une fonction récursive de queue de votre code original ?

Je pense que "--optimize+" fera toujours en sorte que le code se répète, et donc échouera toujours sous Windows, mais atténuera le problème en rendant l'exécutable plus rapide.

Enfin, la solution définitive consiste à utiliser la récursion de queue (en réécrivant le code ou en s'appuyant sur une optimisation agressive du compilateur) ; c'est un bon moyen d'éviter le problème de débordement de pile avec les fonctions récursives.