O que é mais rápido: alocação de pilha ou alocação de pilha

503

Essa pergunta pode parecer bastante elementar, mas esse é um debate que tive com outro desenvolvedor com quem trabalho.

Eu estava cuidando para empilhar alocar as coisas onde podia, em vez de colocá-las na pilha. Ele estava conversando comigo, olhando por cima do meu ombro e comentou que não era necessário, porque eles têm o mesmo desempenho.

Eu sempre tive a impressão de que o crescimento da pilha era tempo constante, e o desempenho da alocação de heap dependia da complexidade atual do heap para alocação (encontrar um buraco no tamanho adequado) e desalocação (furos em colapso para reduzir a fragmentação, como muitas implementações de bibliotecas padrão levam tempo para fazer isso durante exclusões, se não me engano).

Isso me parece algo que provavelmente seria muito dependente do compilador. Para este projeto em particular, estou usando um compilador Metrowerks para a arquitetura PPC . A compreensão dessa combinação seria muito útil, mas, em geral, para o GCC e o MSVC ++, qual é o caso? A alocação de heap não tem o mesmo desempenho que a alocação de pilha? Não há diferença? Ou as diferenças são tão pequenas que se tornam uma micro-otimização inútil.

Adão
fonte
11
Eu sei que isso é muito antigo, mas seria bom ver alguns trechos de C / C ++ demonstrando os diferentes tipos de alocação.
Joseph Weissman
42
O seu aventureiro é terrivelmente ignorante, mas o mais importante é que ele é perigoso porque faz afirmações oficiais sobre coisas sobre as quais ele é terrivelmente ignorante. Consiga essas pessoas da sua equipe o mais rápido possível.
19713 Jim Balter
5
Observe que a pilha geralmente é muito maior que a pilha. Se você receber grandes quantidades de dados, precisará realmente colocá-los no heap ou alterar o tamanho da pilha no sistema operacional.
Paul Draper
1
Todas as otimizações são, a menos que você tenha benchmarks ou argumentos de complexidade que comprovem o contrário, por padrão, micro-otimizações inúteis.
Björn Lindqvist
2
Gostaria de saber se o seu colega de trabalho tem principalmente experiência em Java ou C #. Nesses idiomas, quase tudo é alocado por heap, o que pode levar a tais suposições.
Cort Ammon

Respostas:

493

A alocação de pilha é muito mais rápida, pois tudo o que realmente faz é mover o ponteiro da pilha. Usando conjuntos de memória, você pode obter desempenho comparável com a alocação de heap, mas isso vem com uma leve complexidade adicional e suas próprias dores de cabeça.

Além disso, pilha versus pilha não é apenas uma consideração de desempenho; também informa muito sobre a vida útil esperada dos objetos.

Torbjörn Gyllebring
fonte
211
E o mais importante, a pilha é sempre quente, a memória que você recebe é muito mais provável que seja no cache do que qualquer memória distante pilha alocada
Benoît
47
Em algumas arquiteturas (na maioria incorporadas, que eu conheço), a pilha pode ser armazenada na memória rápida na matriz (por exemplo, SRAM). Isso pode fazer uma enorme diferença!
Leander
38
Porque a pilha é realmente, uma pilha. Você não pode liberar um pedaço de memória usado pela pilha, a menos que esteja em cima dela. Não há gerenciamento, você coloca ou empurra coisas nele. Por outro lado, a memória heap é gerenciada: solicita ao kernel pedaços de memória, talvez os divida, os mescla, os reutilize e os libere. A pilha é realmente destinada a alocações rápidas e curtas.
Benoit
24
@ Pacerier Porque a pilha é muito menor que a pilha. Se você deseja alocar grandes matrizes, é melhor alocá-las no Heap. Se você tentar alocar uma grande matriz na pilha, isso causará um estouro de pilha. Tente, por exemplo, em C ++, isso: int t [100000000]; Tente por exemplo t [10000000] = 10; e depois cout << t [10000000]; Isso deve causar um estouro de pilha ou simplesmente não funciona e não mostra nada. Mas se você alocar a matriz na pilha: int * t = new int [100000000]; e faça as mesmas operações depois, funcionará porque o Heap possui o tamanho necessário para uma matriz tão grande.
Lilian A. Moraru
7
@Pacerier A razão mais óbvia é que os objetos na pilha ir fora do escopo ao sair do bloco que são alocados em.
Jim Balter
166

A pilha é muito mais rápida. Ele literalmente usa apenas uma única instrução na maioria das arquiteturas, na maioria dos casos, por exemplo, no x86:

sub esp, 0x10

(Isso move o ponteiro da pilha para baixo em 0 x 10 bytes e, assim, "aloca" esses bytes para uso por uma variável.)

Obviamente, o tamanho da pilha é muito, muito finito, pois você descobrirá rapidamente se usar demais a alocação da pilha ou tentar fazer recursão :-)

Além disso, há poucas razões para otimizar o desempenho do código que não é necessário, como demonstrado por criação de perfil. A "otimização prematura" geralmente causa mais problemas do que vale a pena.

Minha regra de ouro: se eu sei que vou precisar de alguns dados em tempo de compilação e com menos de algumas centenas de bytes, eu os alocarei em pilhas. Caso contrário, eu o alocarei em heap.

