Entendo o que é um ponteiro de pilha - mas para que é usado?

O ponteiro da pilha aponta para o topo da pilha, que armazena dados no que chamamos de "LIFO". Para roubar a analogia de outra pessoa, é como uma pilha de pratos em que você coloca e coloca pratos no topo. O ponteiro da pilha, OTOH, aponta para o "prato" superior da pilha. Pelo menos, isso é verdade para x86.

Mas por que o computador / programa "se importa" com o que o ponteiro da pilha está apontando? Em outras palavras, qual o objetivo de ter o ponteiro da pilha e saber para onde ele serve?

Uma explicação compreensível pelos programadores em C seria apreciada.

Que finalidade essa pilha realmente serve, em vez de explicar sua estrutura?

Você tem muitas respostas que descrevem com precisão a estrutura dos dados armazenados na pilha, e noto que é o oposto da pergunta que você fez.

O objetivo que a pilha serve é: a pilha faz parte da reificação da continuação em um idioma sem corotinas .

Vamos desempacotar isso.

Continuação é simplesmente colocada, a resposta para a pergunta "o que vai acontecer a seguir no meu programa?" Em todo momento de qualquer programa, algo acontecerá a seguir. Dois operandos serão computados, o programa continuará computando sua soma e, em seguida, o programa continuará atribuindo a soma a uma variável, e então ... e assim por diante.

Reificação é apenas uma palavra de alta qualidade para fazer uma implementação concreta de um conceito abstrato. "O que acontece depois?" é um conceito abstrato; a maneira como a pilha é organizada é parte de como esse conceito abstrato se transforma em uma máquina real que realmente calcula as coisas.

As corotinas são funções que lembram onde estavam, cedem o controle a outra corotina por um tempo e, em seguida, retomam de onde pararam mais tarde, mas não necessariamente imediatamente após a chamada córtina. Pense em "retornar retorno" ou "aguardar" em C #, que deve lembrar onde eles estavam quando o próximo item é solicitado ou a operação assíncrona é concluída. Idiomas com corotinas ou recursos de idiomas semelhantes requerem estruturas de dados mais avançadas que uma pilha para implementar a continuação.

Como uma pilha implementa a continuação? Outras respostas dizem como. A pilha armazena (1) valores de variáveis ​​e temporários cujas vidas úteis são conhecidas por não serem maiores que a ativação do método atual e (2) o endereço do código de continuação associado à ativação mais recente do método. Em idiomas com exceção de manipulação, a pilha também pode armazenar informações sobre a "continuação de erro" - ou seja, o que o programa fará a seguir quando ocorrer uma situação excepcional.

Deixe-me aproveitar esta oportunidade para observar que a pilha não diz "de onde eu vim?" - embora seja frequentemente usado na depuração. A pilha indica para onde você está indo em seguida e quais serão os valores das variáveis ​​de ativação quando você chegar lá . O fato de que em um idioma sem corotinas, o próximo passo é quase sempre de onde você veio facilita esse tipo de depuração. Mas não é necessário que um compilador armazene informações sobre de onde veio o controle, se puder escapar sem fazê-lo. Otimizações de chamada de cauda, ​​por exemplo, destroem informações sobre a origem do controle do programa.

Por que usamos a pilha para implementar a continuação em idiomas sem corotinas? Como a característica da ativação síncrona de métodos é que o padrão de "suspenda o método atual, ative outro método, retome o método atual sabendo o resultado do método ativado", quando composto consigo mesmo, logicamente forma uma pilha de ativações. Criar uma estrutura de dados que implemente esse comportamento de pilha é muito barato e fácil. Por que é tão barato e fácil? Porque os conjuntos de chips foram projetados por muitas décadas especificamente para facilitar esse tipo de programação para os criadores de compiladores.

O uso mais básico da pilha é armazenar o endereço de retorno para funções:

void a(){
    sub();
}
void b(){
    sub();
}
void sub() {
    //should i got back to a() or to b()?
}

e do ponto de vista de C isso é tudo. Do ponto de vista do compilador:

