Pourquoi les débordements de pile sont-ils toujours un problème ?

Question

Cette question me mystifie depuis des années et, compte tenu du nom de ce site, c'est ici qu'il faut la poser.

Pourquoi nous, les programmeurs, avons encore cette StackOverflow problème ?

Pourquoi, dans tous les principaux langages, la mémoire de la pile de threads doit-elle être allouée statiquement à la création du thread ?

Je vais parler dans le contexte de C#/Java, parce que je les utilise le plus, mais c'est probablement un problème plus large.

Une taille de pile fixe entraîne d'énormes problèmes :

• Il est impossible d'écrire un algorithme récursif à moins d'être absolument sûr que la profondeur de la récursion est minuscule. La complexité mémoire linéaire de l'algorithme récursif est souvent inacceptable.
• Il n'y a pas de moyen bon marché de commencer de nouveaux fils de discussion. Vous devez allouer un énorme bloc de mémoire pour la pile afin de tenir compte de toutes les utilisations possibles du fil.
• Même si vous n'utilisez pas de récursion très profonde, vous risquez toujours de manquer d'espace dans la pile, car la taille de la pile est un nombre fixe arbitraire. Considérant que le StackOverflow est généralement irrécupérable, c'est un gros problème à mes yeux.

Maintenant, si la pile était redimensionnée dynamiquement, tous les problèmes ci-dessus seraient grandement atténués, car le débordement de la pile ne serait possible que lorsqu'il y a un débordement de mémoire.

Mais ce n'est pas encore le cas. Pourquoi ? Les processeurs modernes présentent-ils des limitations fondamentales qui rendraient la chose impossible ou inefficace ? Si vous pensez à l'impact sur les performances que les réallocations imposeraient, cela devrait être acceptable car les gens utilisent des structures telles que ArrayList tout le temps sans souffrir beaucoup.

Donc, la question est, est-ce que je rate quelque chose et la StackOverflow n'est pas un problème, ou bien j'ai raté quelque chose et il y a beaucoup de langages avec une pile dynamique, ou bien il y a une raison importante pour que cela soit impossible/difficile à mettre en œuvre ?

Edit : Certaines personnes ont dit que la performance serait un gros problème, mais considérez ceci :

• Nous laissons le code compilé intact. L'accès à la pile reste le même, donc les performances du "cas habituel" restent les mêmes.
• Nous gérons l'exception CPU qui se produit lorsque le code tente d'accéder à la mémoire non allouée et lançons notre routine de "réallocation". Les réallocations ne seront pas fréquentes car <mettez votre argument habituel ArrayList ici>. Cela devrait fonctionner sur la plupart des CPU en mode protégé sans perte de performance. Non ?

Answer 1

Je n'ai jamais rencontré personnellement un débordement de pile qui n'était pas causés par la récursion infinie. Dans ces cas, une taille de pile dynamique ne serait d'aucune utilité, il faudrait juste un peu plus de temps pour épuiser la mémoire.

Answer 2

1) Pour redimensionner les piles, il faut pouvoir déplacer la mémoire, ce qui signifie que les pointeurs vers quoi que ce soit sur une pile peuvent devenir invalides après un redimensionnement de la pile. Oui, vous pouvez utiliser un autre niveau d'indirection pour résoudre ce problème, mais n'oubliez pas que la pile est utilisée pour les opérations suivantes très, très fréquemment.

2) Cela complique considérablement les choses. Les opérations Push/Pop sur les piles fonctionnent généralement simplement en effectuant une arithmétique de pointeur sur un registre du CPU. C'est pourquoi l'allocation sur une pile est plus rapide que l'allocation sur le free-store.

3) Certains processeurs (notamment les microcontrôleurs) implémentent la pile directement sur le matériel, séparément de la mémoire principale.