Dan Lenski
fonte
20
Uma instrução, e que geralmente é compartilhada por TODOS os objetos na pilha.
#
9
Explicou bem, especialmente a questão de precisá-lo de forma verificável. Fico continuamente impressionado com a maneira como as preocupações das pessoas com o desempenho são equivocadas.
Mike Dunlavey
6
"Desalocação" também é muito simples e é feito com uma única leaveinstrução.
doc
15
Lembre-se do custo "oculto" aqui, especialmente pela primeira vez que você estende a pilha. Fazer isso pode resultar em uma falha de página, uma mudança de contexto para o kernel que precisa fazer algum trabalho para alocar a memória (ou carregá-la do swap, no pior caso).
Nos
2
Em alguns casos, você pode até alocá-lo com 0 instruções. Se alguma informação for conhecida sobre quantos bytes precisam ser alocados, o compilador poderá alocá-los antecipadamente ao mesmo tempo em que aloca outras variáveis ​​de pilha. Nesses casos, você não paga nada!
Cort Ammon
119

Honestamente, é trivial escrever um programa para comparar o desempenho:

#include <ctime>
#include <iostream>

namespace {
    class empty { }; // even empty classes take up 1 byte of space, minimum
}

int main()
{
    std::clock_t start = std::clock();
    for (int i = 0; i < 100000; ++i)
        empty e;
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
}

Dizem que uma consistência tola é o hobgoblin das mentes pequenas . Aparentemente, os otimizadores de compilação são os truques da mente de muitos programadores. Essa discussão costumava estar na parte inferior da resposta, mas aparentemente as pessoas não podem se incomodar em ler até agora, então estou subindo aqui para evitar perguntas que já respondi.

Um compilador de otimização pode perceber que esse código não faz nada e pode otimizar tudo. O trabalho do otimizador é fazer coisas assim, e combater o otimizador é uma tarefa fácil.

Eu recomendaria compilar esse código com a otimização desativada, porque não há uma boa maneira de enganar todos os otimizadores atualmente em uso ou que estarão em uso no futuro.

Qualquer pessoa que ligar o otimizador e depois reclamar sobre combatê-lo deve estar sujeita ao ridículo público.

Se eu me importasse com precisão de nanossegundos, não usaria std::clock() . Se eu quisesse publicar os resultados como tese de doutorado, faria um acordo maior sobre isso e provavelmente compararia o GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC e outros compiladores. No momento, a alocação de heap leva centenas de vezes mais que a alocação de pilha, e não vejo nada de útil em investigar mais a questão.

O otimizador tem a missão de se livrar do código que estou testando. Não vejo motivo para dizer ao otimizador para executar e depois tentar enganar o otimizador para que ele não seja realmente otimizado. Mas se eu considerasse importante fazer isso, faria um ou mais dos seguintes procedimentos:

  1. Adicione um membro de dados emptye acesse esse membro de dados no loop; mas se eu ler apenas a partir do membro de dados, o otimizador poderá fazer dobragens constantes e remover o loop; se eu apenas gravar no membro de dados, o otimizador poderá pular tudo, exceto a última iteração do loop. Além disso, a pergunta não era "alocação de pilha e acesso a dados x alocação de pilha e acesso a dados".

  2. Declare e volatile, mas volatilegeralmente é compilado incorretamente (PDF).

  3. Pegue o endereço edentro do loop (e talvez atribua-o a uma variável que é declarada externe definida em outro arquivo). Mas mesmo neste caso, o compilador pode perceber que - pelo menos na pilha - esempre será alocado no mesmo endereço de memória e, em seguida, fará dobragem constante como em (1) acima. Eu recebo todas as iterações do loop, mas o objeto nunca é realmente alocado.

Além do óbvio, esse teste é falho, pois mede tanto a alocação quanto a desalocação, e a pergunta original não perguntou sobre desalocação. É claro que as variáveis ​​alocadas na pilha são desalocadas automaticamente no final de seu escopo; portanto, não chamar delete(1) distorceria os números (a desalocação da pilha é incluída nos números sobre alocação da pilha, portanto, é justo medir a desalocação da pilha) e ( 2) causar um vazamento de memória bastante ruim, a menos que mantenhamos uma referência ao novo ponteiro e ligemos deletedepois que tivermos medido o tempo.

Na minha máquina, usando o g ++ 3.4.4 no Windows, recebo "0 ticks de clock" para alocação de pilha e heap para algo menor que 100000 alocações e mesmo assim recebo "0 ticks de relógio" para alocação de pilha e "15 ticks de relógio "para alocação de heap. Quando medo 10.000.000 de alocações, a alocação de pilha recebe 31 marcações de clock e a alocação de heap leva 1562 marcações de clock.


Sim, um compilador de otimização pode impedir a criação dos objetos vazios. Se bem entendi, ele pode até eliminar todo o primeiro loop. Quando ampliei as iterações para 10.000.000 de alocação de pilha, recebi 31 ticks de clock e alocação de heap, 1562 ticks de clock. Eu acho que é seguro dizer que, sem dizer ao g ++ para otimizar o executável, o g ++ não escapou aos construtores.


