C / C ++ taille de pile maximale du programme

Question

Je veux faire DFS sur un tableau de 100 X 100. (Disons que les éléments du tableau représentent les nœuds du graphe) Donc, dans le pire des cas, la profondeur des appels de fonction récursifs peut aller jusqu'à 10 000, chaque appel prenant jusqu'à 20 octets. Alors, est-ce que cela est faisable, y a-t-il une possibilité de stackoverflow?

Quelle est la taille maximale de la pile en C / C ++?

S'il vous plaît spécifier pour gcc pour les deux
1) cygwin sous Windows
2) Unix

Quelles sont les limites générales?

Answer 1

Dans Visual Studio, la taille de pile par défaut est de 1 MO je pense, donc, avec une profondeur de récursion de 10.000 chaque frame de pile peut être tout au plus ~100 octets qui devrait être suffisant pour un algorithme DFS.

La plupart des compilateurs, y compris Visual Studio vous permettent de spécifier la taille de la pile. Sur certaines (toutes?) linux saveurs de la taille de la pile n'est pas une partie de l'exécutable, mais une variable d'environnement dans le système d'exploitation.

Voici un lien avec de la pile par défaut tailles pour gcc.

DFS sans récursivité:

std::stack<Node> dfs;
dfs.push(start);
do {
    Node top = dfs.top();
    if (top is what we are looking for) {
       break;
    }
    dfs.pop();
    for (outgoing nodes from top) {
        dfs.push(outgoing node);
    }
} while (!dfs.empty())

Answer 2

les piles de fils sont souvent plus petites. Vous pouvez modifier la valeur par défaut au moment du lien ou également au moment de l'exécution. Pour référence, voici quelques exemples de valeurs par défaut:

• glibc i386, x86_64 7,4 Mo
• Tru64 5.1 5.2 MB
• Cygwin 1.8 MB
• Solaris 7..10 1 Mo
• MacOS X 10.5 460 KB
• AIX 5 98 KB
• OpenBSD 4.0 64 Ko
• HP-UX 11 16 Ko

Answer 3

Dépend de la plate-forme, de la chaîne d'outils, de ulimit, des paramètres, etc. Ce n'est pas spécifié, et de nombreuses propriétés statiques et dynamiques peuvent l'influencer.

Answer 4

Oui, il y a une possibilité de dépassement de pile. Le C et le C++ standard ne dicte pas des choses comme la pile de profondeur, celles-ci sont généralement d'une question d'environnement.

La plupart des bons environnements de développement et/ou de systèmes d'exploitation vont vous permettre d'adapter la taille de la pile d'un processus, que ce soit en lien ou le temps de chargement.

Vous devez spécifier le système d'exploitation et l'environnement de développement, vous êtes en utilisant pour plus d'aide ciblée.

Par exemple, sous Ubuntu Karmic Koala, la valeur par défaut de gcc est de 2M réservés et 4K est engagé, mais cela peut être modifié lorsque vous liez le programme. Utiliser l' --stack option de ld à le faire.

Answer 5

Je ne suis pas sûr de ce que vous entendez par une première recherche en profondeur sur un tableau rectangulaire, mais je suppose que vous savez ce que vous faites.

Si la limite de pile pose un problème, vous devriez pouvoir convertir votre solution récursive en une solution itérative qui place les valeurs intermédiaires dans une pile allouée à partir du segment de mémoire.