Poderia ser mais eficiente para os sistemas em geral eliminar as pilhas e usar o Heap para gerenciamento de memória?

14

Parece-me que tudo o que pode ser feito com uma pilha pode ser feito com a pilha, mas nem tudo que pode ser feito com a pilha pode ser feito com a pilha. Isso está correto? Então, por uma questão de simplicidade, e mesmo se perdermos uma pequena quantidade de desempenho com determinadas cargas de trabalho, não seria melhor seguir apenas um padrão (ou seja, a pilha)?

Pense na troca entre modularidade e desempenho. Sei que essa não é a melhor maneira de descrever esse cenário, mas, em geral, parece que a simplicidade de entendimento e design pode ser uma opção melhor, mesmo que exista um potencial para um melhor desempenho.

Templário Sombrio
fonte
1
Em C e C ++, você precisa desalocar explicitamente a memória que foi alocada no heap. Isso não é mais simples.
user16764
Eu usei uma implementação C #, pois os perfis revelaram que os objetos de pilha foram alocados em uma área semelhante a heap com uma terrível coleta de lixo. Minha solução? Mova todo o possível (por exemplo, variáveis ​​de loop, variáveis ​​temporárias, etc.) para a memória heap persistente. Feito o programa comer 10x a RAM e rodar a 10x a velocidade.
precisa saber é o seguinte
@IanMallett: Eu não entendo sua explicação sobre o problema e a solução. Você tem um link com mais informações em algum lugar? Normalmente, acho a alocação baseada em pilha mais rápida.
precisa
@FrankHileman, o problema básico era este: a implementação do C # que eu estava usando tinha uma velocidade de coleta de lixo extremamente baixa. A "solução" era tornar todas as variáveis ​​persistentes para que no tempo de execução nenhuma operação de memória acontecesse. Escrevi um artigo de opinião há um tempo atrás sobre o desenvolvimento de C # / XNA em geral que também discute parte do contexto.
imallett
@IanMallett: obrigado. Como ex-desenvolvedor de C / C ++, que mais usa C # atualmente, minha experiência tem sido bem diferente. Acho que as bibliotecas são o maior problema. Parece que a plataforma XBox360 estava incompleta para desenvolvedores .net. Normalmente, quando tenho problemas com o GC, mudo para o pool. Isso ajuda.
precisa

Respostas:

30

As pilhas são ruins na rápida alocação e desalocação de memória. Se você deseja capturar muitas pequenas quantidades de memória por um período limitado, um monte não é sua melhor escolha. Uma pilha, com seu algoritmo super-simples de alocação / desalocação, se destaca naturalmente (ainda mais se for incorporada ao hardware), e é por isso que as pessoas a usam para coisas como passar argumentos para funções e armazenar variáveis ​​locais - o mais A desvantagem importante é que ele possui espaço limitado e, portanto, manter objetos grandes nele, ou tentar usá-lo para objetos de vida longa, são idéias ruins.

Livrar-se completamente da pilha para simplificar uma linguagem de programação é o caminho errado da IMO - uma abordagem melhor seria abstrair as diferenças, deixar o compilador descobrir que tipo de armazenamento usar, enquanto o programador reúne construções de nível mais próximas da maneira como os humanos pensam - e, de fato, linguagens de alto nível como C #, Java, Python etc. fazem exatamente isso. Eles oferecem sintaxe quase idêntica para objetos alocados em heap e primitivas alocadas em pilha ('tipos de referência' vs. 'tipos de valor' no lingo .NET), totalmente transparentes ou com algumas diferenças funcionais que você deve entender para usar a linguagem corretamente (mas você realmente não precisa saber como uma pilha e uma pilha funcionam internamente).

tdammers
fonte
2
WOW isso foi bom :) Realmente conciso e informativo para um iniciante!
Escuro Templar
1
Em muitas CPUs, a pilha é tratada em hardware, o que é um problema externo ao idioma, mas desempenha um papel importante no tempo de execução.
Patrick Hughes
@ Patrick Hughes: Sim, mas o Heap também está localizado no hardware também, não é?
Escuro Templar
@ Dark O que Patrick provavelmente quer dizer é que arquiteturas como o x86 têm registros especiais para gerenciar a pilha e instruções especiais para colocar ou remover algo na / da pilha. Isso torna muito rápido.
FUZxxl 10/10
3
@Donal Fellows: Tudo verdade. Mas o ponto é que as pilhas e os montes têm pontos fortes e fracos, e usá-los adequadamente produzirá o código mais eficiente.
T113 #
8