Nos anos desde que escrevi isso, a preferência no Stack Overflow foi postar o desempenho de compilações otimizadas. Em geral, acho que isso está correto. No entanto, ainda acho tolo pedir ao compilador que otimize o código quando, na verdade, você não deseja que esse código seja otimizado. Parece-me muito semelhante a pagar mais pelo estacionamento com manobrista, mas recusando-me a entregar as chaves. Nesse caso em particular, não quero o otimizador em execução.

Usando uma versão ligeiramente modificada do benchmark (para abordar o ponto válido em que o programa original não alocava algo na pilha a cada vez no loop) e compilando sem otimizações, mas vinculando-se às bibliotecas de lançamento (para abordar o ponto válido que não usamos não deseja incluir qualquer lentidão causada por links para bibliotecas de depuração):

#include <cstdio>
#include <chrono>

namespace {
    void on_stack()
    {
        int i;
    }

    void on_heap()
    {
        int* i = new int;
        delete i;
    }
}

int main()
{
    auto begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_stack();
    auto end = std::chrono::system_clock::now();

    std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count());

    begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_heap();
    end = std::chrono::system_clock::now();

    std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count());
    return 0;
}

exibe:

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

no meu sistema quando compilado com a linha de comando cl foo.cc /Od /MT /EHsc.

