Por que precisamos de um Heap se tudo pode ser feito com muito mais eficiência no Stack?

24

Na verdade, isso está relacionado à pergunta que fiz ontem sobre por que tanto uma pilha quanto uma pilha são necessárias nos aplicativos que usamos hoje (e por que não podemos simplesmente usar uma pilha em vez de ambas, para ter um & padrão singular a seguir).

No entanto, muitas das respostas indicaram que uma pilha é insubstituível devido ao fato de ser muitas centenas (ou milhares) de vezes mais rápida do que tentar alocar / referenciar a pilha. Sei que há um problema com a alocação dinâmica de armazenamento se acabarmos com o Heap, mas não há uma maneira de contornar isso, ou talvez, uma maneira de melhorar a pilha para que ele possa lidar com a alocação dinâmica de memória?

Templário das Trevas
fonte
4
Dois trechos da sua pergunta anterior: "a desvantagem mais importante é que ela possui espaço limitado e, portanto, manter objetos grandes nele, ou tentar usá-lo para objetos de vida longa, são idéias ruins" e "pilhas são extremamente eficientes estrutura para gerenciar dados que obedecem às regras LIFO (último a entrar, primeiro a sair) ".
Cascabel
2
Sua premissa está com defeito - nem tudo pode ser feito com muito mais eficiência na pilha. Isso não contradiz as respostas que você recebeu - que o que pode ser feito na pilha pode ser feito muito mais rápido lá.
Ingo
... supondo que seu hardware tenha uma pilha ou endereçamento relativo à pilha.
Ritch Melton
3
Estou convencido. Eu digo faça.
101311 JeffO

Respostas:

25

O problema com as pilhas é que você não pode "liberar" a memória, a menos que esteja no topo da pilha. Por exemplo, digamos que você alocou três itens de tamanhos variados:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

A pilha teria ano fundo, bno meio e cno topo. Isso se torna problemático se queremos liberar b:

free(b); // b is not on top! We have to wait until c is freed!

A solução alternativa é mover todos os dados depois be mudar se for o caso a. Isso funciona, mas exigirá 5000000 cópias neste caso - algo que será muito mais lento que um monte.

É por isso que temos um monte. Embora a alocação possa ser mais lenta que uma pilha ( O(log n)vs O(1)), as pilhas permitem que a liberação de memória em um local arbitrário seja rápida - em O(log n)comparação com a pilhaO(n)

Pubby
fonte
4
Relacionado a isso é que o Facebook não remove conteúdo do disco quando você pede para removê-lo, apenas remove o ponteiro para ele. Evidentemente, a sobrecarga de tentar desfragmentar ou tentar encontrar a lacuna equivalente no disco consome muito tempo nas taxas em que estão gravando dados; portanto, basta adicionar tudo na marca d'água máxima do disco.
Paul Tomblin
Bem, os discos do facebook podem ser vistos como heap. E tenho certeza de que eles têm algum tipo de coleta de lixo para esses discos.
deadalnix
2
@deadalnix Na verdade, este é um exemplo de uso de uma pilha enorme em vez da pilha que normalmente é usada para grandes quantidades de memória. O Facebook é um caso especial. Os dados são adicionados muito mais rapidamente do que são removidos para que a desalocação não faça uma diferença significativa na taxa de crescimento - você pode incluir deliberadamente vazamentos de memória no design para obter essa alocação de O (1).
Tom10:
7
@PaulTomblin A principal razão FB não remove o conteúdo é para que eles possam mina-lo para os seus lucros ...
quant_dev
5
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it- O que é basicamente o que acontece quando você exclui um arquivo de qualquer sistema operacional.
Robert Harvey
5

Pilha é por thread, Heap é todo o processo

Se houver 100 threads em todos os itens de trabalho que eu coloquei em uma fila, exatamente onde aloco os itens de trabalho para que qualquer um dos 100 threads os veja?

Existem outros tipos de memória também

Por exemplo, arquivos mapeados na memória, memória compartilhada, E / S mapeada (modo kernel). O argumento da eficiência é meio discutível nessas situações.

JBRWilkinson
fonte
4

Uma pilha é uma estrutura LIFO (último a entrar, primeiro a sair), na parte superior da qual é mantido um ponteiro de referência (geralmente suportado por hardware). Dito isto, qualquer coisa que você está tentando alocar na pilha em vez da pilha teria que ser uma variável local em todas as funções, no topo dessa pilha. Portanto, o principal motivo contra uma pilha é que sua rotina main () precisaria pré-alocar todas as estruturas de dados que seu programa usa (que se destinam a permanecer durante toda a duração do seu programa) antecipadamente, como todas as estruturas de dados alocadas as chamadas de função serão removidas quando as chamadas de função retornarem e seus quadros ou registros de ativação forem removidos da pilha.

Alex
fonte
3
LIFO, não FIFO.
Pubby
por vezes, também chamado FILO;)
Enone
3

As pilhas funcionam muito bem para alocações de memória que obedecem às regras LIFO (Last in First Out), ou seja, você libera a memória na ordem inversa exata que a aloca. O LIFO é um padrão de alocação de memória muito comum, talvez o mais comum. Mas não é o único padrão, ou mesmo o único padrão comum. Para escrever um programa eficiente que possa lidar com uma ampla variedade de problemas, precisamos levar em consideração os padrões menos comuns, mesmo que isso signifique uma infra-estrutura mais complexa.

Se eu conseguir todas as meta para um parágrafo: você é iniciante, como iniciante valoriza a simplicidade e as regras em preto e branco. No entanto, como iniciante, você tem apenas uma visão geral da variedade de problemas e restrições que precisam ser acomodados por programas de computador. Você está inserindo uma tecnologia que está em desenvolvimento ativo há 75 anos. Não há nada de errado em perguntar por que as coisas são do jeito que são, mas a resposta geralmente será "Sim, tentamos o método simples e direto há 50 anos e acabou por não funcionar muito bem para aulas inteiras. de problemas, então tivemos que fazer algo mais complicado ". À medida que a tecnologia avança, a simplicidade geralmente tem que dar lugar à eficiência e flexibilidade.

Charles E. Grant
fonte
0

Por outro exemplo, fechamentos. Se você empilhar pop, poderá perder o registro de ativação do seu fechamento. Portanto, se você deseja que a função anônima e seus dados persistam, você deve armazená-la em outro lugar que não seja a pilha de tempo de execução.

anon
fonte
0

Entre muitos outros motivos para alocar armazenamento de heap.

Se você deseja passar o endereço de um objeto de volta para um programa de chamada, não deve passar o endereço de uma variável da pilha, pois o armazenamento da pilha será reutilizado e possivelmente substituído pela próxima função chamada. Você precisa obter o armazenamento necessário usando malloc () para garantir que ele não seja sobrescrito por chamadas para funções subseqüentes.

Você pode passar endereços de itens de pilha de sua função para funções que você chama, porque você pode garantir que elas existam até que seu programa "retorne ()". Mas assim que sua função retornar, todo o armazenamento da pilha estará disponível.

James Anderson
fonte