Poderia ser mais eficiente para sistemas em geral eliminar Stacks 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 o heap, mas nem tudo que pode ser feito com o heap pode ser feito com a pilha. Isso está correto? Então, para simplificar, e mesmo se perdermos um pouco de desempenho com certas cargas de trabalho, não poderia ser melhor apenas ir com um padrão (ou seja, o heap)?

Pense no trade-off entre modularidade e desempenho. Eu sei que essa não é a melhor maneira de descrever esse cenário, mas, em geral, parece que a simplicidade de compreensão e design pode ser uma opção melhor, mesmo que haja um potencial para um melhor desempenho.

    
por Dark Templar 08.10.2011 / 23:02
fonte

11 respostas

30

Heaps são ruins na alocação e desalocação rápida de memória. Se você quiser pegar muitas pequenas quantidades de memória por um período limitado, um monte não é sua melhor escolha. Uma pilha, com seu algoritmo de alocação / desalocação super-simples, naturalmente se sobressai nisto (ainda mais se for embutido no hardware), e é por isso que as pessoas usam para passar argumentos para funções e armazenar variáveis locais - as mais Uma desvantagem importante é que ela tem espaço limitado e, portanto, manter objetos grandes nela ou tentar usá-la para objetos de vida longa são idéias ruins.

Livrar-se da pilha completamente para simplificar uma linguagem de programação é a maneira errada IMO - uma abordagem melhor seria abstrair as diferenças, deixar o compilador descobrir que tipo de armazenamento usar, enquanto o programador coloca juntos construtos de nível mais alto que estão mais próximos do modo 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 primitivos alocados em pilha ('tipos de referência' versus 'tipos de valor' no jargão .NET), totalmente transparentes ou com algumas diferenças funcionais que você deve entender para usar o idioma corretamente (mas você não precisa saber como uma pilha e um heap funcionam internamente).

    
por 09.10.2011 / 00:06
fonte
8

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

    
por 09.10.2011 / 01:00
fonte
8

Não

A área de pilha em C ++ é incrivelmente rápida em comparação. Não me atrevo a nenhum desenvolvedor experiente em C ++ estar aberto para desabilitar essa funcionalidade.

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

Exercitando essa escolha

Se você quer construir uma biblioteca ou programa que requer que todo objeto seja alocado dinamicamente, você pode fazer isso com C ++. Ele 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, porque ambas são necessárias para implementações boas / rápidas.

Alternativas

Existem outras linguagens que requerem que o armazenamento de cada objeto seja criado no heap; é bastante lento, de tal forma que compromete os designs (programas do mundo real) de uma maneira que é pior do que ter que aprender ambos (IMO).

Ambos são importantes, e o C ++ dá a você o poder de usar ambos efetivamente para cada cenário dado. Dito isto, a linguagem C ++ pode não ser ideal para o seu projeto, se esses fatores em seu OP forem importantes para você (por exemplo, ler em idiomas de nível superior).

    
por 09.10.2011 / 00:27
fonte
6

Then for simplicity's sake, and even if we do lose a little amount of performance with certain workloads, couldn't it be better to just go with one standard (ie, the heap)?

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

Como outros apontaram, as pilhas são uma estrutura extremamente eficiente para gerenciar dados que obedecem às regras LIFO (last in first out). Alocação de memória / liberação na pilha geralmente é apenas uma alteração em um registrador na CPU. Alterar um registrador é quase sempre uma das operações mais rápidas que um processador pode executar.

O heap 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, cada 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 tem que alternar do modo de usuário para o modo kernel, e sempre que isso acontece, o sistema operacional pode decidir que outros programas têm necessidades mais urgentes e que seu programa precisará aguardar.

    
por 09.10.2011 / 00:46
fonte
5

Simula usou o monte para tudo. Colocar tudo no heap sempre induz um nível a mais de indireção para variáveis locais, e isso coloca pressão adicional no Garbage Collector (você tem que levar em consideração que os Garbage Collectors realmente foram sugados naquela época). Em parte, é por isso que Bjarne inventou o C ++.

    
por 08.10.2011 / 23:07
fonte
3

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

    
por 09.10.2011 / 00:09
fonte
2

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

