Que é mais rápido: alocação de pilha ou alocação de Heap

https://stackoverflow.com/questions/161053

03-07-2019
|

Pergunta

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

Eu estava tendo o cuidado de pilha alocar coisas onde eu poderia, em vez de pilha alocá-los. Ele estava falando comigo e assistindo sobre meu ombro e comentou que não era necessário, porque eles são o mesmo desempenho sábio.

Eu estava sempre com a impressão de que o crescimento da pilha era constante de tempo e desempenho de alocação de pilha depende da complexidade atual da pilha tanto para alocação (encontrar um buraco do tamanho adequado) e de-alocação (colapso buracos para reduzir fragmentação, como muitas implementações de biblioteca padrão ter tempo para fazer isso durante exclusões, se não me engano).

Isso me parece algo que provavelmente seria muito compilador dependente. Para este projeto em particular eu estou usando um Metrowerks compilador para a arquitetura PPC . Uma visão sobre esta combinação seria mais útil, mas, em geral, para o GCC e MSVC ++, o que é o caso? É alocação de pilha não tão alto desempenho como alocação de pilha? Será que não há diferença? Ou são as diferenças tão minutos, torna-se inútil micro-otimização.

Solução

alocação

Stack é muito mais rápido, pois tudo o que realmente faz é mover o ponteiro de pilha. Usando pools de memória, você pode obter um desempenho comparável fora de alocação de pilha, mas que vem com uma ligeira complexidade e suas próprias dores de cabeça.

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

Outras dicas

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

sub esp, 0x10

(que move o ponteiro da pilha para baixo por 0x10 bytes e, assim, "aloca" os bytes para uso por uma variável.)

É claro, o tamanho da pilha é muito, muito finito, como você vai descobrir rapidamente se você overuse alocação de pilha ou tentar fazer recursão: -)

Além disso, há pouca razão para otimizar o desempenho de código que não verificável precisar, tal como demonstrado pela criação de perfil. "Otimização prematura", muitas vezes causa mais problemas do que vale a pena.

A minha regra de ouro: se eu sei que vou precisar de alguns dados em tempo de compilação , e é sob algumas centenas de bytes de tamanho, eu empilhar-alocá-lo. Caso contrário, eu amontoar-alocá-lo.

Honestamente, é trivial para 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";
}

É dito que uma consistência tola é o fantasma das mentes pequenas . Aparentemente compiladores de otimização são os duendes da mente de muitos programadores. Esta discussão costumava ser na parte inferior da resposta, mas as pessoas aparentemente não pode ser incomodado para ler tão longe, então eu estou movendo-se aqui para evitar perguntas que eu já respondi.

Um compilador otimizar pode notar que este código não faz nada, e pode otimizar tudo fora. É o trabalho do otimizador para fazer coisas assim, e lutando contra o otimizador é uma missão de tolos.

Eu recomendaria compilar esse código com otimização desligado porque não há nenhuma boa maneira de enganar cada otimizador atualmente em uso ou que estarão em uso no futuro.

Qualquer pessoa que transforma o otimizador e então reclama de combatê-la deve ser objecto de ridículo público.

Se eu me preocupava com precisão de nanossegundos eu não usar std::clock(). Se eu quisesse publicar os resultados como uma tese de doutoramento I faria um grande negócio sobre isso, e eu provavelmente iria comparar GCC, Tendra / Ten15, LLVM, Watcom, Borland, o Visual C ++, Marte Digital, ICC e outros compiladores. Como é, alocação de pilha leva centenas de vezes mais do que alocação de pilha, e eu não vejo nada de útil sobre a investigar a questão mais.

O otimizador tem a missão de livrar-se do código que estou testando. Não vejo qualquer razão para dizer ao otimizador para executar e, em seguida, tentar enganar o otimizador na verdade não otimizar. Mas se eu valor serra em fazer isso, eu faria um ou mais dos seguintes:

Adicionar um membro de dados para empty e acesso que membro de dados no loop; mas se eu sempre apenas ler a partir do membro de dados o otimizador pode fazer dobrar constante e remover o loop; se eu só escrever para o membro de dados, o otimizador pode pular todos, mas a última iteração do loop. Além disso, a questão não era "alocação alocação de pilha e acesso a dados vs. pilha e acesso a dados."
Declare e volatile, mas volatile muitas vezes é compilado incorretamente (PDF).
Leve o endereço do e dentro do loop (e talvez atribuí-la a uma variável que é declarada extern e definidos em outro arquivo). Mas, mesmo neste caso, o compilador pode notar que - na pilha pelo menos - e sempre serão alocados no mesmo endereço de memória, e depois fazer dobrar constante como em (1) acima. Recebo todas as iterações do loop, mas o objeto nunca é realmente alocada.

