É um tipo de coisa híbrida? (por exemplo, meu programa .NET usa uma pilha até que atenda uma chamada assíncrona e depois muda para outra estrutura até ser concluída; nesse momento, a pilha é retornada a um estado em que pode ter certeza dos próximos itens, etc.? )
Basicamente sim.
Suponha que tenhamos
async void MyButton_OnClick() { await Foo(); Bar(); }
async Task Foo() { await Task.Delay(123); Blah(); }
Aqui está uma explicação extremamente simplificada de como as continuações são reificadas. O código real é consideravelmente mais complexo, mas isso transmite a ideia.
Você clica no botão Uma mensagem está na fila. O loop da mensagem processa a mensagem e chama o manipulador de cliques, colocando o endereço de retorno da fila de mensagens na pilha. Ou seja, o que acontece depois que o manipulador é concluído é que o loop da mensagem deve continuar em execução. Portanto, a continuação do manipulador é o loop.
O manipulador de cliques chama Foo (), colocando o endereço de retorno na pilha. Ou seja, a continuação do Foo é o restante do manipulador de cliques.
Foo chama Task.Delay, colocando o endereço de retorno na pilha.
Task.Delay faz a mágica necessária para retornar imediatamente uma tarefa. A pilha está aberta e estamos de volta ao Foo.
Foo verifica a tarefa retornada para ver se está concluída. Não é. A continuação da espera é chamar Blah (), então Foo cria um delegado que chama Blah () e assina os delegados como a continuação da tarefa. (Acabei de fazer uma pequena declaração incorreta; você entendeu? Se não, nós a revelaremos em um momento.)
O Foo cria seu próprio objeto Task, marca-o como incompleto e retorna-o à pilha para o manipulador de cliques.
O manipulador de cliques examina a tarefa de Foo e descobre que ela está incompleta. A continuação da espera no manipulador é chamar Bar (); portanto, o manipulador de cliques cria um delegado que chama Bar () e o define como a continuação da tarefa retornada por Foo (). Em seguida, ele retorna a pilha para o loop da mensagem.
O loop de mensagens continua processando as mensagens. Eventualmente, a mágica do cronômetro criada pela tarefa de atraso funciona e envia uma mensagem para a fila dizendo que a continuação da tarefa de atraso agora pode ser executada. Portanto, o loop da mensagem chama a continuação da tarefa, colocando-se na pilha como de costume. Esse delegado chama Blah (). Blah () faz o que faz e retorna a pilha.
Agora o que acontece? Aqui está a parte complicada. A continuação da tarefa de atraso não chama apenas Blah (). Ele também deve acionar uma chamada para Bar () , mas essa tarefa não sabe sobre Bar!
Na verdade, Foo criou um delegado que (1) chama Blah () e (2) chama a continuação da tarefa que Foo criou e devolveu ao manipulador de eventos. É assim que chamamos um delegado que chama Bar ().
E agora fizemos tudo o que precisávamos, na ordem correta. Como nunca paramos de processar as mensagens no loop de mensagens por muito tempo, o aplicativo permaneceu responsivo.
Que esses cenários sejam avançados demais para uma pilha faz todo sentido, mas o que substitui a pilha?
Um gráfico de objetos de tarefas que contêm referências entre si por meio das classes de fechamento de delegados. Essas classes de fechamento são máquinas de estado que controlam a posição do aguardado mais recentemente executado e os valores dos habitantes locais. Além disso, no exemplo dado, uma fila de ações de estado global implementada pelo sistema operacional e o loop de mensagens que executam essas ações.
Exercício: como você acha que tudo isso funciona em um mundo sem loops de mensagens? Por exemplo, aplicativos de console. aguardar em um aplicativo de console é bem diferente; você pode deduzir como funciona do que você sabe até agora?
Quando soube disso anos atrás, a pilha estava lá porque era muito rápida e leve, uma parte da memória alocada no aplicativo para longe do heap porque suportava um gerenciamento altamente eficiente para a tarefa em questão (trocadilho intencional?). O que mudou?
As pilhas são uma estrutura de dados útil quando a vida útil das ativações do método forma uma pilha, mas no meu exemplo as ativações do manipulador de cliques, Foo, Bar e Blah não formam uma pilha. E, portanto, a estrutura de dados que representa esse fluxo de trabalho não pode ser uma pilha; é um gráfico de tarefas e delegados alocados em heap que representa um fluxo de trabalho. As aguardas são os pontos no fluxo de trabalho em que não é possível avançar mais no fluxo de trabalho até que o trabalho iniciado anteriormente seja concluído; enquanto esperamos, podemos executar outro trabalho que não depende da conclusão dessas tarefas iniciadas.
A pilha é apenas uma matriz de quadros, onde os quadros contêm (1) ponteiros para o meio das funções (onde a chamada aconteceu) e (2) valores de variáveis locais e temperaturas. A continuação das tarefas é a mesma coisa: o delegado é um ponteiro para a função e possui um estado que faz referência a um ponto específico no meio da função (onde a espera aconteceu), e o fechamento possui campos para cada variável local ou temporária . Os quadros simplesmente não formam mais um bom arranjo, mas todas as informações são iguais.
Appel escreveu que uma coleta de lixo de papel antiga pode ser mais rápida que a alocação de pilha . Leia também o livro Compilando com continuações e o manual de coleta de lixo . Algumas técnicas de GC são (de maneira não intuitiva) muito eficientes. O estilo de passagem de continuação define uma transformação canônica de programa inteiro (a transformação CPS ) para se livrar das pilhas (substituindo conceitualmente os quadros de chamadas por fechamentos alocados por heap , em outras palavras "reificando" os quadros de chamada individuais como "valores" ou "objetos" individuais )
Mas a pilha de chamadas ainda é muito usada, e os processadores atuais têm hardware dedicado (registro de pilha, máquinas de cache, ...) dedicado às pilhas de chamadas (e isso ocorre porque a maioria das linguagens de programação de baixo nível, principalmente C, é mais fácil de implementar com uma pilha de chamadas). Observe também que as pilhas são compatíveis com o cache (e isso importa muito para o desempenho).
Na prática, as pilhas de chamadas ainda estão aqui. Mas agora temos muitos deles, e algumas vezes a pilha de chamadas é dividida em muitos segmentos menores (por exemplo, algumas páginas de 4Kbytes cada), que às vezes são coletados como lixo ou alocados por heap. Esses segmentos de pilha podem ser organizados em alguma lista vinculada (ou em alguma estrutura de dados mais complexa, quando necessário). Por exemplo, os compiladores do GCC têm uma
-fsplit-stack
opção (especialmente útil para Go, suas "goroutines" e seus "processos assíncronos"). Com pilhas divididas, você pode ter muitos milhares de pilhas (e as co-rotinas se tornam mais fáceis de implementar) feitas de milhões de pequenos segmentos de pilha, e "desenrolando" a pilha pode ser mais rápida (ou pelo menos quase tão rápida quanto em um único pedaço) pilha).(em outras palavras, a distinção entre pilha e pilha é embaçada, mas pode exigir transformação de todo o programa ou alteração incompatível da convenção de chamada e do compilador)
Veja também this & that e muitos documentos (por exemplo, isso ) discutindo a transformação do CPS. Leia também sobre ASLR e call / cc . Leia (& STFW) mais sobre continuações .
As implementações .CLR & .NET podem não ter uma transformação avançada em GC & CPS, por muitos motivos pragmáticos. É uma troca relacionada a transformações inteiras do programa (e facilidade de usar rotinas C de baixo nível e ter um tempo de execução codificado em C ou C ++).
O Chicken Scheme está usando a pilha da máquina (ou C) de uma maneira não convencional com a transformação do CPS: toda alocação acontece na pilha e, quando ela se torna muito grande, uma etapa geracional de cópia e encaminhamento do GC passa a mover os valores alocados recentes da pilha (e provavelmente o continuação atual) para o heap e, em seguida, a pilha é drasticamente reduzida com um grande
setjmp
.Leia também SICP , Pragmática da Linguagem de Programação , o Dragon Book , Lisp In Small Pieces .
fonte