Você pode não concordar com minha abordagem para obter uma compilação não otimizada. Tudo bem: sinta-se à vontade, modifique o benchmark o quanto quiser. Quando ligo a otimização, recebo:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Não porque a alocação de pilha seja realmente instantânea, mas porque qualquer compilador meio decente pode perceber que on_stacknão faz nada de útil e pode ser otimizado. O GCC no meu laptop Linux também percebe que on_heapnão faz nada de útil e também o otimiza:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds
Max Lybbert
fonte
2
Além disso, você deve adicionar um loop de "calibração" no início de sua função principal, algo para lhe dar uma idéia de quanto tempo você está recebendo por ciclo de loop e ajustar os outros loops para garantir que o seu exemplo seja executado. algum tempo, em vez da constante fixa que você está usando.
Joe Pineda
2
Também estou feliz por aumentar o número de vezes que cada loop de opção é executado (além de instruir o g ++ a não otimizar?) Produziu resultados significativos. Então agora temos fatos concretos para dizer que a pilha é mais rápida. Obrigada pelos teus esforços!
Joe Pineda
7
O trabalho do otimizador é livrar-se de códigos como este. Existe um bom motivo para ativar o otimizador e impedir que ele realmente otimize? Editei a resposta para tornar as coisas ainda mais claras: se você gosta de lutar contra o otimizador, esteja preparado para aprender como são os escritores de compiladores inteligentes.
Max Lybbert
3
Estou muito atrasado, mas também vale a pena mencionar aqui que a alocação de heap solicita memória através do kernel, portanto o desempenho atingido também depende muito da eficiência do kernel. Usando esse código com o Linux (Linux 3.10.7-gentoo # 2 SMP Wed 4 de setembro 18:58:21 MDT 2013 x86_64), modificando para o cronômetro HR e usando 100 milhões de iterações em cada loop, obtém-se este desempenho: stack allocation took 0.15354 seconds, heap allocation took 0.834044 secondscom -O0set, make A alocação de heap do Linux é mais lenta em um fator de cerca de 5,5 na minha máquina específica.
Taywee
4
Nas janelas sem otimizações (compilação de depuração), ele usará o heap de depuração, que é muito mais lento que o heap sem depuração. Não acho uma má idéia "enganar" o otimizador. Os escritores de compiladores são inteligentes, mas os compiladores não são de IA.
paulm 11/05
30

Uma coisa interessante que aprendi sobre a alocação de pilha versus heap no processador Xbox 360 Xenon, que também pode ser aplicada a outros sistemas com vários núcleos, é que a alocação no heap faz com que uma seção crítica seja inserida para interromper todos os outros núcleos, para que a alocação não ocorra. não entre em conflito. Assim, em um loop restrito, a Alocação de pilha era o caminho a seguir para matrizes de tamanho fixo, pois evitava paradas.

Essa pode ser outra aceleração a ser considerada se você estiver codificando para multicore / multiproc, pois sua alocação de pilha será visível apenas pelo núcleo executando sua função de escopo, e isso não afetará outros núcleos / CPUs.

Furious Coder
fonte
4
Isso é verdade para a maioria das máquinas multicore, não apenas para o Xenon. Até a Cell precisa fazer isso porque você pode estar executando dois threads de hardware nesse núcleo de PPU.
Crashworks
15
Isso é um efeito da implementação (particularmente ruim) do alocador de heap. Alocadores de heap melhores não precisam adquirir um bloqueio em todas as alocações.
26610 Chris Dodd
19

Você pode escrever um alocador de heap especial para tamanhos específicos de objetos com desempenho muito alto. No entanto, o alocador de heap geral não é particularmente eficiente.

Também concordo com Torbjörn Gyllebring sobre a vida útil esperada dos objetos. Bom ponto!

Chris Jester-Young
fonte
1
Isso às vezes é chamado de alocação de laje.
Benoit
8

Eu não acho que a alocação de pilha e a alocação de heap sejam geralmente intercambiáveis. Espero também que o desempenho de ambos seja suficiente para uso geral.

Eu recomendo fortemente para itens pequenos, o que for mais adequado ao escopo da alocação. Para itens grandes, a pilha provavelmente é necessária.

Em sistemas operacionais de 32 bits que possuem vários threads, a pilha geralmente é bastante limitada (embora geralmente tenha pelo menos alguns mb), porque o espaço de endereço precisa ser dividido e, mais cedo ou mais tarde, uma pilha de threads será executada em outra. Em sistemas de encadeamento único (Linux glibc de encadeamento único de qualquer maneira), a limitação é muito menor porque a pilha pode crescer e crescer.

Nos sistemas operacionais de 64 bits, há espaço de endereço suficiente para tornar as pilhas de threads muito grandes.

MarkR
fonte
6

Geralmente, a alocação de pilha consiste apenas em subtrair o registro do ponteiro de pilha. Isso é muito mais rápido do que pesquisar em um monte.

Às vezes, a alocação de pilha requer a adição de uma página (s) de memória virtual. Adicionar uma nova página de memória zerada não requer a leitura de uma página do disco; portanto, isso ainda será muito mais rápido do que pesquisar em um heap (especialmente se parte do heap também tiver sido paginada). Em uma situação rara, e você poderia construir um exemplo, espaço suficiente está disponível em parte do heap que já está na RAM, mas a alocação de uma nova página para a pilha precisa aguardar que outra página seja gravada para o disco. Nessa rara situação, a pilha é mais rápida.

Programador do Windows
fonte
Não acho que a pilha seja "pesquisada", a menos que seja paginada. Certamente a memória de estado sólido usa um multiplexador e pode obter acesso direto à memória, daí a Memória de Acesso Aleatório.
Joe Phillips
4
Aqui está um exemplo. O programa de chamada pede para alocar 37 bytes. A função de biblioteca procura um bloco de pelo menos 40 bytes. O primeiro bloco da lista livre possui 16 bytes. O segundo bloco da lista livre possui 12 bytes. O terceiro bloco tem 44 bytes. A biblioteca para de procurar nesse ponto.
Programador Windows
6

Além da vantagem de desempenho de ordem de magnitude sobre a alocação de heap, a alocação de pilha é preferível para aplicativos de servidor de longa execução. Até os melhores heaps gerenciados acabam ficando tão fragmentados que o desempenho do aplicativo diminui.

Jay
fonte
4

Uma pilha tem uma capacidade limitada, enquanto uma pilha não. A pilha típica para um processo ou thread é de cerca de 8K. Você não pode alterar o tamanho depois de alocado.

Uma variável de pilha segue as regras de escopo, enquanto uma pilha não. Se o ponteiro de sua instrução ultrapassar uma função, todas as novas variáveis ​​associadas à função desaparecem.

Mais importante ainda, você não pode prever a cadeia geral de chamadas de funções com antecedência. Portanto, uma mera alocação de 200 bytes de sua parte pode aumentar o estouro da pilha. Isso é especialmente importante se você estiver escrevendo uma biblioteca, não um aplicativo.

yogman
fonte
1
A quantidade de espaço de endereço virtual alocado para uma pilha de modo de usuário em um sistema operacional moderno provavelmente será pelo menos 64 kB ou maior por padrão (1 MB no Windows). Você está falando sobre tamanhos de pilha do kernel?
bk1e
1
Na minha máquina, o tamanho padrão da pilha para um processo é 8 MB, não kB. Quantos anos tem o seu computador?
Greg Rogers
3

Eu acho que a vida é crucial, e se a coisa que está sendo alocada deve ser construída de uma maneira complexa. Por exemplo, na modelagem orientada a transações, você geralmente precisa preencher e passar uma estrutura de transação com vários campos para as funções de operação. Veja o padrão OSCI SystemC TLM-2.0 para um exemplo.

Alocá-los na pilha perto da chamada para a operação tende a causar uma sobrecarga enorme, pois a construção é cara. A boa maneira de alocar no heap e reutilizar os objetos de transação é o pool ou uma política simples como "este módulo precisa apenas de um objeto de transação".

Isso é muitas vezes mais rápido do que alocar o objeto em cada chamada de operação.

O motivo é simplesmente que o objeto tem uma construção cara e uma vida útil bastante longa.

Eu diria: tente os dois e veja o que funciona melhor no seu caso, porque pode realmente depender do comportamento do seu código.

jakobengblom2
fonte
3

Provavelmente, o maior problema de alocação de heap versus alocação de pilha é que a alocação de heap no caso geral é uma operação ilimitada e, portanto, você não pode usá-lo quando o tempo é um problema.

Para outros aplicativos em que o tempo não é um problema, pode não ser tão importante, mas se você alocar muito, isso afetará a velocidade de execução. Sempre tente usar a pilha para memória de curta duração e frequentemente alocada (por exemplo, em loops) e pelo maior tempo possível - faça alocação de heap durante a inicialização do aplicativo.

larsivi
fonte
3

Não é a alocação de pilha jsut que é mais rápida. Você também ganha muito ao usar variáveis ​​de pilha. Eles têm melhor localidade de referência. E, finalmente, a desalocação também é muito mais barata.

MSalters
fonte
3

A alocação de pilha é algumas instruções, enquanto o alocador de heap de rtos mais rápido conhecido por mim (TLSF) usa, em média, na ordem de 150 instruções. Além disso, as alocações de pilha não exigem um bloqueio, pois usam armazenamento local de encadeamento, o que é outra grande conquista de desempenho. Portanto, as alocações de pilha podem ser de 2 a 3 pedidos de magnitude mais rapidamente, dependendo da intensidade do multithreaded do seu ambiente.

Em geral, a alocação de heap é seu último recurso se você se preocupa com o desempenho. Uma opção intermediária viável pode ser um alocador de pool fixo, que também é apenas algumas instruções e tem muito pouco overhead por alocação, por isso é ótimo para objetos pequenos de tamanho fixo. No lado negativo, ele funciona apenas com objetos de tamanho fixo, não é inerentemente seguro para threads e tem problemas de fragmentação de bloco.

Andrei Pokrovsky
fonte
3

Preocupações específicas da linguagem C ++

Primeiro de tudo, não há alocação de "pilha" ou "pilha" exigida pelo C ++ . Se você está falando sobre objetos automáticos em escopos de bloco, eles ainda não são "alocados". (BTW, a duração automática do armazenamento em C definitivamente NÃO é a mesma que "alocada"; a última é "dinâmica" na linguagem C ++.) A memória alocada dinamicamente está no armazenamento gratuito , não necessariamente no "heap", embora o este geralmente é a implementação (padrão) .

Embora, de acordo com as regras semânticas da máquina abstrata , os objetos automáticos ainda ocupem memória, uma implementação em C ++ em conformidade pode ignorar esse fato quando provar que isso não importa (quando não altera o comportamento observável do programa). Essa permissão é concedida pela regra como no ISO C ++, que também é a cláusula geral que permite as otimizações usuais (e também existe uma regra quase igual na ISO C). Além da regra como se, o ISO C ++ também deve regras de exclusão de cópiapermitir a omissão de criações específicas de objetos. As chamadas de construtor e destruidor envolvidas são assim omitidas. Como resultado, os objetos automáticos (se houver) nesses construtores e destruidores também são eliminados, em comparação com a semântica abstrata ingênua implícita no código-fonte.

Por outro lado, a alocação gratuita de loja é definitivamente "alocação" por design. Sob as regras ISO C ++, essa alocação pode ser alcançada através de uma chamada de uma função de alocação . No entanto, desde a ISO C ++ 14, existe uma nova regra (não como se) que permite mesclar ::operator newchamadas da função de alocação global (ie ) em casos específicos. Portanto, partes das operações de alocação dinâmica também podem não funcionar, como no caso de objetos automáticos.

As funções de alocação alocam recursos de memória. Os objetos ainda podem ser alocados com base na alocação usando alocadores. Para objetos automáticos, eles são apresentados diretamente - embora a memória subjacente possa ser acessada e usada para fornecer memória a outros objetos (por posicionamento new), mas isso não faz muito sentido como armazenamento gratuito, porque não há como mover o recursos em outros lugares.

Todas as outras preocupações estão fora do escopo do C ++. No entanto, eles ainda podem ser significativos.

Sobre implementações de C ++

O C ++ não expõe registros de ativação reificados ou algum tipo de continuação de primeira classe (por exemplo, pelos famosos call/cc); não há como manipular diretamente os quadros de registro de ativação - onde a implementação precisa colocar os objetos automáticos. Uma vez que não há interoperações (não portáteis) com a implementação subjacente (código não portável "nativo", como código de montagem em linha), uma omissão da alocação subjacente dos quadros pode ser bastante trivial. Por exemplo, quando a função chamada é incorporada, os quadros podem ser mesclados efetivamente com outros, portanto não há como mostrar o que é a "alocação".

No entanto, uma vez respeitadas as interoperações, as coisas estão ficando complexas. Uma implementação típica do C ++ expõe a capacidade de interoperabilidade no ISA (arquitetura do conjunto de instruções) com algumas convenções de chamada como o limite binário compartilhado com o código nativo (máquina no nível do ISA). Isso seria explicitamente oneroso, principalmente ao manter o ponteiro da pilha , que geralmente é mantido diretamente por um registro no nível ISA (com provavelmente instruções específicas da máquina para acessar). O ponteiro da pilha indica o limite do quadro superior da chamada de função (atualmente ativa). Quando uma chamada de função é inserida, é necessário um novo quadro e o ponteiro da pilha é adicionado ou subtraído (dependendo da convenção do ISA) por um valor não inferior ao tamanho de quadro necessário. O quadro é então dito alocadoquando o ponteiro da pilha após as operações. Parâmetros de funções também podem ser passados ​​para o quadro da pilha, dependendo da convenção de chamada usada para a chamada. O quadro pode conter a memória de objetos automáticos (provavelmente incluindo os parâmetros) especificados pelo código-fonte C ++. No sentido de tais implementações, esses objetos são "alocados". Quando o controle sai da chamada de função, o quadro não é mais necessário, geralmente é liberado restaurando o ponteiro da pilha de volta ao estado anterior à chamada (salvo anteriormente de acordo com a convenção de chamada). Isso pode ser visto como "desalocação". Essas operações tornam o registro de ativação efetivamente uma estrutura de dados LIFO, por isso costuma ser chamada de " pilha (chamada) ".

Como a maioria das implementações em C ++ (principalmente as que visam o código nativo no nível ISA e usam a linguagem assembly como saída imediata) usam estratégias semelhantes como essa, um esquema de "alocação" tão confuso é popular. Essas alocações (bem como desalocações) passam ciclos de máquina e podem ser caras quando as chamadas (não otimizadas) ocorrem com frequência, mesmo que as microarquiteturas de CPU modernas possam ter otimizações complexas implementadas por hardware para o padrão de código comum (como usar um empilhar o mecanismo na implementação PUSH/ POPinstruções).

Mas, de qualquer maneira, em geral, é verdade que o custo da alocação de quadros de pilha é significativamente menor do que uma chamada para uma função de alocação que opera o armazenamento gratuito (a menos que seja totalmente otimizado) , o que em si pode ter centenas (se não milhões de :-) operações para manter o ponteiro da pilha e outros estados. As funções de alocação geralmente são baseadas na API fornecida pelo ambiente hospedado (por exemplo, tempo de execução fornecido pelo sistema operacional). Diferente do objetivo de reter objetos automáticos para chamadas de funções, essas alocações são de uso geral, portanto, elas não terão estrutura de quadro como uma pilha. Tradicionalmente, eles alocam espaço do armazenamento de pool chamado heap (ou vários heaps). Diferente da "pilha", o conceito "pilha" aqui não indica a estrutura de dados que está sendo usada;é derivado de implementações de idiomas anteriores décadas atrás . (BTW, a pilha de chamadas geralmente é alocada com tamanho fixo ou especificado pelo usuário do heap pelo ambiente na inicialização do programa ou do encadeamento.) A natureza dos casos de uso torna as alocações e desalocações de um heap muito mais complicadas (do que pressionar ou soltar). quadros de pilha) e dificilmente possível de ser otimizado diretamente pelo hardware.

