Tamanho máximo da pilha C / C ++ do programa

115

Eu quero fazer DFS em uma matriz 100 X 100. (Digamos que os elementos da matriz representam os nós do gráfico) Portanto, assumindo o pior caso, a profundidade das chamadas de função recursivas pode ir até 10.000 com cada chamada ocupando até, digamos, 20 bytes. Portanto, é viável significa que existe a possibilidade de stackoverflow?

Qual é o tamanho máximo da pilha em C / C ++?

Especifique para gcc para
1) cygwin no Windows
2) Unix

Quais são os limites gerais?

avd
fonte

Respostas:

106

No Visual Studio, o tamanho da pilha padrão é 1 MB, eu acho, então com uma profundidade de recursão de 10.000 cada quadro de pilha pode ter no máximo ~ 100 bytes, o que deve ser suficiente para um algoritmo DFS.

A maioria dos compiladores, incluindo o Visual Studio, permite que você especifique o tamanho da pilha. Em alguns (todos?) Tipos de linux, o tamanho da pilha não é parte do executável, mas uma variável de ambiente no sistema operacional. Você pode então verificar o tamanho da pilha com ulimit -se definir um novo valor com, por exemplo ulimit -s 16384.

Aqui está um link com tamanhos de pilha padrão para gcc.

DFS sem recursão:

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())
Andreas Brinck
fonte
47

pilhas de threads geralmente são menores. Você pode alterar o padrão em tempo de link ou também em tempo de execução. Para referência, alguns padrões são:

  • glibc i386, x86_64 7,4 MB
  • Tru64 5.1 5.2 MB
  • Cygwin 1,8 MB
  • Solaris 7..10 1 MB
  • MacOS X 10,5 460 KB
  • AIX 5 98 KB
  • OpenBSD 4.0 64 KB
  • HP-UX 11 16 KB
pixelbeat
fonte
17

Dependente da plataforma, dependente do conjunto de ferramentas, dependente do ulimit, dependente do parâmetro ... Ele não é especificado de forma alguma, e há muitas propriedades estáticas e dinâmicas que podem influenciá-lo.

DrPizza
fonte
6

Sim, existe a possibilidade de estouro da pilha. O padrão C e C ++ não dita coisas como a profundidade da pilha, isso geralmente é um problema ambiental.

A maioria dos ambientes de desenvolvimento e / ou sistemas operacionais decentes permitirá que você ajuste o tamanho da pilha de um processo, seja no link ou no tempo de carregamento.

Você deve especificar qual sistema operacional e ambiente de desenvolvimento está usando para obter assistência mais direcionada.

Por exemplo, no Ubuntu Karmic Koala, o padrão para gcc é 2M reservados e 4K confirmados, mas isso pode ser alterado quando você vincula o programa. Use o--stack opção de ldfazer isso.

paxdiablo
fonte
5

Acabei de ficar sem pilha no trabalho, era um banco de dados e estava executando alguns threads, basicamente o desenvolvedor anterior jogou um grande array na pilha, e a pilha estava baixa de qualquer maneira. O software foi compilado usando o Microsoft Visual Studio 2015.

Mesmo que o encadeamento tenha ficado sem pilha, ele falhou silenciosamente e continuou, apenas a pilha transbordou quando chegou a hora de acessar o conteúdo dos dados na pilha.

O melhor conselho que posso dar é não declarar arrays na pilha - especialmente em aplicativos complexos e particularmente em threads, em vez disso, use heap. É para isso que existe;)

Além disso, lembre-se de que ele pode não falhar imediatamente ao declarar a pilha, mas apenas no acesso. Meu palpite é que o compilador declara a pilha no Windows "otimisticamente", ou seja, ele assumirá que a pilha foi declarada e tem tamanho suficiente até chegar a usá-la e então descobrir que a pilha não está lá.

Diferentes sistemas operacionais podem ter diferentes políticas de declaração de pilha. Por favor, deixe um comentário se você souber quais são essas políticas.

Coruja
fonte
3

Não tenho certeza do que você quer dizer com fazer uma pesquisa em profundidade em uma matriz retangular, mas presumo que você saiba o que está fazendo.

Se o limite da pilha for um problema, você deve ser capaz de converter sua solução recursiva em uma solução iterativa que envia valores intermediários para uma pilha que é alocada do heap.

Dave Kirby
fonte