• todos os argumentos de função são passados ​​pelos registros da CPU - se não houver registros suficientes, os argumentos serão colocados na pilha
• depois que a função termina (a maioria), os registros devem ter os mesmos valores de antes de inseri-los - portanto, os registros usados ​​são copiados na pilha

E do ponto de vista do sistema operacional: o programa pode ser interrompido a qualquer momento. Depois de concluirmos a tarefa do sistema, precisamos restaurar o estado da CPU, então vamos armazenar tudo na pilha

Tudo isso funciona, pois não nos importamos com a quantidade de itens que já estão na pilha ou quantos itens alguém adicionará no futuro, só precisamos saber quanto movemos o ponteiro da pilha e restaurá-lo depois que terminarmos.

LIFO vs FIFO

LIFO significa Last In, First Out. Assim, o último item colocado na pilha é o primeiro item retirado da pilha.

O que você descreveu com a analogia de sua louça (na primeira revisão ) é uma fila ou FIFO, primeiro a entrar, primeiro a sair.

A principal diferença entre os dois é que o LIFO / pilha empurra (insere) e aparece (remove) do mesmo lado, e uma fila FIFO / faz isso de extremos opostos.

// Both:

Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]

// Stack            // Queue
Pop()               Pop()
-> [a, b]           -> [b, c]

O ponteiro da pilha

Vamos dar uma olhada no que está acontecendo sob o capô da pilha. Aqui está um pouco de memória, cada caixa é um endereço:

...[ ][ ][ ][ ]...                       char* sp;
    ^- Stack Pointer (SP)

E há um ponteiro de pilha apontando para a parte inferior da pilha atualmente vazia (se a pilha cresce ou diminui não é particularmente relevante aqui, então ignoraremos isso, mas é claro que no mundo real, isso determina qual operação adiciona e que subtrai do SP).

Então, vamos empurrar a, b, and cnovamente. Gráficos à esquerda, operação de "alto nível" no meio, pseudo-código C-ish à direita:

...[a][ ][ ][ ]...        Push('a')      *sp = 'a';
    ^- SP
...[a][ ][ ][ ]...                       ++sp;
       ^- SP

...[a][b][ ][ ]...        Push('b')      *sp = 'b';
       ^- SP
...[a][b][ ][ ]...                       ++sp;
          ^- SP

...[a][b][c][ ]...        Push('c')      *sp = 'c';
          ^- SP
...[a][b][c][ ]...                       ++sp;
             ^- SP

Como você pode ver, cada vez que pushinserimos o argumento no local que o ponteiro da pilha está apontando no momento e ajusta o ponteiro da pilha para apontar para o próximo local.

Agora vamos aparecer:

...[a][b][c][ ]...        Pop()          --sp;
          ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'c'
          ^- SP
...[a][b][c][ ]...        Pop()          --sp;
       ^- SP
...[a][b][c][ ]...                       return *sp; // returns 'b'
       ^- SP

Popé o oposto de push, ajusta o ponteiro da pilha para apontar para o local anterior e remove o item que estava lá (geralmente para devolvê-lo a quem chamou pop).

Você provavelmente percebeu isso be cainda está na memória. Eu só quero garantir que esses não são erros de digitação. Voltaremos a isso em breve.

Vida sem ponteiro de pilha

Vamos ver o que acontece se não tivermos um ponteiro de pilha. Começando com o envio novamente:

...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]...        Push(a)        ? = 'a';

Hum, hum ... se não tivermos um ponteiro de pilha, não podemos mover algo para o endereço que ele aponta. Talvez possamos usar um ponteiro que aponte para a base e não para o topo.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[a][ ][ ][ ]...        Push(a)        *bp = 'a';
    ^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]...        Push(b)        *bp = 'b';
    ^- bp

Uh oh Como não podemos alterar o valor fixo da base da pilha, apenas o substituímos apressionando bpara o mesmo local.

Bem, por que não acompanhamos quantas vezes pressionamos. E também precisamos acompanhar os horários em que aparecemos.

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);
                                         int count = 0;

...[a][ ][ ][ ]...        Push(a)        bp[count] = 'a';
    ^- bp
...[a][ ][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Push(a)        bp[count] = 'b';
    ^- bp
...[a][b][ ][ ]...                       ++count;
    ^- bp
...[a][b][ ][ ]...        Pop()          --count;
    ^- bp
...[a][b][ ][ ]...                       return bp[count]; //returns b
    ^- bp

Bem, funciona, mas na verdade é bastante semelhante a antes, exceto que *pointeré mais barato do que pointer[offset](sem aritmética extra), sem mencionar que é menos digitado. Isso parece uma perda para mim.

Vamos tentar de novo. Em vez de usar o estilo de string Pascal para encontrar o final de uma coleção baseada em array (rastreando quantos itens há na coleção), vamos tentar o estilo de string C (varredura do começo ao fim):

...[ ][ ][ ][ ]...                       char* bp; // "base pointer"
    ^- bp                                bp = malloc(...);

...[ ][ ][ ][ ]...        Push(a)        char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       *top = 'a';
    ^- bp    ^- top

...[ ][ ][ ][ ]...        Pop()          char* top = bp;
    ^- bp, top
                                         while(*top != 0) { ++top; }
...[ ][ ][ ][a]...                       --top;
    ^- bp       ^- top                   return *top; // returns '('

Você já deve ter adivinhado o problema aqui. Não é garantido que a memória não inicializada seja 0. Portanto, quando procuramos o topo para colocar a, acabamos pulando um monte de locais de memória não utilizados que contêm lixo aleatório. Da mesma forma, quando digitalizamos para o topo, acabamos pulando muito além do aque acabamos de empurrar até finalmente encontrarmos outro local de memória 0, e voltar e devolver o lixo aleatório antes disso.

Isso é fácil de corrigir, basta adicionar operações Pushe Popgarantir que o topo da pilha seja sempre atualizado para ser marcado com a 0, e precisamos inicializar a pilha com esse terminador. Claro que isso também significa que não podemos ter um 0(ou qualquer valor que escolhemos como terminador) como um valor realmente na pilha.

Além disso, também alteramos o que eram operações O (1) para operações O (n).

TL; DR

O ponteiro da pilha controla o topo da pilha, onde ocorre toda a ação. Existem maneiras de se livrar dele ( bp[count]e topainda são essencialmente o ponteiro da pilha), mas ambas acabam sendo mais complicadas e lentas do que simplesmente ter o ponteiro da pilha. E não saber onde está o topo da pilha significa que você não pode usá-la.

Nota: O ponteiro da pilha que aponta para a "parte inferior" da pilha de tempo de execução no x86 pode ser um equívoco relacionado a toda a pilha de tempo de execução de cabeça para baixo. Em outras palavras, a base da pilha é colocada em um endereço de memória alto e a ponta da pilha cresce em endereços de memória inferiores. O ponteiro da pilha faz ponto para a ponta da pilha onde toda a ação ocorre, assim que a ponta está em um endereço de memória menor do que a base da pilha.

O ponteiro da pilha é usado (com o ponteiro do quadro) para a pilha de chamadas (siga o link para a wikipedia, onde há uma boa imagem).

A pilha de chamadas contém quadros de chamadas, que contêm endereço de retorno, variáveis ​​locais e outros dados locais (em particular, conteúdo derramado de registros; documentos formais).

Leia também sobre chamadas de cauda (algumas chamadas de cauda recursivas não precisam de nenhum quadro de chamada), tratamento de exceções (como setjmp e longjmp , elas podem envolver o surgimento de muitos quadros de pilha ao mesmo tempo), sinais e interrupções e continuações . Consulte também convenções de chamada e interfaces binárias de aplicativos (ABIs), em particular a ABI x86-64 (que define que alguns argumentos formais são passados ​​pelos registradores).

Além disso, codifique algumas funções simples em C, use-as gcc -Wall -O -S -fverbose-asm para compilá-las e examine o .s arquivo assembler gerado .

Appel escreveu um artigo antigo de 1986 alegando que a coleta de lixo pode ser mais rápida que a alocação de pilha (usando o estilo de passagem de continuação no compilador), mas isso provavelmente é falso nos processadores x86 atuais (principalmente por causa dos efeitos de cache).

Observe que as convenções de chamada, ABIs e layout da pilha são diferentes nos 32 bits i686 e nos 64 bits x86-64. Além disso, as convenções de chamada (e quem é responsável por alocar ou exibir o quadro de chamada) podem ser diferentes em idiomas diferentes (por exemplo, C, Pascal, Ocaml, SBCL Common Lisp têm convenções de chamada diferentes ...)

Aliás, extensões x86 recentes como o AVX estão impondo restrições de alinhamento cada vez maiores no ponteiro da pilha (IIRC, um quadro de chamada no x86-64 deseja ser alinhado a 16 bytes, ou seja, duas palavras ou ponteiros).

Em termos simples, o programa se importa porque está usando esses dados e precisa acompanhar onde encontrá-los.

Se você declarar variáveis ​​locais em uma função, a pilha será onde elas estão armazenadas. Além disso, se você chamar outra função, a pilha será onde ela armazenará o endereço de retorno, para que possa voltar à função em que estava quando o nome que você ligou terminar e continuar de onde parou.

Sem o SP, a programação estruturada como a conhecemos seria essencialmente impossível. (Você pode resolver o problema, mas isso exigiria a implementação de sua própria versão, portanto isso não faz muita diferença.)

Para a pilha de processadores em um processador x86, a analogia de uma pilha de pratos é realmente imprecisa.
Por várias razões (principalmente históricas), a pilha do processador cresce da parte superior da memória para a parte inferior da memória, portanto, uma analogia melhor seria uma cadeia de elos de corrente pendurados no teto. Ao colocar algo na pilha, um elo de corrente é adicionado ao elo mais baixo.

O ponteiro da pilha se refere ao elo mais baixo da corrente e é usado pelo processador para "ver" onde está o elo mais baixo, para que os elos possam ser adicionados ou removidos sem ter que percorrer toda a cadeia do teto para baixo.

De certo modo, dentro de um processador x86, a pilha está de cabeça para baixo, mas o peitoril normal da terminologia da pilha é usado, para que o link mais baixo seja referido como o topo da pilha.

Os elos da cadeia a que me referi acima são na verdade células de memória em um computador e são usados ​​para armazenar variáveis ​​locais e alguns resultados intermediários dos cálculos. Os programas de computador se preocupam com a localização da parte superior da pilha (ou seja, onde fica o link mais baixo), porque a grande maioria das variáveis ​​que uma função precisa acessar existe perto de onde o ponteiro da pilha está se referindo e é rápido o acesso a elas.

Esta resposta refere-se especificamente para o apontador da pilha do fio corrente (de execução) .

Nas linguagens de programação procedural, um encadeamento normalmente tem acesso a uma pilha ¹ para os seguintes propósitos:

• Controle de fluxo, ou seja, "pilha de chamadas".
  • Quando uma função chama outra função, a pilha de chamadas lembra para onde retornar.
  • Uma pilha de chamadas é necessária porque é assim que queremos que uma "chamada de função" se comporte - "para continuar de onde paramos" .
  • Existem outros estilos de programação que não possuem chamadas de função no meio da execução (por exemplo, somente são permitidas especificar a próxima função quando o final da função atual for atingida) ou não possuem nenhuma chamada de função (apenas usando saltos goto e condicionais ) Esses estilos de programação podem não precisar de uma pilha de chamadas.
• Parâmetros de chamada de função.
  • Quando uma função chama outra função, os parâmetros podem ser pressionados na pilha.
  • É necessário que o chamador e o destinatário sigam a mesma convenção sobre quem é responsável por limpar os parâmetros da pilha, quando a chamada terminar.
• Variáveis ​​locais que vivem dentro de uma chamada de função.
  • Observe que uma variável local pertencente a um chamador pode ser acessível a um receptor, passando um ponteiro para essa variável local para o receptor.

Nota ¹ : dedicada ao uso do encadeamento, embora seu conteúdo seja totalmente legível - e esmagável - por outros encadeamentos.

Na programação de montagem, C e C ++, todos os três propósitos podem ser cumpridos pela mesma pilha. Em alguns outros idiomas, alguns propósitos podem ser cumpridos por pilhas separadas ou memória alocada dinamicamente.

Aqui está uma versão deliberadamente simplificada do que a pilha é usada.

Imagine a pilha como uma pilha de fichas. O ponteiro da pilha aponta para o cartão superior.

Quando você chama uma função:

• Você escreve o endereço do código imediatamente após a linha que chamou a função em um cartão e o coloca na pilha. (Ou seja, você incrementa o ponteiro da pilha em um e escreve o endereço para onde ele aponta)
• Depois, anote os valores contidos nos registros em alguns cartões e os coloque na pilha. (ou seja, você incrementa o ponteiro da pilha pelo número de registros e copia o conteúdo do registro no local para o qual aponta)
• Então você coloca um cartão marcador na pilha. (ou seja, você salva o ponteiro atual da pilha.)
• Em seguida, você escreve o valor de cada parâmetro com o qual a função é chamada, um em um cartão e o coloca na pilha. (ou seja, você incrementa o ponteiro da pilha pelo número de parâmetros e grava os parâmetros no local em que o ponteiro da pilha aponta.)
• Em seguida, você adiciona um cartão para cada variável local, potencialmente escrevendo o valor inicial nela. (ou seja, você incrementa o ponteiro da pilha pelo número de variáveis ​​locais.)

Neste ponto, o código na função é executado. O código é compilado para saber onde cada cartão é relativo ao topo. Portanto, sabe que a variável xé a terceira carta do topo (ou seja, o ponteiro da pilha - 3) e que o parâmetro yé a sexta carta do topo (ou seja, o ponteiro da pilha - 6.)

Este método significa que o endereço de cada variável ou parâmetro local não precisa ser inserido no código. Em vez disso, todos esses itens de dados são endereçados em relação ao ponteiro da pilha.

Quando a função retorna, a operação reversa é simplesmente:

• Procure o cartão marcador e jogue fora todos os cartões acima dele. (ou seja, defina o ponteiro da pilha para o endereço salvo.)
• Restaure os registros dos cartões salvos anteriormente e jogue-os fora. (ou seja, subtraia um valor fixo do ponteiro da pilha)
• Comece a executar o código a partir do endereço no cartão na parte superior e jogue-o fora. (ou seja, subtraia 1 do ponteiro da pilha.)

A pilha está agora de volta ao estado em que estava antes da função ser chamada.

Ao considerar isso, observe duas coisas: a alocação e desalocação de pessoas locais é uma operação extremamente rápida, pois apenas adiciona um número ou subtrai um número do ponteiro da pilha. Observe também como isso funciona naturalmente com recursão.

Isso é simplificado demais para fins explicativos. Na prática, parâmetros e locais podem ser colocados nos registradores como uma otimização, e o ponteiro da pilha geralmente será incrementado e diminuído pelo tamanho da palavra da máquina, não por um. (Para citar algumas coisas.)

As linguagens de programação modernas, como você sabe, suportam o conceito de chamadas de sub-rotina (geralmente chamadas de "chamadas de função"). Isso significa que:

1. No meio de algum código, você pode chamar outra função no seu programa;
2. Essa função não sabe explicitamente de onde foi chamada;
3. No entanto, quando seu trabalho é concluído return, o controle volta ao ponto exato em que a chamada foi iniciada, com todos os valores da variável local em vigor como quando a chamada foi iniciada.

Como o computador controla isso? Ele mantém um registro contínuo de quais funções estão aguardando quais chamadas retornar. Este registro é uma pilha e uma vez que é como um passo importante, que normalmente chamam a pilha.

E como esse padrão de chamada / retorno é tão importante, as CPUs foram projetadas para fornecer suporte de hardware especial a ele. O ponteiro da pilha é um recurso de hardware nas CPUs - um registro dedicado exclusivamente a acompanhar o topo da pilha e usado pelas instruções da CPU para ramificar em uma sub-rotina e retornar dela.