Efeitos no acesso à memória

A alocação de pilha usual sempre coloca o novo quadro no topo, por isso possui uma boa localidade. Isso é amigável para o cache. OTOH, a memória alocada aleatoriamente no armazenamento gratuito não possui essa propriedade. Desde o ISO C ++ 17, existem modelos de recursos de pool fornecidos por <memory>. O objetivo direto dessa interface é permitir que os resultados de alocações consecutivas sejam próximos na memória. Isso reconhece o fato de que essa estratégia geralmente é boa para desempenho com implementações contemporâneas, por exemplo, ser amigável para armazenar em cache em arquiteturas modernas. É sobre o desempenho do acesso, e não da alocação .

Concorrência

A expectativa de acesso simultâneo à memória pode ter efeitos diferentes entre a pilha e as pilhas. Uma pilha de chamadas geralmente pertence exclusivamente a um encadeamento de execução em uma implementação C ++. OTOH, heaps geralmente são compartilhados entre os threads em um processo. Para esses heaps, as funções de alocação e desalocação precisam proteger a estrutura de dados administrativos internos compartilhados da corrida de dados. Como resultado, alocações e desalocações de heap podem ter uma sobrecarga adicional devido a operações de sincronização interna.

Eficiência espacial

Devido à natureza dos casos de uso e das estruturas de dados internas, os heaps podem sofrer fragmentação da memória interna , enquanto a pilha não. Isso não afeta diretamente o desempenho da alocação de memória, mas em um sistema com memória virtual , a baixa eficiência de espaço pode piorar o desempenho geral do acesso à memória. Isso é particularmente terrível quando o HDD é usado como uma troca de memória física. Pode causar latência bastante longa - às vezes bilhões de ciclos.

