Por que os programas usam pilhas de chamadas, se chamadas de função aninhadas podem ser incorporadas?

32

Por que não fazer o compilador executar um programa como este:

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

e converta-o em um programa como este:

function c(b) { return b^2 + 5 };

eliminando assim a necessidade do computador de lembrar o endereço de retorno de c (b)?

Suponho que o aumento do espaço no disco rígido e da RAM necessários para armazenar o programa e suportar sua compilação (respectivamente) seja a razão pela qual usamos pilhas de chamadas. Isso está correto?

moonman239
fonte
30
Veja o que acontece se você fizer isso em um programa com tamanho significativo. Em particular, as funções são chamadas de mais de um local.
user253751
10
Além disso, às vezes o compilador não sabe qual função é chamada! Exemplo bobo:window[prompt("Enter function name","")]()
user253751
26
Como você implementa function(a)b { if(b>0) return a(b-1); }sem uma pilha?
pjc50
8
Onde está a relação com a programação funcional?
Mašťov
14
@ pjc50: é recursivo de cauda, ​​então o compilador o traduz em um loop com um mutável b. Porém, nem todas as funções recursivas podem eliminar a recursão, e mesmo quando a função pode, em princípio, o compilador pode não ser inteligente o suficiente para fazê-lo.
21715 Steve Jobs (

Respostas:

75

Isso é chamado de "inlining" e muitos compiladores fazem isso como uma estratégia de otimização nos casos em que faz sentido.

No seu exemplo específico, essa otimização economizaria espaço e tempo de execução. Mas se a função fosse chamada em vários locais do programa (não incomum!), Aumentaria o tamanho do código, para que a estratégia se tornasse mais duvidosa. (E, é claro, se uma função se chama direta ou indiretamente, seria impossível integrar, pois o código se tornaria infinito em tamanho.)

E, obviamente, isso só é possível para funções "privadas". As funções expostas para chamadores externos não podem ser otimizadas, pelo menos não em idiomas com vínculo dinâmico.

JacquesB
fonte
7
@Blrfl: Compiladores modernos, na verdade, não precisam mais de definições no cabeçalho; eles podem se alinhar nas unidades de tradução. Isso requer um vinculador decente, no entanto. As definições nos arquivos de cabeçalho são uma solução alternativa para os vinculadores burros.
MSalters
3
"As funções expostas para chamadores externos não podem ser otimizadas" - a função precisa existir, mas qualquer site de chamada específico (no seu próprio código ou, se eles tiverem a fonte, os chamadores externos) podem ser incorporados.
Random832
14
Uau, 28 votos positivos para uma resposta que nem sequer menciona a razão pela qual inline tudo é impossível: recursão.
Mašťov
3
@R ..: LTO é otimização de tempo de LINK, não LOAD Time Optimization.
MSalters
2
@immibis: Mas se essa pilha explícita for introduzida pelo compilador, essa pilha será a pilha de chamadas.
user2357112 suporta Monica
51

Há duas partes em sua pergunta: por que ter várias funções (em vez de substituir chamadas de função por sua definição) e por que implementar essas funções com pilhas de chamadas em vez de alocar estaticamente seus dados em outro lugar?

A primeira razão é recursão. Não apenas o tipo "oh, vamos fazer uma nova chamada de função para cada item desta lista", também o tipo modesto em que você pode ter duas chamadas de uma função ativas ao mesmo tempo, com muitas outras funções entre elas. Você precisa colocar variáveis ​​locais em uma pilha para suportar isso e não pode incorporar funções recursivas em geral.

Há um problema para as bibliotecas: você não sabe quais funções serão chamadas a partir de onde e com que frequência; portanto, uma "biblioteca" nunca poderá realmente ser compilada, enviada apenas para todos os clientes em algum formato conveniente de alto nível que será inline no aplicativo. Além de outros problemas, você perde completamente o vínculo dinâmico com todas as suas vantagens.

Além disso, há muitos motivos para não incorporar funções, mesmo quando você pode:

  1. Não é necessariamente mais rápido. Configurar o quadro da pilha e derrubá-lo talvez seja uma dúzia de instruções de ciclo único, para muitas funções grandes ou em loop que nem sequer são 0,1% do tempo de execução.
  2. Pode ser mais lento. A duplicação de código tem custos, por exemplo, isso colocará mais pressão no cache de instruções.
  3. Algumas funções são muito grandes e são chamadas de muitos lugares, inseri-las em todos os lugares aumenta o binário muito além do razoável.
  4. Os compiladores geralmente enfrentam dificuldades com funções muito grandes. Tudo o resto é igual, uma função do tamanho 2 * N leva mais de 2 * T tempo, enquanto uma função do tamanho N leva T tempo.

fonte
1
Estou surpreso com o ponto 4. Qual é o motivo disso?
JacquesB
12
@JacquesB Muitos algoritmos de otimização são quadráticos, cúbicos ou até tecnicamente completos para NP. O exemplo canônico é a alocação de registros, que é NP-completa por analogia com a coloração do gráfico. (Geralmente, os compiladores não tentam uma solução exata, mas apenas algumas heurísticas muito ruins são executadas em tempo linear.) Muitas otimizações simples de uma passagem precisam primeiro de análises superlineares, como tudo o que depende da dominância nos fluxos de controle (geralmente n log n time com n blocos básicos).
2
"Você realmente tem duas perguntas aqui" Não, não tenho. Apenas um - por que não tratar uma chamada de função como apenas um espaço reservado que o compilador pode, por exemplo, substituir pelo código da função chamada?
moonman239
4
@ moonman239 Então sua redação me assustou. Ainda assim, sua pergunta pode ser decomposta como eu faço na minha resposta e acho que essa é uma perspectiva útil.
16

As pilhas nos permitem ignorar elegantemente os limites impostos pelo número finito de registros.

Imagine ter exatamente 26 globais "registra az" (ou mesmo apenas os registros de 7 bytes do chip 8080) E todas as funções que você escreve neste aplicativo compartilham essa lista simples.

Um começo ingênuo seria alocar os primeiros registros para a primeira função e, sabendo que foram necessários apenas 3, inicie com "d" para a segunda função ... Você se esgota rapidamente.

Em vez disso, se você tiver uma fita metafórica, como a máquina de turing, cada função poderá iniciar uma "chamar outra função" salvando todas as variáveis ​​que está usando e encaminhar () a fita e, em seguida, a função de chamada pode se confundir com tantas registra como deseja. Quando o chamado é retornado, ele retorna o controle para a função pai, que sabe onde capturar a saída do receptor conforme necessário e, em seguida, reproduz a fita para trás para restaurar seu estado.

Seu quadro de chamada básico é exatamente isso e é criado e descartado por seqüências de código de máquina padronizadas que o compilador realiza nas transições de uma função para outra. (Faz muito tempo que eu não lembro dos meus quadros de pilha C, mas você pode ler sobre as várias maneiras das tarefas de quem descarta o que em X86_calling_conventions .)

(a recursão é incrível, mas se você já teve que fazer malabarismos com registros sem uma pilha, apreciaria muito as pilhas.)


Suponho que o aumento do espaço no disco rígido e da RAM necessários para armazenar o programa e suportar sua compilação (respectivamente) seja a razão pela qual usamos pilhas de chamadas. Isso está correto?

Embora possamos alinhar mais atualmente, ("mais velocidade" é sempre bom; "menos kb de montagem" significa muito pouco em um mundo de fluxos de vídeo). A principal limitação está na capacidade do compilador de nivelar certos tipos de padrões de código.

Por exemplo, objetos polimórficos - se você não conhece o único e único tipo de objeto a ser entregue, não pode achatar; você precisa olhar para a tabela de recursos do objeto e chamar por esse ponteiro ... trivial para fazer em tempo de execução, impossível alinhar em tempo de compilação.

Uma cadeia de ferramentas moderna pode alinhar alegremente uma função definida polimorficamente quando achatar o (s) chamador (es) o suficiente para saber exatamente qual é o sabor do obj:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

acima, o compilador pode optar por manter o status interno, desde o InlineMe até o que estiver dentro do ato (), nem a necessidade de tocar em nenhuma vtables no tempo de execução.

Mas qualquer incerteza quanto ao sabor do objeto o deixará como uma chamada para uma função discreta, mesmo que outras invocações da mesma função sejam incorporadas.

xander
fonte
11

Casos que essa abordagem não pode tratar:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

Não são linguagens e plataformas com pilhas pouca ou nenhuma chamada. Os microprocessadores PIC têm uma pilha de hardware limitada a entre 2 e 32 entradas . Isso cria restrições de design.

COBOL proíbe recursão: https://stackoverflow.com/questions/27806812/in-cobol-is-it-possible-to-recursively-call-a-paragraph

A imposição de uma proibição de recursão significa que você pode representar o gráfico de chamada inteiro do programa estaticamente como um DAG. Seu compilador poderá emitir uma cópia de uma função para cada local a partir do qual é chamada com um salto fixo em vez de um retorno. Nenhuma pilha é necessária, apenas mais espaço de programa, potencialmente bastante para sistemas complexos. Mas para pequenos sistemas embarcados, isso significa que você pode garantir que não haja excesso de pilha durante a execução, o que seria uma má notícia para o controle de reator nuclear / turbina a jato / acelerador de carro etc.

pjc50
fonte
12
Seu primeiro exemplo é recursão básica e você está correto lá. Mas seu segundo exemplo parece ser um loop for chamando outra função. Integrar a função é diferente de desenrolar um loop; a função pode ser alinhada sem desenrolar o loop. Ou eu perdi alguns detalhes sutis?
precisa saber é
1
Se o seu primeiro exemplo pretende definir a série Fibonacci, está errado. (Está faltando uma fibchamada.)
Paŭlo Ebermann 14/15
1
Embora proibir a recursão signifique que todo o gráfico de chamadas possa ser representado como um DAG, isso não significa que se possa listar a lista completa de sequências de chamadas aninhadas em uma quantidade razoável de espaço. Em um projeto meu para um microcontrolador com 128 KB de espaço de código, cometi o erro de solicitar um gráfico de chamada que incluísse todas as funções que pudessem afetar o requisito máximo de parâmetro-RAM e esse gráfico de chamada tivesse terminado em um show. Um gráfico de chamadas completo teria sido ainda mais longo, e isso era para um programa que cabia em 128K de espaço de código.
precisa
8

Você quer que a função inlining , ea maioria ( otimização ) compiladores estão fazendo isso.

Observe que inlining requer que a função chamada seja conhecida (e é efetiva apenas se a função chamada não for muito grande), pois conceitualmente está substituindo a chamada pela reescrita da função chamada. Portanto, você geralmente não pode incorporar uma função desconhecida (por exemplo, um ponteiro de função - e que inclui funções de bibliotecas compartilhadas dinamicamente vinculadas -, que talvez seja visível como um método virtual em algumas tabelas , mas alguns compiladores às vezes podem otimizar através de técnicas de destirtualização ). Obviamente, nem sempre é possível alinhar funções recursivas (alguns compiladores inteligentes podem usar avaliação parcial e, em alguns casos, conseguir alinhar funções recursivas).

Observe também que o inlining, mesmo quando é facilmente possível, nem sempre é eficaz: você (na verdade seu compilador) pode aumentar tanto o tamanho do código que os caches da CPU (ou o preditor de ramificação ) funcionariam com menos eficiência e isso faria com que seu programa fosse executado Mais devagar.

Estou focando um pouco no estilo de programação funcional , já que você marcou sua pergunta como tal.

Observe que você não precisa ter nenhuma pilha de chamadas (pelo menos no sentido de máquina da expressão "pilha de chamadas"). Você poderia usar apenas a pilha.

Portanto, dê uma olhada nas continuações e leia mais sobre o estilo de passagem de continuação (CPS) e a transformação do CPS (intuitivamente, você pode usar os fechamentos de continuação como "quadros de chamada" reificados alocados no heap, e eles meio que imitam uma pilha de chamadas; você precisa de um coletor de lixo eficiente ).

Andrew Appel escreveu um livro Compilando com continuações e uma coleta de lixo de papel antiga pode ser mais rápida que a alocação de pilha . Veja também o artigo de A.Kennedy (ICFP2007) Compilando com continuações, continuação

Também recomendo a leitura do livro Lisp In Small Pieces , de Queinnec , que possui vários capítulos relacionados à continuação e compilação.

Observe também que algumas linguagens (por exemplo, Brainfuck ) ou máquinas abstratas (por exemplo , OISC , RAM ) não possuem nenhum recurso de chamada, mas ainda estão completas com Turing , portanto você (em teoria) nem precisa de nenhum mecanismo de chamada de função, mesmo que é extremamente conveniente. BTW, algumas arquiteturas antigas de conjuntos de instruções (por exemplo, IBM / 370 ) nem sequer possuem uma pilha de chamadas de hardware ou uma instrução de máquina de chamada de envio (o IBM / 370 tinha apenas uma instrução de máquina de Filial e Link )

Por fim, se todo o seu programa (incluindo todas as bibliotecas necessárias) não tiver nenhuma recursão, você poderá armazenar o endereço de retorno (e as variáveis ​​"locais", que na verdade estão se tornando estáticas) de cada função em locais estáticos. Os antigos compiladores Fortran77 fizeram isso no início dos anos 80 (portanto, os programas compilados não usavam nenhuma pilha de chamadas naquele momento).

Basile Starynkevitch
fonte
2
É muito discutível se o CPS não tem "pilha de chamadas". Não está na pilha , na região mística da RAM comum que tem um pouco de suporte de hardware %esp, etc., mas ainda mantém a contabilidade equivalente em uma pilha de espaguete com nome apropriado em outra região da RAM. O endereço de retorno, em particular, é essencialmente codificado na continuação. E, é claro, as continuações não são mais rápidas (e parece-me que é nisso que o OP estava chegando) do que não fazer chamadas de forma alguma através do inlining.
Os documentos antigos de Appel alegaram (e demonstraram com benchmarking) que o CPS pode ser tão rápido quanto ter uma pilha de chamadas.
Basile Starynkevitch
Sou cético quanto a isso, mas, independentemente disso, não foi o que afirmei.
1
Na verdade, isso foi na estação de trabalho MIPS do final dos anos 80. Provavelmente, a hierarquia de cache nos PCs atuais tornaria o desempenho um pouco diferente. Houve vários artigos que analisam as alegações de Appel (e de fato, em máquinas atuais, alocação de pilha pode ser ligeiramente mais rápido -pela alguns percents- que cuidadosamente elaborado coleta de lixo)
Basile Starynkevitch
1
@ Gilles: Muitos núcleos ARM mais novos, como o Cortex M0 e M3 (e provavelmente outros como o M4), têm suporte de pilha de hardware para coisas como manipulação de interrupções. Além disso, o conjunto de instruções Thumb inclui um subconjunto limitado das instruções STRM / STRM que inclui STRMDB R13 com qualquer combinação de R0-R7 com / sem LR e LDRMIA R13 de qualquer combinação de R0-R7 com / sem PC, que trata efetivamente R13 como um ponteiro de pilha.
precisa
8

Inlining (substituindo chamadas de função por funcionalidade equivalente) funciona bem como uma estratégia de otimização para pequenas funções simples. A sobrecarga de uma chamada de função pode ser efetivamente trocada por uma pequena penalidade no tamanho adicionado do programa (ou, em alguns casos, nenhuma penalidade).

No entanto, grandes funções que por sua vez chamam outras funções podem levar a uma enorme explosão no tamanho do programa, se tudo estiver embutido.

O objetivo principal das funções que podem ser chamadas é facilitar a reutilização eficiente, não apenas pelo programador, mas pela própria máquina, e isso inclui propriedades como memória razoável ou pegada no disco.

Pelo que vale: você pode ter funções que podem ser chamadas sem uma pilha de chamadas. Por exemplo: IBM System / 360. Ao programar em idiomas como FORTRAN nesse hardware, o contador de programa (endereço de retorno) seria salvo em uma pequena seção de memória reservada logo à frente do ponto de entrada da função. Ele permite funções reutilizáveis, mas não permite recursão ou código multiencadeado (uma tentativa de uma chamada recursiva ou reentrante resultaria na substituição de um endereço de retorno salvo anteriormente).

Conforme explicado por outras respostas, as pilhas são boas. Eles facilitam a recursão e as chamadas multithread. Embora qualquer algoritmo codificado para usar a recursão possa ser codificado sem depender da recursão, o resultado pode ser mais complexo, mais difícil de manter e menos eficiente. Não tenho certeza de que uma arquitetura sem pilha possa suportar multithreading.

Zenilogix
fonte