Aussi, vous pouvez définir la taille de la pile d'un thread lorsque vous créez un nouveau thread à l'aide de la fonction beginthread() Ainsi, si vous trouvez que l'espace supplémentaire de la pile est inutile, vous pouvez définir la taille de la pile en conséquence.

D'après mon expérience, les débordements de pile sont généralement provoqués par des récursions infinies ou des fonctions récursives qui allouent enorme sur la pile. Selon MSDN, la taille par défaut de la pile fixée par l'éditeur de liens est de 1MB (l'en-tête des fichiers exécutables peut fixer sa propre valeur par défaut). ce qui semble être plus que suffisant pour la majorité des cas.

Le mécanisme de pile fixe fonctionne suffisamment bien pour la majorité des applications, il n'y a donc pas vraiment besoin de le changer. Si ce n'est pas le cas, vous pouvez toujours déployer votre propre pile.

Answer 3

Je ne peux pas parler pour les "langues majeures". De nombreux langages "mineurs" utilisent des enregistrements d'activation alloués au tas, chaque appel utilisant un morceau d'espace de tas au lieu d'un morceau de pile linéaire. Cela permet à la récursion d'aller aussi profondément que vous avez de l'espace d'adresse à allouer.

Certaines personnes ici prétendent que la récursion aussi profonde est mauvaise, et que l'utilisation d'une "grosse pile linéaire" est tout à fait correcte. Ce n'est pas vrai. Je suis d'accord pour dire que si vous devez utiliser tout l'espace d'adressage, vous avez un problème quelconque. Cependant, lorsque l'on a de très grandes structures de graphes ou d'arbres, il est possible d'utiliser une pile linéaire. veulent pour permettre une récursion profonde et vous ne voulez pas deviner combien d'espace linéaire de pile vous avez besoin d'abord, parce que vous vous trompez.

Si vous décidez d'opter pour le parallélisme et que vous avez beaucoup (des milliers ou des millions de "grains" [pensez à de petits fils]), vous ne pouvez pas allouer 10 Mo d'espace de pile à chaque fil, car vous gaspilleriez des gigaoctets de RAM. Comment diable pouvez-vous avoir un million de grains ? C'est simple : beaucoup de grains qui s'imbriquent les uns dans les autres ; lorsqu'un grain est gelé en attendant un verrou, vous ne pouvez pas vous en débarrasser, et pourtant vous voulez toujours faire tourner d'autres grains pour utiliser vos processeurs disponibles. Cela maximise la quantité de travail disponible, et permet donc d'utiliser efficacement de nombreux processeurs physiques.

El PARLANSE Le langage de programmation parallèle utilise ce modèle de grains parallèles en très grand nombre, et l'allocation du tas sur les appels de fonction. Nous avons conçu PARLANSE pour permettre l'analyse et la transformation symbolique de très grands programmes informatiques sources (disons, plusieurs millions de lignes de code). Ceux-ci produisent... des arbres syntaxiques abstraits géants, des graphiques de flux de contrôle/données géants, des tables de symboles géantes, avec des dizaines de millions de nœuds. Beaucoup d'opportunités pour les travailleurs parallèles.

L'allocation du tas permet aux programmes PARLANSE d'avoir une portée lexicale, même à travers les frontières de parallélisme, car on peut implémenter "la pile" comme une pile cactus, où les bifurcations se produisent dans "la pile" pour les sous-grains, et chaque grain peut par conséquent voir les enregistrements d'activation (scopes parents) de ses appelants. Cela rend le passage de grandes structures de données peu coûteux lors de la récursion ; il suffit de les référencer lexicalement.

On pourrait penser que l'allocation du tas ralentit le programme. C'est le cas ; PARLANSE paie une pénalité d'environ 5% en termes de performance mais gagne la capacité de traiter de très grandes structures en parallèle, avec autant de grains que l'espace d'adressage peut en contenir.

Answer 4

Piles son redimensionné dynamiquement - ou, pour être plus précis, grandi dynamiquement. Il y a débordement lorsqu'une pile ne peut plus croître, ce qui ne veut pas dire qu'elle a épuisé l'espace d'adressage, mais plutôt qu'elle s'est développée au point d'entrer en conflit avec une partie de la mémoire utilisée à d'autres fins (par exemple, le tas d'un processus).

Vous voulez peut-être dire que les piles ne peuvent pas être déplacé dynamiquement ? La raison en est probablement que les piles sont intimement liées au matériel. Les processeurs ont des registres et des piles de logique dédiés à la gestion des piles de threads (esp, ebp, instructions call/return/enter/leave sur x86). Si votre langage est compilé (ou même jitted), vous êtes lié au mécanisme matériel et ne pouvez pas déplacer les piles.

Cette "limitation" matérielle est probablement là pour rester. Re-baser une pile de threads pendant l'exécution d'un thread semble loin d'être une demande raisonnable de la part d'une plate-forme matérielle (et la complexité supplémentaire gênerait considérablement tout code exécuté sur un tel CPU imaginaire, même compilé). On peut imaginer un environnement complètement virtualisé où cette limitation ne s'applique pas, mais comme un tel code ne pourrait pas être jitté - il serait insupportablement lent. Aucune chance de pouvoir faire quoi que ce soit d'interactif avec.

Answer 5

Je vais résumer les arguments dans les réponses jusqu'à présent car je ne trouve aucune réponse couvrant ce sujet suffisamment bien.

Examen statique de la pile

Motivation

Tout le monde n'en a pas besoin.

• La plupart des algorithmes ne font pas appel à une récursion profonde ou à un grand nombre de threads, de sorte que peu de gens ont besoin de piles dynamiques.
• Une pile dynamique entraînerait un débordement de pile à récursion infinie, ce qui est une erreur facile à commettre, plus difficile à diagnostiquer (un débordement de mémoire, tout en étant aussi mortel qu'un débordement de pile pour le processus en cours, est également dangereux pour les autres processus).
• Chaque algorithme récursif peut être émulé par un algorithme itératif similaire.

Difficultés de mise en œuvre

La mise en œuvre de la pile dynamique s'avère moins simple qu'il n'y paraît.

• Le redimensionnement de la pile à lui seul ne suffit pas, à moins de disposer d'un espace d'adressage illimité. Vous aurez parfois besoin de relocaliser la pile également.
• Le déplacement de la pile nécessiterait la mise à jour de tous les pointeurs vers les structures de données allouées sur la pile. Si cela est simple (du moins dans les langages gérés) pour les données en mémoire, il n'y a pas de moyen facile de faire de même pour les données dans les registres du CPU du thread.
• Certains processeurs (notamment les microcontrôleurs) implémentent la pile directement sur le matériel, séparément de la mémoire principale.

Mises en œuvre existantes

Certains langages ou bibliothèques d'exécution possèdent déjà la fonctionnalité de pile dynamique ou quelque chose de similaire.

• Certaines bibliothèques d'exécution (lesquelles ?) ne pré-engagent pas l'intégralité du bloc de mémoire alloué à la pile. Cela peut atténuer le problème, en particulier pour les systèmes 64 bits, mais pas l'éliminer complètement.
• Ira Baxter nous a dit sobre PARLANSE un langage spécifiquement conçu pour traiter des structures de données complexes avec un haut degré de parallélisme. Il utilise de petits "grains" de travail alloués au tas au lieu de la pile.
• sucette floue nous a dit que "Correctement écrit Erlang n'a pas de débordements de pile !"
• Le langage de programmation Google Go est réputé pour avoir une pile dynamique. (un lien serait le bienvenu)

J'aimerais voir plus d'exemples ici.

J'espère ne pas avoir oublié d'informations importantes sur ce sujet. Faire de ce site un wiki communautaire afin que chacun puisse ajouter de nouvelles informations.