Limitações de alocações de pilha

Embora as alocações de pilha geralmente tenham desempenho superior às alocações de heap na realidade, isso certamente não significa que as alocações de pilha sempre possam substituir as alocações de heap.

Primeiro, não há como alocar espaço na pilha com um tamanho especificado em tempo de execução de maneira portátil com o ISO C ++. Existem extensões fornecidas por implementações como allocao VLA (matriz de comprimento variável) do G ++, mas existem razões para evitá-las. (IIRC, a fonte Linux remove o uso do VLA recentemente.) (Observe também que a ISO C99 possui o VLA obrigatório, mas a ISO C11 torna o suporte opcional.)

Segundo, não há uma maneira confiável e portátil de detectar a exaustão do espaço na pilha. Isso geralmente é chamado de estouro de pilha (hmm, a etimologia deste site) , mas provavelmente com mais precisão, estouro de pilha . Na realidade, isso geralmente causa acesso inválido à memória e o estado do programa é corrompido (... ou talvez pior, uma falha de segurança). De fato, o ISO C ++ não tem um conceito de "pilha" e o torna indefinido quando o recurso está esgotado . Tenha cuidado com a quantidade de espaço que resta para objetos automáticos.

Se o espaço da pilha acabar, há muitos objetos alocados na pilha, que podem ser causados ​​por chamadas de funções ativas ou uso inadequado de objetos automáticos. Tais casos podem sugerir a existência de erros, por exemplo, uma chamada de função recursiva sem condições corretas de saída.