Como a alocação de pilha leva quase nenhum tempo, uma alocação mesmo em um heap muito eficiente será de 100k (se não for 1M +) de 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 um contador de loop sendo alocado um milhão de vezes mais devagar.

Se o hardware for rápido o suficiente, você pode escrever um aplicativo que use somente heap. Mas agora imaginando que tipo de aplicativo você poderia escrever se tirasse proveito do heap e usasse o mesmo hardware.

    
por 09.10.2011 / 00:02
fonte
2

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

link

Se eu o ler corretamente, esses caras modificaram um compilador C para alocar "quadros de pilha" no heap e, em seguida, usar a coleta de lixo para desalocar os quadros em vez de estourar a pilha.

Os "quadros de pilha" alocados em pilha superam os "quadros de pilha" alocados em heap de forma decisiva.

    
por 09.10.2011 / 05:13
fonte
1

Como a pilha de chamadas vai funcionar em um heap? Essencialmente, você teria que alocar uma pilha no heap em cada programa, então porque não ter o hardware OS + fazendo isso para você?

Se você quer que as coisas sejam realmente simples e eficientes, basta dar ao usuário seu pedaço de memória e deixá-lo lidar com isso. Claro, ninguém quer implementar tudo sozinho e é por isso que temos uma pilha e uma pilha.

    
por 09.10.2011 / 00:09
fonte
1

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

  1. A alocação de heap tem uma limitação que sizeof (a [0]) == sizeof (a [1])
  2. A alocação de pilha tem uma limitação de que sizeof (a) é uma constante de 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 fazer árvores dimensionadas em tempo de compilação
  5. O heap requer rastreamento de propriedade
  6. A alocação e a desalocação da pilha são automáticas
  7. A memória heap pode ser facilmente passada de um escopo para outro por meio de ponteiros
  8. A memória de 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. O heap é ruim para o desempenho
  10. A pilha é bem rápida
  11. Objetos de heap são retornados de funções por meio de ponteiros que assumem a propriedade. Ou shared_ptrs.
  12. Os objetos de pilha são retornados de funções por meio de referências que não são apropriadas.
  13. O heap requer correspondência a cada novo com o tipo correto de excluir ou excluir []
  14. Os objetos de pilha usam listas de inicialização de RAII e de construtor
  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. Os objetos de pilha usam parâmetros de construtor para inicialização
  17. O heap usa arrays e o tamanho do array pode mudar em tempo de execução
  18. A pilha é para objetos únicos e o tamanho é fixado em tempo de compilação

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

    
por 09.10.2011 / 01:07
fonte
1

Os computadores modernos possuem várias camadas de memória cache, além de um sistema de memória principal grande, mas lento. É possível 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. Assim, acessar um local mil vezes é muito mais rápido do que acessar 1.000 (ou mesmo 100) locais independentes uma vez em cada. Como a maioria dos aplicativos aloca e desaloca repetidamente pequenas quantidades de memória perto do topo da pilha, os locais na parte superior da pilha são usados e reutilizados em uma quantidade enorme, de tal forma que a grande maioria (99% + em um aplicativo típico) de acessos de pilha podem ser manipulados usando a memória cache.

Por outro lado, se um aplicativo cria e abandona repetidamente objetos de heap para armazenar informações de continuação, cada versão de cada objeto de pilha que já tenha sido criado deve ser gravada na memória principal. Mesmo se a grande maioria desses objetos fosse completamente inútil no momento em que a CPU quisesse reciclar as páginas de cache em que eles começaram, a CPU não teria como saber disso. Consequentemente, a CPU teria que perder muito tempo executando gravações de memória lenta de informações inúteis. 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 depois que a rotina sair. Se parâmetros e variáveis locais forem passados pela pilha, e se a inspeção do código da rotina revelar que não persiste uma cópia da referência passada, então o código que chama a rotina pode ter certeza de que, se não houver referência externa à pilha objeto existia antes da chamada, nenhum irá existir depois. Por outro lado, se os parâmetros foram passados através de objetos heap, conceitos como "depois de retornos de rotina" tornam-se 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 uma chamada única.

    
por 27.10.2012 / 21:09
fonte

Tags