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

Eu quero fazer o DFS em um array de 100 x 100. (Digamos que elementos de array representem nós de gráfico) Assim, assumindo o pior caso, a profundidade das chamadas de function recursiva pode ir até 10000 com cada chamada levando até 20 bytes. Então, é possível significa que existe uma possibilidade de stackoverflow?

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

Por favor, especifique para gcc para ambos
1) cygwin no Windows
2) Unix

Quais são os limites gerais?

No Visual Studio, o tamanho da pilha padrão é de 1 MB, portanto, com uma profundidade de recursion 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 especificar 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 -s e configurá-lo para um novo valor com, por exemplo, ulimit -s 16384 .

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

DFS sem recursion:

 std::stack 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()) 

as pilhas de threads são geralmente menores. Você pode alterar o padrão no momento do link ou alterar no tempo de execução também. 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

Dependente de plataforma, dependente de toolchain, dependente de ulimit, dependente de parâmetro …. Não é de todo especificado, e existem muitas propriedades estáticas e dinâmicas que podem influenciá-lo.

Sim, existe uma possibilidade de estouro de pilha. Os padrões C e C ++ não ditam coisas como profundidade de pilha, esses são geralmente um problema ambiental.

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

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

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

Não tenho certeza do que você quer dizer ao fazer uma primeira pesquisa aprofundada em uma matriz retangular, mas suponho que você saiba o que está fazendo.

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

Acabei de ficar sem pilha no trabalho, era um database e estava executando alguns threads, basicamente o desenvolvedor anterior tinha jogado uma grande matriz 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, ele apenas empilhou quando accessu o conteúdo dos dados na pilha.

O melhor conselho que posso dar é não declarar matrizes na pilha – especialmente em aplicações complexas e particularmente em threads, em vez disso, use heap. É para isso que está lá;

Também tenha em mente que não pode falhar imediatamente ao declarar a pilha, mas apenas no access. Meu palpite é que o compilador declara a pilha no Windows “otimisticamente”, isto é, ela assumirá que a pilha foi declarada e tem tamanho suficiente até que venha a usá-la e descubra 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.