No entanto, chamadas recursivas profundas às vezes são desejadas. Nas implementações de idiomas que exigem suporte a chamadas ativas não acopladas (onde a profundidade da chamada é limitada apenas pela memória total), é impossível usar a pilha de chamadas nativa (contemporânea) diretamente como o registro de ativação do idioma de destino, como implementações típicas de C ++. Para contornar o problema, são necessárias formas alternativas de construção dos registros de ativação. Por exemplo, SML / NJ aloca explicitamente quadros na pilha e usa pilhas de cactos . A alocação complicada desses quadros de registro de ativação geralmente não é tão rápida quanto os quadros da pilha de chamadas. No entanto, se essas linguagens forem implementadas ainda mais com a garantia de recursão adequada da cauda, a alocação direta da pilha no idioma do objeto (ou seja, o "objeto" no idioma não é armazenado como referências, mas os valores primitivos nativos que podem ser mapeados individualmente para objetos C ++ não compartilhados) são ainda mais complicados com mais penalidade de desempenho em geral. Ao usar o C ++ para implementar essas linguagens, é difícil estimar os impactos no desempenho.

FrankHB
fonte
Como stl, cada vez menos pessoas estão dispostas a diferenciar esses conceitos. Muitos caras no cppcon2018 também usam com heapfrequência.
陳力
@ 力 力 "O heap" pode ser inequívoco, com algumas implementações específicas em mente, então talvez às vezes seja bom. É redundante "em geral", no entanto.
FrankHB
O que é interoperabilidade?
陳力
@ 陳 力 Eu quis dizer qualquer tipo de interoperação de código "nativo" envolvida na fonte C ++, por exemplo, qualquer código de montagem embutido. Isso se baseia em suposições (da ABI) não cobertas pelo C ++. A interoperabilidade COM (baseada em algumas ABI específicas do Windows) é mais ou menos semelhante, embora seja principalmente neutra ao C ++.
9118 FrankHB #
2

Há um argumento geral a ser feito sobre essas otimizações.

A otimização que você obtém é proporcional à quantidade de tempo que o contador do programa realmente está nesse código.

Se você fizer uma amostra do contador do programa, descobrirá onde ele gasta seu tempo, e isso geralmente está em uma pequena parte do código e, geralmente, nas rotinas de biblioteca das quais você não tem controle.

Somente se você achar que está gastando muito tempo na alocação de pilha de seus objetos, será visivelmente mais rápido alocá-los.

Mike Dunlavey
fonte
2

A alocação de pilha quase sempre será tão rápida ou mais rápida que a alocação de heap, embora certamente seja possível para um alocador de heap simplesmente usar uma técnica de alocação baseada em pilha.

No entanto, existem problemas maiores ao lidar com o desempenho geral da alocação baseada na pilha versus heap (ou em termos um pouco melhores, alocação local x externa). Geralmente, a alocação de heap (externa) é lenta porque está lidando com muitos tipos diferentes de alocações e padrões de alocação. Reduzir o escopo do alocador que você está usando (tornando-o local para o algoritmo / código) tenderá a aumentar o desempenho sem grandes alterações. Adicionar uma melhor estrutura aos seus padrões de alocação, por exemplo, forçar uma ordem LIFO nos pares de alocação e desalocação também pode melhorar o desempenho do seu alocador usando o alocador de uma maneira mais simples e estruturada. Ou, você pode usar ou escrever um alocador ajustado para seu padrão de alocação específico; a maioria dos programas aloca alguns tamanhos discretos com frequência, portanto, um monte baseado em um buffer lateral de alguns tamanhos fixos (de preferência conhecidos) terá um desempenho extremamente bom. O Windows usa sua pilha de baixa fragmentação por esse mesmo motivo.

Por outro lado, a alocação baseada em pilha em um intervalo de memória de 32 bits também é perigosa se você tiver muitos threads. As pilhas precisam de um intervalo de memória contíguo; portanto, quanto mais threads você tiver, mais espaço de endereço virtual será necessário para que eles sejam executados sem um estouro de pilha. Isso não será um problema (por enquanto) com os de 64 bits, mas certamente pode causar estragos em programas de longa duração com muitos threads. Ficar sem espaço de endereço virtual devido à fragmentação é sempre uma tarefa difícil.

MSN
fonte
Discordo da sua primeira frase.
Brian beuning
2

Como outros já disseram, a alocação de pilha é geralmente muito mais rápida.

No entanto, se seus objetos são caros de copiar, a alocação na pilha pode levar a um enorme impacto no desempenho mais tarde, quando você os usa, se não for cuidadoso.

Por exemplo, se você alocar algo na pilha e depois colocá-lo em um contêiner, seria melhor alocá-lo na pilha e armazenar o ponteiro no contêiner (por exemplo, com um std :: shared_ptr <>). O mesmo acontece se você estiver passando ou retornando objetos por valor e outros cenários semelhantes.

O ponto é que, embora a alocação de pilha seja geralmente melhor do que a alocação de heap em muitos casos, às vezes, se você se esforçar para alocá-la de pilha quando não se encaixa melhor no modelo de computação, isso pode causar mais problemas do que resolve.

wjl
fonte
2
class Foo {
public:
    Foo(int a) {

    }
}
int func() {
    int a1, a2;
    std::cin >> a1;
    std::cin >> a2;

    Foo f1(a1);
    __asm push a1;
    __asm lea ecx, [this];
    __asm call Foo::Foo(int);

    Foo* f2 = new Foo(a2);
    __asm push sizeof(Foo);
    __asm call operator new;//there's a lot instruction here(depends on system)
    __asm push a2;
    __asm call Foo::Foo(int);

    delete f2;
}