Simplificando, uma pilha não é um pouco de desempenho. É centenas ou milhares de vezes mais rápido que o monte. Além disso, a maioria das máquinas modernas possui suporte de hardware para a pilha (como x86) e essa funcionalidade de hardware, por exemplo, a pilha de chamadas não pode ser removida.

DeadMG
fonte
O que você quer dizer quando diz que as máquinas modernas têm suporte de hardware para a pilha? A pilha em si já está no hardware, não é?
Dark Templar
1
O x86 possui registros e instruções especiais para lidar com a pilha. O x86 não tem suporte para pilhas - essas coisas são criadas pelo sistema operacional.
Pubby
8

Não

A área de pilha em C ++ é incrivelmente rápida em comparação. Acho que nenhum desenvolvedor experiente de C ++ estaria aberto a desativar essa funcionalidade.

Com o C ++, você tem escolha e controle. Os designers não estavam particularmente inclinados a introduzir recursos que adicionavam tempo ou espaço de execução significativo.

Exercitando essa escolha

Se você deseja criar uma biblioteca ou programa que exija que cada objeto seja alocado dinamicamente, você pode fazer isso com C ++. Seria executado de forma relativamente lenta, mas você poderia ter essa 'modularidade'. Para o resto de nós, a modularidade é sempre opcional, introduza-a conforme necessário, pois ambas são necessárias para implementações boas / rápidas.

Alternativas

Existem outros idiomas que exigem que o armazenamento para cada objeto seja criado no heap; é bastante lento, comprometendo os designs (programas do mundo real) de uma maneira que é pior do que ter que aprender os dois (IMO).

Ambos são importantes, e o C ++ fornece o uso eficiente de energia para cada cenário. Dito isto, a linguagem C ++ pode não ser ideal para o seu design, se esses fatores no seu OP forem importantes para você (por exemplo, leia em linguagens de nível superior).

justin
fonte
O heap é na verdade a mesma velocidade da pilha, mas não tem o suporte de hardware especializado para alocação. Por outro lado, existem maneiras de acelerar muito as pilhas (sujeitas a várias condições que as tornam técnicas somente para especialistas).
Donal Fellows
@DonalFellows: O suporte de hardware para pilhas é irrelevante. O importante é saber que sempre que algo é lançado, é possível liberar qualquer coisa alocada após ele. Algumas linguagens de programação não possuem pilhas que podem liberar objetos de forma independente, mas possuem apenas o método "liberar tudo alocado após".
precisa
6

Então, por uma questão de simplicidade, e mesmo se perdermos uma pequena quantidade de desempenho com determinadas cargas de trabalho, não seria melhor seguir apenas um padrão (ou seja, a pilha)?

Na verdade, o impacto no desempenho provavelmente será considerável!

Como outros já apontaram, as pilhas são uma estrutura extremamente eficiente para gerenciar dados que obedecem às regras LIFO (último a entrar, primeiro a sair). A alocação / liberação de memória na pilha geralmente é apenas uma alteração em um registro na CPU. Alterar um registro é quase sempre uma das operações mais rápidas que um processador pode executar.

A pilha geralmente é uma estrutura de dados bastante complexa e a alocação / liberação de memória exigirá muitas instruções para fazer toda a contabilidade associada. Pior ainda, em implementações comuns, toda chamada para trabalhar com o heap tem o potencial de resultar em uma chamada para o sistema operacional. As chamadas do sistema operacional consomem muito tempo! O programa normalmente precisa alternar do modo de usuário para o modo de kernel, e sempre que isso acontece, o sistema operacional pode decidir que outros programas têm necessidades mais prementes e que seu programa precisará aguardar.

Charles E. Grant
fonte
5

Simula usou a pilha para tudo. Colocar tudo no heap sempre induz mais um nível de indireção para as variáveis ​​locais e coloca pressão adicional no Garbage Collector (você deve levar em conta que o Garbage Collectors realmente foi péssimo naquela época). É em parte por isso que Bjarne inventou o C ++.

fredoverflow
fonte
Então, basicamente, o C ++ também usa o heap também?
Dark Templar
2
@ Dark: O que? Não. A falta de pilha no Simula foi uma inspiração para fazê-lo melhor.
Fredoverflow
Ah entendo o que você quer dizer agora! Obrigado +1 :)
Dark Templar
3

As pilhas são extremamente eficientes para dados LIFO, como os metadados associados às chamadas de função, por exemplo. A pilha também aproveita os recursos inerentes de design da CPU. Como o desempenho nesse nível é fundamental para praticamente tudo o mais em um processo, aceitar esse hit "pequeno" nesse nível se propagará muito amplamente. Além disso, a memória heap é móvel pelo sistema operacional, o que seria mortal para as pilhas. Embora uma pilha possa ser implementada na pilha, ela exige sobrecarga que afetará literalmente todas as partes de um processo no nível mais granular.