Para além do óbvio, este teste é falho na medida em que mede tanto a alocação e desalocação, e a pergunta original não perguntar sobre deallocation. Claro variáveis ??alocados na pilha são automaticamente desalocados no final do seu alcance, para que não chamar delete seria (1) distorcer os números (deallocation pilha está incluído nos números sobre alocação de pilha, por isso é justo para medir deallocation pilha) e (2) causa um vazamento de memória muito ruim, a menos que manter uma referência para o novo ponteiro e chamada delete depois temos a nossa medição de tempo.

Na minha máquina, usando g ++ 3.4.4 no Windows, eu recebo "0 relógio avança" para ambos pilha e alocação de pilha com nada menos de 100000 alocações, e mesmo assim eu recebo "0 relógio marca" para a alocação de pilha e " 15 relógio carrapatos" para alocação de pilha. Quando eu medir 10.000.000 atribuições, alocação de pilha leva 31 carrapatos de relógio e montão allocation leva 1562 ticks de relógio.

Sim, um compilador de otimização pode elidir criar os objetos vazios. Se eu entendi corretamente, pode até omitir todo o primeiro loop. Quando eu colidido até as iterações para alocação de pilha 10.000.000 levou 31 carrapatos de relógio e alocação de pilha teve 1562 ticks de relógio. Eu acho que é seguro dizer que sem dizer g ++ para otimizar o executável, g ++ não elide os construtores.

Nos anos desde que eu escrevi isso, a preferência no estouro de pilha tem sido a de desempenho pós partir otimizado constrói. Em geral, eu acho que isso é correto. No entanto, eu ainda acho que é bobagem para pedir o compilador para o código otimizar quando na verdade não quer que o código otimizado. Parece-me como sendo muito semelhante a pagar extra para estacionamento com manobrista, mas recusando-se a entregar as chaves. Neste caso particular, eu não quero que o otimizador de execução.

