Qual é mais rápido: alocação de pilha ou alocação de heap

Esta questão pode parecer bastante elementar, mas este é um debate que tive com outro desenvolvedor com quem trabalho.

Eu estava tomando cuidado para empilhar alocar coisas onde eu pudesse, em vez de montá-las. Ele estava falando comigo e olhando por cima do meu ombro e comentou que não era necessário, porque eles são o mesmo desempenho sábio.

Eu sempre tive a impressão de que aumentar a pilha era tempo constante, e o desempenho da alocação de heap dependia da complexidade atual do heap para alocação (encontrar um buraco do tamanho adequado) e desalocação (furos para reduzir fragmentação, como muitas implementações de biblioteca 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 . O insight sobre essa combinação seria mais útil, mas, em geral, para o GCC e o MSVC ++, qual é o caso? A alocação de heap não é tão alta quanto a alocação de pilha? Não há diferença? Ou são as diferenças tão pequenas que se tornam micro-otimização sem sentido.

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

Além disso, stack vs. heap não é apenas uma consideração de desempenho; também informa muito sobre o tempo de vida esperado dos objects.

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

sub esp, 0x10 

(Isso move o ponteiro da pilha para baixo por 0x10 bytes e, assim, “aloca” esses bytes para uso por uma variável.)

É claro que o tamanho da pilha é muito, muito finito, já que você descobrirá rapidamente se usa demais a alocação de pilha ou tentará recursion 🙂

Além disso, há poucas razões para otimizar o desempenho do código que não precisa dele, como demonstrado pela criação de perfil. “Otimização prematura” muitas vezes causa mais problemas do que vale a pena.

Minha regra de ouro: se eu sei que vou precisar de alguns dados em tempo de compilation , e é sob algumas centenas de bytes de tamanho, eu pilha-alocá-lo. Caso contrário, eu alocarei o heap.

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

 #include  #include  namespace { class empty { }; // even empty classs 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, otimizar compiladores são os duelos da mente de muitos programadores. Essa discussão costumava estar no fim da resposta, mas as pessoas aparentemente não se incomodam em ler até aqui, então estou mudando para cá 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 lutar contra o otimizador é uma tarefa tola.

Eu recomendaria a compilation desse 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 um que ligar o otimizador e depois reclamar sobre a luta deve estar sujeito ao ridículo público.

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

O otimizador tem a missão de se livrar do código que estou testando. Eu não vejo nenhum motivo para dizer ao otimizador para executar e, em seguida, tentar enganar o otimizador em não realmente otimizando. Mas se eu vi valor em fazer isso, eu faria um ou mais dos seguintes procedimentos:

  1. Adicione um membro de dados para empty e acesse esse membro de dados no loop; mas se eu apenas ler o membro de dados, o otimizador pode fazer o dobramento constante e remover o loop; se eu apenas gravar no membro de dados, o otimizador pode pular tudo, exceto a última iteração do loop. Além disso, a pergunta não era "alocação de pilha e access a dados versus alocação de heap e access a dados".

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

  3. Pegue o endereço de e dentro do loop (e talvez o atribua a uma variável declarada extern e definida em outro arquivo). Mas mesmo neste caso, o compilador pode notar que - na pilha, pelo menos - e sempre será alocado no mesmo endereço de memory, e então fará o dobramento constante como em (1) acima. Eu recebo todas as iterações do loop, mas o object nunca é realmente alocado.

Além do óbvio, esse teste tem falhas, pois mede tanto a alocação quanto a desalocação, e a pergunta original não perguntou sobre a desalocação. Obviamente, as variables ​​alocadas na pilha são desalocadas automaticamente no final de seu escopo, portanto, não chamar delete (1) inclina os números (a desalocação de pilha é incluída nos números sobre alocação de pilha, portanto, é justo medir a desalocação de heap) e (2) causar um memory leaks muito ruim, a menos que mantenhamos uma referência ao novo ponteiro e chamemos delete depois que tivermos a medição do 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 qualquer coisa menor que 100000 alocações e mesmo assim recebo "0 ticks de relógio" para alocação de pilha e "15 pulsos de clock" "para alocação de heap. Quando eu medir 10.000.000 alocações, a alocação de pilha leva 31 pulsos de clock e alocação de pilha leva 1562 pulsos de clock.


Sim, um compilador otimizador pode elidir a criação de objects vazios. Se bem entendi, pode até mesmo elidir todo o primeiro loop. Quando aumentei as iterações para 10.000.000 de alocação de pilha, obtive 31 pulsos de clock e a alocação de heap levou 1.562 pulsos de clock. Eu acho que é seguro dizer que sem dizer ao g ++ para otimizar o executável, g + + não elidiu os construtores.


Nos anos desde que escrevi isso, a preferência no Stack Overflow era publicar o desempenho de compilações otimizadas. Em geral, acho que isso está correto. No entanto, ainda acho que é bobagem pedir ao compilador para otimizar o código quando, na verdade, você não quer que o código seja otimizado. Parece-me muito semelhante a pagar mais pelo estacionamento com manobrista, mas se recusa a entregar as chaves. Nesse caso específico, não quero o otimizador em execução.

Usando uma versão ligeiramente modificada do benchmark (para abordar o ponto válido de que o programa original não alocou algo na pilha a cada vez através do loop) e compilando sem otimizações, mas ligando para liberar bibliotecas (para abordar o ponto válido que nós don Deseja include qualquer lentidão causada pela vinculação a bibliotecas de debugging):

 #include  #include  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(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(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 a minha abordagem para obter uma compilation não otimizada. Tudo bem: sinta-se à vontade para modificar o benchmark o quanto você 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 é realmente instantânea, mas porque qualquer compilador meio decente pode perceber que on_stack não faz nada de útil e pode ser otimizado. O GCC no meu laptop Linux também percebe que o on_heap não faz nada útil e o otimiza também:

 on_stack took 0.000003 seconds on_heap took 0.000002 seconds 

Uma coisa interessante que aprendi sobre Stack vs. Heap Allocation no processador Xenon do Xbox 360, que também pode se aplicar a outros sistemas multicore, é que alocar no heap faz com que uma seção crítica seja inserida para interromper todos os outros núcleos, de modo que a alocação não seja está em conflito. Assim, em um loop apertado, a alocação de pilha era o caminho a percorrer para matrizes de tamanho fixo, pois impedia as barracas.

Esta pode ser uma outra aceleração a ser considerada se você estiver codificando para multicore / multiproc, pois sua alocação de pilha só será visível pelo núcleo executando sua function com escopo definido, e isso não afetará nenhum outro núcleo / CPU.

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

Também concordo com Torbjörn Gyllebring sobre o tempo de vida esperado dos objects. Bom ponto!

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

Eu recomendaria fortemente para itens pequenos, o que for mais adequado ao escopo da alocação. Para itens grandes, o heap provavelmente é necessário.

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

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

Normalmente, a alocação de pilha consiste apenas em subtrair do registrador de ponteiro da pilha. Isso é muito mais rápido do que procurar um monte.

Às vezes, a alocação de pilha requer a adição de uma (s) página (s) de memory virtual. Adicionar uma nova página de memory zerada não requer a leitura de uma página do disco, então normalmente isso ainda será muito mais rápido do que procurar um heap (especialmente se parte do heap foi paginada também). Em uma situação rara, e você poderia construir um exemplo desse tipo, espaço suficiente apenas estará 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 alguma outra página seja gravada para o disco. Nessa situação rara, o heap é mais rápido.

Além da vantagem de desempenho de ordens de magnitude sobre a alocação de heap, a alocação de pilha é preferível para aplicativos de servidor de longa execução. Até mesmo os heaps mais bem gerenciados acabam se tornando tão fragmentados que o desempenho do aplicativo se degrada.

Uma pilha tem uma capacidade limitada, enquanto uma pilha não é. A pilha típica de 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 de heap não. Se o seu ponteiro de instrução vai além de uma function, todas as novas variables ​​associadas à function desaparecem.

O mais importante de tudo é que você não pode prever antecipadamente a cadeia geral de chamadas de function. Portanto, uma mera alocação de 200 bytes de sua parte pode gerar um estouro de pilha. Isso é especialmente importante se você estiver escrevendo uma biblioteca, não um aplicativo.

Eu acho que a vida é crucial, e se a coisa que está sendo alocada tem que ser construída de uma maneira complexa. Por exemplo, na modelagem orientada por transação, você geralmente precisa preencher e passar uma estrutura de transação com vários campos para 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 enorme sobrecarga, já que a construção é cara. O bom caminho é alocar no heap e reutilizar os objects de transação por meio de pooling ou de uma política simples como “este módulo precisa apenas de um object de transação”.

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

A razão é simplesmente que o object tem uma construção cara e uma vida útil bastante longa.

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

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 onde o tempo é um problema.

Para outras aplicações onde o tempo não é um problema, pode não importar tanto, mas se você aloca muito, isso afetará a velocidade de execução. Sempre tente usar a pilha para memory de curta duração e muitas vezes alocada (por exemplo, em loops) e pelo maior tempo possível – alocação de heap durante a boot do aplicativo.

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

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

No entanto, existem problemas maiores ao lidar com o desempenho geral da alocação baseada em pilha versus heap (ou em termos ligeiramente melhores, alocação local versus alocação 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 melhor estrutura a seus padrões de alocação, por exemplo, forçar uma ordenação LIFO em pares de alocação e desalocação também pode melhorar o desempenho do alocador usando o alocador de uma maneira mais simples e mais 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 freqüência, portanto, um heap baseado em um buffer lookaside de alguns tamanhos fixos (preferencialmente conhecidos) terá um desempenho extremamente bom. O Windows usa seu heap de baixa fragmentação por essa mesma razão.

Por outro lado, a alocação baseada em pilha em um intervalo de memory de 32 bits também é repleta de perigos se você tiver muitos encadeamentos. As pilhas precisam de um intervalo de memory contíguo, portanto, quanto mais segmentos 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 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 dor para lidar.

A alocação de pilha é um par de instruções, enquanto o alocador de heap de rtos mais rápido conhecido por mim (TLSF) usa, em média, a ordem de 150 instruções. Também as alocações de pilha não exigem um bloqueio porque usam o armazenamento local de encadeamento, que é outra grande conquista de desempenho. Portanto, as alocações de pilha podem ser de 2 a 3 ordens de magnitude mais rápidas, dependendo de quão fortemente multithread 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 um par de instruções e tem muito pouca sobrecarga por alocação, por isso é ótimo para objects pequenos de tamanho fixo. No lado negativo, ele só funciona com objects de tamanho fixo, não é inerentemente seguro para threads e tem problemas de fragmentação de blocos.

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

A otimização obtida é proporcional à quantidade de tempo que o contador de programas está realmente nesse código.

Se você experimentar o contador de programa, descobrirá onde ele gasta seu tempo, e isso geralmente está em uma pequena parte do código e, com frequência, em rotinas de biblioteca sobre as quais você não tem controle.

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

A alocação de pilha é muito mais rápida.

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

No entanto, se os seus objects são caros para copiar, alocar na pilha pode levar a um enorme impacto no desempenho mais tarde quando você usar os objects se você não for cuidadoso.

Por exemplo, se você alocar algo na pilha e, em seguida, colocá-lo em um contêiner, seria melhor alocar no heap e armazenar o ponteiro no contêiner (por exemplo, com um std :: shared_ptr <>). A mesma coisa é verdadeira se você está passando ou retornando objetos por valor e outros cenários semelhantes.

O ponto é que, embora a alocação de pilha seja geralmente melhor que a alocação de heap em muitos casos, às vezes, se você se esforçar para alocar pilha quando não se encheckbox melhor no modelo de cálculo, ela pode causar mais problemas do que resolve.

 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á em func , o f1 e o ponteiro f2 foram alocados na pilha (armazenamento automatizado). E, a propósito, Foo f1(a1) não tem efeitos de instrução no ponteiro de pilha ( esp ), foi alocado, se func quer obter o membro f1 , é instrução é algo assim: lea ecx [ebp+f1], call Foo::SomeFunc() . Outra coisa que a pilha aloca pode fazer alguém pensar que a memory é algo parecido com FIFO , o FIFO acabou de acontecer quando você entra em alguma function, se você está na function e aloca algo como int i = 0 , não houve nenhum push.

Foi mencionado anteriormente que a alocação de 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 memory livre como uma lista encadeada com os dados de carga útil consistindo no ponteiro para o endereço inicial da parte livre e o tamanho da parte livre. Para alocar X bytes de memory, a lista de links é percorrida e cada nota é visitada em seqüência, verificando se seu tamanho é pelo menos X. Quando uma porção com tamanho P> = X é encontrada, P é dividido em duas partes com tamanhos X e PX. A linked list é atualizada e o ponteiro para a primeira parte é retornado.

Como você pode ver, a alocação de heap depende de fatores como a quantidade de memory solicitada, a fragmentação da memory e assim por diante.

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

Pode ser bom fazer essa distinção: você pode usar um “alocador de pilha” no heap. Estritamente falando, eu tomo alocação de pilha para significar o método real de alocação em vez da localização da alocação. Se você está alocando um monte de coisas na pilha real do programa, isso pode ser ruim por uma série de razões. Por outro lado, usar um método de pilha para alocar na pilha quando possível é a melhor escolha que você pode fazer para um método de alocação.

Desde que você mencionou o Metrowerks e o PPC, estou supondo que você esteja falando do Wii. Neste caso, a memory é um prêmio, e usar um método de alocação de pilha, sempre que possível, garante que você não perca memory em fragments. Naturalmente, isso exige muito mais cuidado do que os methods de alocação de heap “normais”. É aconselhável avaliar as compensações para cada situação.

Observe que as considerações geralmente não são sobre velocidade e desempenho ao escolher a alocação de pilha versus heap. A pilha funciona 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 é semelhante a uma pilha, o último procedimento inserido é o primeiro a ser encerrado. Na maioria das linguagens de programação, todas as variables ​​necessárias em um procedimento só serão visíveis durante a execução do procedimento, portanto, são pressionadas ao inserir um procedimento e saem da pilha ao sair ou retornar.

Agora, para 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 memory no procedimento S e 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 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á apontar para esses novos dados.

Nunca faça suposições prematuras, pois o código e o uso de outros aplicativos podem afetar sua function. Então, olhando para a function é o isolamento é inútil.

Se você é sério com o aplicativo, então VTune ou use qualquer ferramenta de perfil semelhante e veja os hotspots.

Ketan

Eu gostaria de dizer realmente gerar código pelo GCC (eu me lembro VS também) não tem sobrecarga para fazer alocação de pilha .

Diga para a seguinte function:

  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: 

Então, independentemente da quantidade de variables ​​locais que você tem (mesmo dentro de if ou switch), apenas o 3880 mudará para outro valor. A menos que você não tenha uma variável local, esta instrução só precisa ser executada. Portanto, alocar variável local não tem sobrecarga.