kylben
fonte
2

"eficiente" em termos de você escrever código, talvez, mas certamente não em termos de eficiência do software. As alocações de pilha são essencialmente livres (são necessárias apenas algumas instruções da máquina para mover o ponteiro da pilha e reservar espaço na pilha para variáveis ​​locais).

Como a alocação de pilha quase não leva tempo, uma alocação mesmo em um heap muito eficiente será 100k (se não 1M +) vezes mais lenta.

Agora imagine quantas variáveis ​​locais e outras estruturas de dados um aplicativo típico usa. Cada pequeno "i" que você usa como contador de loop é alocado um milhão de vezes mais devagar.

Certifique-se de que o hardware seja rápido o suficiente, você pode escrever um aplicativo que use apenas heap. Agora, imagine agora que tipo de aplicativo você poderia escrever se aproveitasse o heap e usasse o mesmo hardware.

DXM
fonte
Quando você diz "imagine quantas variáveis ​​locais e outras estruturas de dados um aplicativo típico usa" a que outras estruturas de dados você se refere especificamente?
Escuro Templar
1
Os valores "100k" e "1M +" são de alguma forma científicos? Ou é apenas uma maneira de dizer "muito"?
Bruno Reis
@Bruno - IMHO os números de 100 mil e 1 milhão que usei são na verdade estimativas conservadoras para provar um ponto. Se você estiver familiarizado com o VS e C ++, escreva um programa que aloque 100 bytes na pilha e escreva um que aloque 100 bytes na pilha. Em seguida, mude para a visualização de desmontagem e simplesmente conte o número de instruções de montagem que cada alocação leva. As operações de heap são geralmente várias chamadas de função para o DLL do Windows, existem buckets e listas vinculadas e, em seguida, há coalescência e outros algoritmos. Com a pilha, pode resumir-se a uma instrução de montagem "add esp, 100" ...
DXM
2
"100k (se não 1M +) de vezes mais lento"? Isso é um pouco exagerado. Que sejam duas ordens de magnitude mais lentas, talvez três, mas é isso. Pelo menos, meu Linux é capaz de fazer alocações de heap de 100M (+ algumas instruções vizinhas) em menos de 6 segundos em um Core i5, que não pode ser mais do que algumas centenas de instruções por alocação - na verdade, é quase certamente menos. Se é seis ordens de magnitude mais lenta que a pilha, há algo de muito errado com a implementação da pilha do sistema operacional. Claro que há um erro muito com o Windows, mas isso ...
leftaroundabout
1
os moderadores provavelmente estão prestes a matar todo esse tópico de comentários. Então, aqui está o negócio, reconheço que os números reais foram puxados para fora do meu ...., mas vamos concordar o fator é muito, muito grande e não fazer mais comentários :)
DXM
2

Você pode ter interesse em "A coleta de lixo é rápida, mas a pilha é mais rápida".

http://dspace.mit.edu/bitstream/handle/1721.1/6622/AIM-1462.ps.Z

Se eu li corretamente, esses caras modificaram um compilador C para alocar "quadros de pilha" na pilha e, em seguida, usam a coleta de lixo para desalocar os quadros em vez de estourar a pilha.

Os "quadros de pilha" alocados à pilha superam decisivamente os "quadros de pilha" alocados na pilha.

Bruce Ediger
fonte
1

Como a pilha de chamadas funciona em um heap? Essencialmente, você teria que alocar uma pilha na pilha em todos os programas; então, por que não fazer com que o hardware do OS + faça isso por você?

Se você quiser que as coisas sejam realmente simples e eficientes, dê ao usuário um pedaço de memória e deixe-o lidar com isso. É claro que ninguém quer implementar tudo sozinho e é por isso que temos uma pilha e uma pilha.

Pubby
fonte
A rigor, uma "pilha de chamadas" não é um recurso necessário de um ambiente de tempo de execução da linguagem de programação. por exemplo, uma implementação direta de uma linguagem funcional avaliada preguiçosamente por redução de gráfico (que eu codifiquei) não possui pilha de chamadas. Mas a pilha de chamadas é uma técnica muito útil e amplamente utilizada, especialmente porque os processadores modernos assumem que você a usa e são otimizados para seu uso.
Ben
@ Ben - embora seja verdade (e uma coisa boa) abstrair coisas como alocação de memória de um idioma, isso não altera a arquitetura do computador que prevalece agora. Portanto, seu código de redução de gráfico ainda usará a pilha durante a execução - goste ou não.
Ingo
@ Ingo Não é realmente em nenhum sentido significativo. Claro, o sistema operacional inicializará uma seção da memória tradicionalmente chamada "a pilha", e haverá um registro apontando para ela. Mas as funções no idioma de origem não acabam representadas como quadros de pilha na ordem de chamada. A execução da função é totalmente representada pela manipulação de estruturas de dados no heap. Mesmo sem usar a otimização de última chamada, não é possível "sobrecarregar a pilha". É o que quero dizer quando digo que não há nada fundamental na "pilha de chamadas".
Ben
Não falo das funções do idioma de origem, mas das funções do intérprete (ou o que seja) que realmente executam a redução do gráfico. Aqueles precisarão de uma pilha. Isso é evidente, pois o hardware contemporâneo não faz redução de gráfico. Portanto, seu algoritmo de redução de gráfico é finalmente mapeado para a máquina, e aposto que há chamadas de sub-rotina entre elas. QED.
Ingo
1