Usando uma versão ligeiramente modificada do índice de referência (para o endereço do ponto válido que o programa original não alocar algo na pilha cada vez através do loop) e compilar sem otimizações mas ligando para liberar bibliotecas (para abordar o ponto válido que não deseja incluir qualquer desaceleração causada por ligando 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 o cl foo.cc /Od /MT /EHsc linha de comando.

Você pode não concordar com a minha abordagem para obter uma compilação não otimizado. Isso é bom: sensação modificar livre o ponto de referência, tanto quanto você quer. Quando ligo otimização, eu recebo:

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

Não porque alocação de pilha é realmente instantânea, mas porque qualquer compilador semi-decente pode notar que on_stack não faz nada útil e pode ser otimizada de distância. GCC no meu laptop Linux também percebe que on_heap não faz nada útil, e otimiza-lo assim:

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

Uma coisa interessante que eu aprendi sobre Stack vs. Heap Allocation no processador Xenon Xbox 360, que também pode ser aplicado a outros sistemas multicore, é que alocar na pilha faz com que uma seção crítica a ser introduzido para deter todos os outros núcleos para que a alocação não está em conflito. Assim, dentro de um loop, Pilha Allocation era o caminho a percorrer para matrizes de tamanho fixo, uma vez que impediu bancas.

Esta pode ser outra aceleração para considerar se você está programando para multicore / multiproc, em que a sua alocação de pilha só será visível pelo core rodando a sua função de escopo, e que não afetará quaisquer outros núcleos / CPUs.

Você pode escrever um alocador de pilha especial para tamanhos específicos de objetos que é muito alto desempenho. No entanto, a Geral alocador de pilha não é particularmente alto desempenho.

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

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

Eu recomendo fortemente para pequenos itens, o que for mais adequado ao âmbito da atribuição. Para grandes itens, a pilha é provavelmente necessário.

Em sistemas operacionais de 32 bits que têm vários tópicos, pilha muitas vezes é bastante limitado (embora normalmente a pelo menos alguns mb), porque as necessidades de espaço de endereços para ser retalhado e mais cedo ou mais tarde, um segmento de pilha vai correr em outra . Em sistemas single threaded (Linux glibc única de qualquer forma de rosca) a limitação é muito menos porque a pilha pode apenas crescer e crescer.

Em sistemas operacionais de 64 bits, há espaço de endereço suficiente para fazer pilhas de thread bastante grande.

alocação Normalmente pilha consiste apenas de subtrair do registo ponteiro de pilha. Esta é toneladas mais rápido do que procurar um montão.

alocação Às vezes pilha requer a adição de uma página (s) de memória virtual. Adicionando uma nova página de memória zerada não requer leitura de uma página do disco, de modo geral isso ainda vai ser toneladas mais rápido do que procurar uma pilha (especialmente se parte da pilha foi paginada também). Em uma situação rara, e você poderia construir um exemplo, espaço suficiente só acontece para estar disponível em parte da pilha que já está na RAM, mas a atribuição de uma nova página para a pilha tem de esperar por alguma outra página para se escrito para o disco. Nessa situação rara, a pilha é mais rápido.

Além da vantagem de desempenho ordens de grandeza mais de alocação de pilha, alocação de pilha é preferível por muito tempo a execução de aplicativos de servidor. Mesmo os montes melhor gerenciados eventualmente se tão fragmentado que degrada o desempenho do aplicativo.

A 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, uma vez que está alocado.

Uma pilha variável segue as regras de escopo, enquanto um amontoado não. Se o seu ponteiro de instrução vai além de uma função, todas as novas variáveis ??associadas com a função de ir embora.

O mais importante de tudo, você não pode prever a cadeia de chamada função global com antecedência. Assim, uma simples repartição 200 bytes de sua parte pode levantar um estouro de pilha. Isto é especialmente importante se você estiver escrevendo uma biblioteca, e não um aplicativo.

Eu acho que a vida é crucial, e se a coisa que está sendo alocada tem que ser construído de uma forma complexa. Por exemplo, na modelagem orientada por transação, você geralmente tem que preencher e passar em uma estrutura de transação com um monte de campos para funções de operação. Olhe para o padrão OSCI SystemC TLM-2.0 para um exemplo.

atribuição dessas na pilha perto da chamada para a operação tende a causar enorme sobrecarga, como a construção é caro. A boa forma há para alocar na pilha e reutilizar a transação objetos quer por pooling ou uma política simples como "este módulo só precisa de um objeto de transação sempre".

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

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

Eu diria: tentar ambos e ver o que funciona melhor no seu caso, porque ele realmente pode depender do comportamento do seu código.

Provavelmente o maior problema de alocação de pilha contra alocação de pilha, é que alocação de pilha no caso geral é uma operação sem limites, e assim você não pode usá-lo onde o tempo é um problema.

Para outras aplicações onde o tempo não é um problema, ele pode não importa tanto, mas se você MONTÃO alocar muito, isso vai afetar a velocidade de execução. Sempre tente usar a pilha para a memória vivida e muitas vezes alocados curto (por exemplo, em loops), e o maior tempo possível -. Fazer alocação de pilha durante a inicialização do aplicativo

Não é apenas pilha de alocação que é mais rápido. Você também ganhar um monte sobre o uso de variáveis ??de pilha. Eles têm melhor localidade de referência. E, finalmente, deallocation é muito mais barato também.

alocação de pilha será quase sempre mais rápido ou mais rápido do que alocação de pilha, embora seja certamente possível para um alocador de pilha simplesmente usar uma técnica de alocação de pilha base.

No entanto, existem questões maiores quando se lida com o desempenho global da pilha vs. alocação baseado em pilha (ou ligeiramente melhores condições, vs. locais alocação externa). Normalmente, montão alocação (externo) é lento porque está lidando com muitos tipos diferentes de atribuições e padrões de alocação. Reduzir o âmbito do alocador de que você está usando (tornando-o local para o algoritmo / código) tenderá a aumentar o desempenho sem grandes mudanças. Adicionando uma melhor estrutura para os seus padrões de alocação, por exemplo, forçando uma ordem LIFO em pares de alocação e desalocação também pode melhorar o desempenho do seu alocador usando o alocador de uma forma mais simples e mais estruturada. Ou, você pode usar ou escrever um alocador atento para o seu padrão de alocação particular; a maioria dos programas de alocar alguns tamanhos discretos com frequência, de modo que uma pilha é baseada em um tampão Lookaside de alguns tamanhos fixos (preferivelmente conhecido) irá executar extremamente bem. O Windows usa a sua baixa fragmentação-heap por isso mesmo.

Por outro lado, a alocação baseada em pilha em um intervalo de memória de 32 bits também é cheio de perigo, se você tem muitos tópicos. Pilhas precisa de um intervalo de memória contígua, de modo que os segmentos mais você tem, mais espaço de endereço virtual que você terá para eles a correr sem um estouro de pilha. Este não será um problema (por enquanto) com 64 bits, mas certamente pode causar estragos no longo executar programas com muitas threads. Funcionando fora do espaço de endereço virtual devido à fragmentação é sempre uma dor de lidar com eles.

alocação de pilha é um par de instruções enquanto os rtos mais rápidos heap alocador conhecido para mim (TLSF) usos, em média, da ordem de 150 instruções. Também alocações de pilha não requerem um bloqueio porque eles usam armazenamento local de segmento que é uma vitória enorme desempenho. Então alocações de pilha pode ser 2-3 ordens de magnitude mais rápido, dependendo do quão forte multithreaded seu ambiente é.

Na alocação geral pilha é o último recurso, se você se preocupa com o desempenho. A viável no meio opção pode ser um alocador piscina fixo que é também instruções apenas um par e tem sobrecarga muito pouco per-alocação por isso é ótimo para pequenos objetos de tamanho fixo. No lado negativo só funciona com objetos de tamanho fixo, não é inerentemente segmento seguro e tem problemas bloco de fragmentação.

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

A optimização que você recebe é proporcional à quantidade de tempo que o contador de programa é realmente nesse código.

Se você provar o contador de programa, você vai descobrir onde ele gasta o seu tempo, e que é geralmente em uma pequena parte do código, e muitas vezes em rotinas da biblioteca que você não tem controle sobre.

Só se você achar que gastar muito tempo na pilha de alocação de seus objetos vai ser visivelmente mais rápido para empilhar-alocá-los.

Como já foi dito, a alocação de pilha é geralmente muito mais rápido.

No entanto, se os objetos são caros para copiar, alocando na pilha pode levar a um grande desempenho atingido mais tarde, quando você usa os objetos se você não for cuidadoso.

Por exemplo, se você alocar algo na pilha, e depois colocá-lo em um recipiente, que teria sido melhor para alocar na pilha e armazenar o ponteiro no recipiente (por exemplo, com um std :: shared_ptr <>) . A mesma coisa é verdade se você estiver passando ou retornando objetos de valor, e outros cenários semelhantes.

O ponto é que, apesar de alocação de pilha é geralmente melhor do que alocação de pilha, em muitos casos, por vezes, se você sair do seu caminho para empilhar alocar quando não se ajuste melhor ao modelo de computação, 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 ponteiro f2 foi 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 desejos func obter o f1 membro, é instrução é algo como isto: lea ecx [ebp+f1], call Foo::SomeFunc(). Outra coisa a pilha de alocar pode fazer alguém pensar que a memória é algo como FIFO, o FIFO só aconteceu quando você entrar em alguma função, se você estiver na função e alocar algo como int i = 0, não há impulso aconteceu.

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

O sistema operacional mantém porções de memória livre como uma lista ligada com os dados de carga que consistem do ponteiro para o endereço inicial da porção livre e o tamanho da porção livre. Para alocar X bytes de memória, a lista de links é atravessada e cada nota é visitado em seqüência, verificação para ver se o seu tamanho é de pelo menos X. Quando uma parte com tamanho P> = X é encontrado, P é dividida em duas partes com tamanhos X e PX. A lista ligada é atualizado e o ponteiro para a primeira parte é devolvida.

Como você pode ver, alocação de pilha depende de fatores podem como a quantidade de memória que você está pedindo, como fragmentado a memória é e assim por diante.

Em geral, a alocação de pilha é mais rápido do que alocação de pilha como mencionado por quase todos os resposta acima. Um impulso pilha ou pop é O (1), enquanto que a atribuição ou de libertar a partir de uma pilha poderia exigir um pé de atribuições anteriores. No entanto, você geralmente não deve ser atribuído, apertado, loops de uso intensivo de desempenho, por isso a escolha geralmente virá para baixo a outros fatores.

Pode ser bom para fazer esta distinção: você pode usar um "alocador de pilha" na pilha. 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 actual programa, que pode ser ruim para uma variedade de razões. Por outro lado, usando um método de pilha para alocar no heap quando possível é a melhor escolha que você pode fazer para um método de atribuição.

Uma vez que você mencionou Metrowerks e PPC, eu estou supondo que você quer dizer Wii. Neste memória caso é um prêmio, e usando um método de alocação de pilha sempre que possível garante que você não perca de memória em fragmentos. É claro que, fazendo isso requer muito mais cuidado do que métodos de alocação "normais" heap. É sábio para avaliar as vantagens e desvantagens para cada situação.

Nota que as considerações não são tipicamente cerca de velocidade e desempenho ao escolher pilha contra alocação de pilha. A pilha funciona como uma pilha, o que significa que é bem adequado para empurrar blocos e popping-los novamente, última in, first out. Execução de procedimentos também é pilha-like, último procedimento introduzido é primeiro a ser encerrado. Na maioria das linguagens de programação, todas as variáveis ??necessárias em um procedimento só será visível durante a execução do procedimento, assim, eles são empurrados ao entrar um procedimento e retirado da pilha em cima da saída ou retorno.

Agora, para um exemplo onde a pilha não pode ser utilizada:

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

Se você alocar alguma memória no processo S e colocá-lo na pilha e, em seguida, sair S, os dados alocados será retirado da pilha. Mas a variável x em P também apontou que os dados, de modo que x é agora apontando para algum lugar debaixo do ponteiro de pilha (assumir pilha cresce para baixo) com um conteúdo desconhecido. O conteúdo pode ainda estar lá, se o ponteiro da pilha é apenas mudou-se sem limpar os dados abaixo dela, mas se você começar a alocação de novos dados na pilha, o ponteiro x pode realmente apontam para que os novos dados em vez disso.

preocupações específicas à ++ Linguagem C

Em primeiro lugar, não há nenhuma chamada "pilha" ou alocação "amontoado" mandatado pelo C ++ . Se você está falando sobre objetos automáticos no âmbito do bloco, eles são ainda não "atribuída". (BTW, duração de armazenamento automático em C não é definitivamente o mesmo para "atribuída", este último é "dinâmico" no C linguagem ++). E a memória alocada dinamicamente está no loja livre , não necessariamente em "pilha", embora este último é muitas vezes o (padrão) aplicação .

Embora de acordo com as regras semânticas abstratas, objetos automáticos ainda ocupam memória, a implementação de um conformando C ++ é permitido ignorar esse fato quando se pode provar isso não importa (quando não alterar o comportamento observável do programa). Esta permissão é concedida pela as-se a regra em ISO C ++, que é também a cláusula geral permitindo que as otimizações habituais (e há também uma quase mesma regra em ISO C). Além do as-se a regra, ISO C ++ também tem regras elisão cópia para permitir a omissão de criações específicas de objetos. As chamadas de construtor e destruidor envolvidos são assim omitidas. Como resultado, os objetos automáticas (se houver) nestes construtores e destruidores são também eliminadas, em comparação com a semântica abstratas ingênuos implícitos pelo código-fonte.

Por outro lado, a alocação de armazenamento livre é definitivamente "alocação" por design. Segundo as regras da ISO C ++, essa atribuição pode ser alcançado por uma chamada de um função de alocação . No entanto, desde ISO C ++ 14, há uma nova regra (não-como-se) para permitir a fusão função de alocação global de chamadas (ou seja ::operator new) em casos específicos. Assim, partes de operações de alocação dinâmica também pode ser não-op como o caso de objetos automáticas.

funções de alocação alocar recursos de memória. Os objetos podem ainda ser alocados com base na alocadores de alocação usando. Para objetos automáticas, são directamente apresentado - embora a memória subjacente pode ser acessado e ser usado para fornecer memória para outros objetos (por new colocação), mas isso não faz grande sentido, como a loja livre, porque não há nenhuma maneira de mover os recursos em outros lugares.

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

Sobre Implementações de C ++

C ++ não expor registros de ativação reificadas ou alguns tipos de continuações de primeira classe (por exemplo, o famoso call/cc), não há nenhuma maneira de manipular diretamente os recordes quadros de ativação - onde a necessidade de implementação para colocar os objetos automáticos para. Uma vez que não há interoperações (não-portáteis) com a implementação subjacente (código não-portáteis "nativo", como o código de montagem em linha), uma omissão da atribuição subjacente dos quadros podem ser bastante trivial. Por exemplo, quando a função chamada é inline, os quadros podem ser efetivamente incorporada outros, então não há nenhuma maneira de mostrar o que é a "alocação".

No entanto, uma vez interops são respeitados, as coisas estão ficando complexo. Uma implementação típica do C ++ irá expor a capacidade de interoperabilidade no ISA (instrução-set arquitetura) com alguns chamando convenções como o limite binário compartilhado com o código nativo (máquina de nível ISA). Isso seria explicitamente caro, nomeadamente, ao manter o stack pointer , que é muitas vezes directamente detido por um registo de nível ISA (com instruções de máquina provavelmente específicas para acesso). O ponteiro de pilha indica o limite do quadro superior da chamada de função (actualmente activo). Quando uma chamada de função é inserido, um novo quadro é necessário, e o ponteiro de pilha é adicionado ou subtraído (dependendo da convenção de ISA) por um valor não inferior ao tamanho do quadro requerido. O quadro é, em seguida, disse alocada quando o ponteiro da pilha após as operações. Parâmetros de funções pode ser passado sobre a armação da pilha comobem, dependendo da convenção de chamada usado para a chamada. O quadro pode manter a memória de objetos automática (provavelmente incluindo os parâmetros) especificados pelo código fonte do C ++. No sentido de tais implementações, esses objetos são "atribuída". Quando o controlo sai da chamada de função, a moldura já não é necessário, que normalmente é libertado através do restabelecimento do ponteiro de pilha volta para o estado antes da chamada (salvo anteriormente de acordo com a convenção de chamada). Isto pode ser visto como "deallocation". Estas operações faz com que o registro de ativação de forma eficaz uma estrutura de dados LIFO, por isso é muitas vezes chamado de " o (call) pilha ". O ponteiro de pilha eficazmente indica a posição do topo da pilha.

Porque implementações mais C ++ (em particular as dirigidas código nativo de nível ISA e usando a linguagem assembly como sua saída imediata) usa estratégias semelhantes como este, como confundindo esquema de "alocação" é popular. Tais alocações (bem como deallocations) fazer ciclos de máquina gastar, e ele pode ser caro quando o (não-otimizadas) chamadas ocorrem com freqüência, embora modernos micro arquitetura de CPU pode ter otimizações complexas implementadas por hardware para o padrão de código comum (como o uso de um motor de pilha na implementação de instruções PUSH / POP).

Mas de qualquer maneira, em geral, é verdade que o custo de alocação de quadro de pilha é significativamente menor do que uma chamada para uma função de alocação de operar a loja livre (a menos que seja totalmente otimizado de distância) , que em si pode ter centenas de (se não milhões de :-) operações para manter o ponteiro da pilha e de outros estados. funções de atribuição são tipicamente baseados em API fornecida pela ambiente hospedado (por exemplo tempo de execução fornecida pelo SO). Diferente para o propósito de segurar objetos automáticas para as funções de chamadas, essas atribuições são gerais-determinei, assim eles não terão estrutura de quadros como uma pilha. Tradicionalmente, eles alocar espaço do conjunto de armazenamento chamado pilha (ou várias pilhas). Diferente da "pilha", o conceito de "pilha" aqui não indicam a estrutura de dados a ser utilizado; ele é derivado de início implementações de linguagem décadas atrás . (BTW, a pilha de chamadas normalmente é alocado com tamanho fixo ou especificado pelo usuário da pilha pelo ambiente no programa ou linha de inicialização.) A natureza dos casos de uso faz alocações e deallocations de uma pilha muito mais complicado (de impulso ou pop de empilhar quadros), e quase impossível de ser diretamente otimizada por hardware.

Efeitos sobre a memória de acesso

A alocação de pilha habitual sempre colocar o novo quadro na parte superior, por isso tem um muito bom localidade. Esta é amigável para cache. OTOH, memória alocada aleatoriamente na loja livre não tem essa propriedade. Desde ISO C ++ 17, existem modelos de pool de recursos fornecidos pelo <memory>. O objetivo direto de tal interface é para permitir que os resultados das alocações consecutivas, sendo juntos na memória. Esta reconhece o fato de que esta estratégia é geralmente bom para o desempenho com implementações contemporâneas, por exemplo, sendo amigável para o cache em arquiteturas modernas. Isto é sobre o desempenho de acesso em vez de alocação , no entanto.

Concorrência

Expectativa de acesso simultâneo de memória pode ter efeitos diferentes entre a pilha e pilhas. A pilha de chamadas é geralmente exclusivamente propriedade de uma thread de execução em uma implementação C ++. OTOH, montes são muitas vezes compartilhada entre os threads em um processo. Para esses montes, as funções de alocação e desalocação tem que proteger a dat administrativa interna compartilhadauma estrutura de corrida de dados. Como resultado, as alocações de pilha e desalocações pode ter uma sobrecarga adicional devido a operações de sincronização internos.

Eficiência Espaço

Devido à natureza dos casos de uso e estruturas de dados internos, escombreiras podem sofre de interna memória fragmentação , enquanto a pilha não. Isso não tem impacto direto sobre o desempenho de alocação de memória, mas em um sistema com virtual memória, baixa eficiência de espaço pode degenerar desempenho global de acesso à memória. Isto é particularmente horrível quando HDD é usado como swap de memória física. Ela pode causar bastante longa latência -. Às vezes bilhões de ciclos

Limitações da pilha alocações

Apesar de alocações de pilha são muitas vezes superior em desempenho de alocações de heap na realidade, ele certamente não alocações médios pilha sempre pode substituir alocações de heap.

Em primeiro lugar, não há nenhuma maneira de alocar espaço na pilha com um tamanho especificado em tempo de execução de uma forma portátil com ISO C ++. Existem extensões fornecidas por implementações como alloca e VLA 's L ++ (matriz de comprimento variável), mas existem razões para utilização evitá-los. (IIRC, fonte remove Linux usam de VLA recentemente.) (Observe também ISO C99 tem VLA, mas ISO C11 transforma o suporte opcional.)

Em segundo lugar, não há nenhuma maneira confiável e portátil para detectar pilha espaço exaustão. Isso é muitas vezes chamado de estouro de pilha (hmm, etimologia deste site), mas provavelmente mais accruately, "empilhar superação". Na realidade, isso muitas vezes faz com que o acesso inválido de memória e o estado do programa é então corruptied (... ou talvez pior, uma falha de segurança). Na verdade, ISO C ++ não tem o conceito de pilha e torna indefinido comportamento quando o recurso está esgotado . Seja cauteloso sobre quanto espaço deve ser deixado para objetos automáticos.

Se o espaço de pilha esgotar-se, há muitos objeto alocado na pilha, que pode ser causada por muitas chamadas ativas de funções ou uso indevido de objetos automáticas. Tais casos podem sugerir a existência de erros, por exemplo uma chamada recursiva função sem condições de saída corretos.

No entanto, chamadas recursivas profundas são muitas vezes desejado. Em implementações de linguagens que requerem suporte de chamadas ativas não ligados (profundidade chamada limitado apenas pela memória total), é impossível usar pilha de chamadas nativa diretamente como o registro de ativação língua-alvo como implementações típicas de C ++. Por exemplo, SML / NJ aloca explicitamente quadros na pilha e usos cactus pilhas . A alocação complicado de tais quadros do registro de ativação geralmente não é rápido como os quadros de pilha de chamadas. No entanto, ao implementar ainda mais línguas com adequada cauda recursão, alocação de pilha direto na linguagem objeto (que é , a "objecto" na linguagem não armazenados como referências, mas os valores primitivos, que pode ser um-para-um mapeado para objectos não partilhados C ++) é complicada ainda mais com mais perda de desempenho em geral. Ao usar C ++ para implementar tais línguas, é difícil estimar os impactos de desempenho.

Nunca faça suposição prematura como outro código de aplicação e uso pode ter impacto na sua função. Então, olhando para a função é o isolamento é de nenhum uso.

Se você é sério com aplicação, em seguida, VTune-lo ou usar qualquer ferramenta de perfil semelhante e olhar para hotspots.

Ketan

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

Say por função a seguir:

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

Segue-se o código de gerar:

  __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:

Assim whatevery quanto variável local que você tem (mesmo dentro se ou switch), apenas o 3880 vai mudar para outro valor. A menos que você não tem variável local, esta instrução só precisa executar. Então alocar variável local não tem sobrecarga.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow