Combien sont trop d'appels de fonction imbriqués?

15

Cité sur MSDN à propos de StackOverflowException :

Exception levée lorsque la pile d'exécution déborde car elle contient trop d'appels de méthode imbriqués.

Too manyest assez vague ici. Comment savoir quand trop est vraiment trop? Des milliers d'appels de fonction? Des millions? Je suppose que cela doit être lié en quelque sorte à la quantité de mémoire dans l'ordinateur, mais est-il possible de trouver un ordre de grandeur à peu près précis?

Cela m'inquiète car je développe un projet qui implique une utilisation intensive des structures récursives et des appels de fonctions récursives. Je ne veux pas que l'application échoue lorsque je commence à l'utiliser pour plus que de petits tests.

marco-fiset
la source
4
Il est relativement facile de convertir une fonction récursive en fonction non récursive. Collez simplement vos données sur un Stack<T>.
Brian
1
La taille de "trop" est à vous de définir. Pour .NET, utilisez editbin /stack:WHATEVER-NUMBER-YOU-LIKE yourexefile.exe.
SK-logic

Réponses:

28

Cela m'inquiète car je développe un projet qui implique une utilisation intensive des structures récursives et des appels de fonctions récursives. Je ne veux pas que l'application échoue lorsque je commence à l'utiliser pour plus que de petits tests.

Sauf si votre environnement linguistique prend en charge l' optimisation des appels de queue (et que votre récursion est un appel de queue), une règle de base est la suivante: la profondeur de récursivité doit être garantie comme étant O (log n), c'est-à-dire en utilisant des algorithmes ou des structures de données basés sur la division et conquérir (comme les arbres, la plupart des alogorithmes de tri, etc.) est OK, mais rien de linéaire (comme les implémentations récursives de la gestion des listes liées) ne l'est pas.

Michael Borgwardt
la source
3
+1. Très bonne réponse, j'ai implicitement utilisé cette règle mais je n'en avais pas conscience.
Giorgio
De nos jours, à peu près n'importe quel compilateur de qualité de production digne de la phrase adjectif prendra en charge l'optimisation des appels de queue.
John R. Strohm
1
@ JohnR.Strohm Cependant, l'OP a marqué la question .NET, donc AFAIK, seule la gigue 64 bits fait actuellement une optimisation des appels de queue.
Mark Hurd
1
Juste pour qu'il n'y ait pas de confusion, les x86 et x64 honorent toujours la "queue" CIL. préfixe d'instruction. Donc, pour résumer, en terre .NET, F # effectue une optimisation complète des appels de queue, C # ne le fait pas, et la gigue x64 le fait si c'est "facile" (cela ne peut pas dépendre). Voir blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/…
Stephen Swensen
1
Certes, mais dans certains cas, comme dans un infâme serveur IIS hébergeant ASP.NET, même une simple profondeur de récursion O (log n) peut échouer en raison de leur limite de profondeur de pile minuscule pathétique, injustifiée et risible, ce qui rend à peu près toute récursivité (ou même une longue chaîne d'appels imbriqués non récursifs) impossible. La seule solution consiste à modifier le binaire iis lui-même.
SK-logic
17

Par défaut, le CLR alloue 1 Mo à la pile pour chaque thread (voir cet article ). Donc, c'est cependant de nombreux appels qu'il faut pour dépasser ce montant. Cela variera en fonction de l'espace sur la pile que chaque appel utilise pour des choses comme les paramètres et les variables locales.

Vous pouvez même lui faire lancer un StackOverflowExceptionavec un seul appel si vous êtes prêt à être un peu peu orthodoxe:

private static unsafe void BlowUpTheStack()
{
    var x = stackalloc byte[1000000000];
    Console.WriteLine("Oh no, I've blown up the stack!");
}
Cole Campbell
la source
Malheureusement, ce défaut raisonnable est souvent violé (par exemple, dans asp.net).
SK-logic
2

Puisque Cole Campbell a noté la taille de la mémoire et Michael Borgwardt a noté l' optimisation des appels de queue, je ne les couvrirai pas.

Une autre chose à savoir est CPS qui peut être utilisé pour optimiser plusieurs fonctions entrelacées où l'optimisation des appels de queue est pour des fonctions uniques.

Vous pouvez augmenter la taille de la pile comme nous l'avons fait ici , et sachez que le code 64 bits mange la pile plus rapidement que le code 32 bits.

Il convient de noter que nous avons exécuté l'un des exemples sous F # interactif pendant plus de 40 heures sans faire exploser la pile. Oui, c'était un appel de fonction qui s'est déroulé de lui-même en continu jusqu'à la fin.

En outre, si vous devez effectuer une couverture de code pour déterminer où les problèmes se produisent et que vous ne pouvez pas utiliser la couverture de code avec VS, TestDriven.NET

Guy Coder
la source