A pilha e a pilha são necessárias. Eles são usados ​​em diferentes situações, por exemplo:

  1. A alocação de heap tem uma limitação de que sizeof (a [0]) == sizeof (a [1])
  2. A alocação de pilha tem uma limitação de que sizeof (a) é constante em tempo de compilação
  3. A alocação de heap pode fazer loops, gráficos, etc. estruturas de dados complexas
  4. A alocação de pilha pode criar árvores de tamanho em tempo de compilação
  5. O heap requer rastreamento de propriedade
  6. A alocação e desalocação de pilha é automática
  7. A memória da pilha pode ser facilmente passada de um escopo para outro por meio de ponteiros
  8. A memória da pilha é local para cada função e os objetos precisam ser movidos para o escopo superior para prolongar sua vida útil (ou armazenados dentro de objetos em vez de dentro de funções membro)
  9. Heap é ruim para desempenho
  10. A pilha é bem rápida
  11. Objetos de heap são retornados de funções por meio de ponteiros que são proprietários. Ou shared_ptrs.
  12. Os objetos de pilha são retornados das funções por meio de referências que não são de propriedade.
  13. O heap exige a correspondência de todos os novos com o tipo correto de exclusão ou exclusão []
  14. Objetos de pilha usam listas de inicialização de construtor e RAII
  15. Objetos de heap podem ser inicializados em qualquer ponto dentro de uma função e não podem usar parâmetros de construtor
  16. Objetos de pilha usam parâmetros de construtor para inicialização
  17. O heap usa matrizes e o tamanho da matriz pode mudar no tempo de execução
  18. A pilha é para objetos únicos e o tamanho é fixo em tempo de compilação

Basicamente, os mecanismos não podem ser comparados, porque muitos detalhes são diferentes. A única coisa comum a eles é que ambos lidam com a memória de alguma forma.

tp1
fonte
1

Os computadores modernos têm várias camadas de memória cache, além de um sistema de memória principal grande, mas lento. Pode-se fazer dezenas de acessos à memória cache mais rápida no tempo necessário para ler ou gravar um byte do sistema de memória principal. Portanto, acessar um local mil vezes é muito mais rápido do que acessar 1.000 (ou mesmo 100) locais independentes uma vez cada. Como a maioria dos aplicativos aloca e desaloca repetidamente pequenas quantidades de memória próximo ao topo da pilha, os locais na parte superior da pilha são usados ​​e reutilizados uma quantidade enorme, de modo que a grande maioria (99% + em um aplicativo típico) de acessos de pilha podem ser tratados usando memória cache.

Por outro lado, se um aplicativo criar e abandonar repetidamente objetos de heap para armazenar informações de continuação, todas as versões de todos os objetos de pilha que já foram criados teriam que ser gravadas na memória principal. Mesmo que a grande maioria desses objetos fosse completamente inútil quando a CPU quisesse reciclar as páginas de cache em que eles começaram, a CPU não teria como saber disso. Conseqüentemente, a CPU precisaria perder muito tempo executando gravações lentas de informações inúteis na memória. Não é exatamente uma receita de velocidade.

Outra coisa a considerar é que, em muitos casos, é útil saber que uma referência de objeto passada para uma rotina não será usada quando a rotina terminar. Se parâmetros e variáveis ​​locais são passados ​​através da pilha e se a inspeção do código da rotina revelar que ela não persiste em uma cópia da referência passada, o código que chama a rotina pode ter certeza de que, se nenhuma referência externa ao objeto existia antes da chamada, nenhum existirá depois. Por outro lado, se parâmetros foram passados ​​por meio de objetos heap, conceitos como "após o retorno de uma rotina" se tornam um pouco mais nebulosos, pois se o código mantivesse uma cópia da continuação, seria possível que a rotina "retornasse" mais de uma vez após um chamada única.

supercat
fonte