Seria assim em asm. Quando você está dentro func, o f1ponteiro e f2foi alocado na pilha (armazenamento automatizado). E, a propósito, Foo f1(a1)não tem efeitos de instrução no ponteiro da pilha ( esp), ele foi alocado, se funcquer obter o membro f1, é instrução é algo como isto: lea ecx [ebp+f1], call Foo::SomeFunc(). Outra coisa que a pilha aloca pode fazer alguém pensar que a memória é algo parecido FIFO, o que FIFOaconteceu quando você entra em alguma função, se você estiver na função e alocar algo como int i = 0, não houve push.

bitnick
fonte
1

Foi mencionado antes que a alocação da pilha está simplesmente movendo o ponteiro da pilha, ou seja, uma única instrução na maioria das arquiteturas. Compare isso com o que geralmente acontece no caso de alocação de heap.

O sistema operacional mantém partes da memória livre como uma lista vinculada com os dados da carga útil que consistem no ponteiro para o endereço inicial da parte livre e o tamanho da parte livre. Para alocar X bytes de memória, a lista de links é percorrida e cada nota é visitada em sequência, verificando se seu tamanho é pelo menos X. Quando uma parte com tamanho P> = X é encontrada, P é dividido em duas partes com tamanhos X e PX. A lista vinculada é atualizada e o ponteiro para a primeira parte é retornado.

Como você pode ver, a alocação de heap depende de fatores como quanta memória você está solicitando, quão fragmentada é a memória e assim por diante.

Nikhil
fonte
1

Em geral, a alocação de pilha é mais rápida que a alocação de heap, conforme mencionado em quase todas as respostas acima. Um push ou pop de pilha é O (1), enquanto alocar ou liberar de um heap pode exigir uma caminhada das alocações anteriores. No entanto, você normalmente não deve alocar loops apertados e com alto desempenho, portanto a escolha geralmente se resume a outros fatores.

Pode ser bom fazer essa distinção: você pode usar um "alocador de pilha" na pilha. A rigor, considero alocação de pilha como o método real de alocação, e não o local da alocação. Se você está alocando muitas coisas na pilha de programas real, isso pode ser ruim por vários motivos. Por outro lado, usar um método de pilha para alocar no heap quando possível é a melhor escolha que você pode fazer para um método de alocação.

Desde que você mencionou Metrowerks e PPC, acho que você quer dizer Wii. Nesse caso, a memória é premium e o uso de um método de alocação de pilha sempre que possível garante que você não desperdiça memória em fragmentos. Obviamente, isso exige muito mais cuidado do que os métodos de alocação de heap "normais". É aconselhável avaliar as compensações para cada situação.

Dan Olson
fonte
1

Observe que as considerações geralmente não são sobre velocidade e desempenho ao escolher a pilha versus a alocação de heap. A pilha age como uma pilha, o que significa que é adequada para empurrar blocos e estourá-los novamente, por último, primeiro a sair. A execução dos procedimentos também é do tipo pilha; o último procedimento inserido é o primeiro a ser encerrado. Na maioria das linguagens de programação, todas as variáveis ​​necessárias em um procedimento só serão visíveis durante a execução do procedimento; portanto, elas são pressionadas ao entrar em um procedimento e salvas da pilha ao sair ou retornar.

Agora, um exemplo em que a pilha não pode ser usada:

Proc P
{
  pointer x;
  Proc S
  {
    pointer y;
    y = allocate_some_data();
    x = y;
  }
}

Se você alocar alguma memória no procedimento S, colocá-la na pilha e sair de S, os dados alocados serão removidos da pilha. Mas a variável x em P também apontou para esses dados, então x agora está apontando para algum lugar abaixo do ponteiro da pilha (suponha que a pilha cresça para baixo) com um conteúdo desconhecido. O conteúdo ainda pode estar lá se o ponteiro da pilha for movido para cima sem limpar os dados abaixo dele, mas se você começar a alocar novos dados na pilha, o ponteiro x poderá realmente apontar para esses novos dados.

Kent Munthe Caspersen
fonte
0

Nunca faça suposições prematuras, pois outros códigos e uso de aplicativos podem afetar sua função. Portanto, olhar para a função é isolar é inútil.

Se você é sério com o aplicativo, faça o VTune ou use qualquer ferramenta de perfil semelhante e observe os pontos ativos.

Ketan

Ketan
fonte
-1

Eu gostaria de dizer que, na verdade, o código gerado pelo GCC (eu também lembro do VS) não tem sobrecarga para fazer a alocação de pilha .

Diga para a seguinte função:

  int f(int i)
  {
      if (i > 0)
      {   
          int array[1000];
      }   
  }

A seguir, o código é gerado:

  __Z1fi:
  Leh_func_begin1:
      pushq   %rbp
  Ltmp0:
      movq    %rsp, %rbp
  Ltmp1:
      subq    $**3880**, %rsp <--- here we have the array allocated, even the if doesn't excited.
  Ltmp2:
      movl    %edi, -4(%rbp)
      movl    -8(%rbp), %eax
      addq    $3880, %rsp
      popq    %rbp
      ret 
  Leh_func_end1:

Portanto, seja qual for a quantidade local de variável que você tenha (mesmo dentro de if ou switch), apenas o 3880 mudará para outro valor. A menos que você não tenha variável local, esta instrução só precisa ser executada. Portanto, alocar variável local não tem sobrecarga.

ZijingWu
fonte