Una struttura stack è utilizzata per i processi asincroni?

11

Questo domanda ha una risposta eccellente da parte di Eric Lippert che descrive a cosa serve lo stack. Per anni ho saputo - in generale - che cos'è lo stack e come è usato, ma alcune parti delle sue risposte mi chiedono se questa struttura dello stack sia oggi meno utilizzata dove la programmazione asincrona è la norma.

Dalla sua risposta:

the stack is part of the reification of continuation in a language without coroutines.

In particolare, la parte senza coroutine di questo mi chiede.

Ci spiega un po 'di più qui:

Coroutines are functions that can remember where they were, yield control to another coroutine for a while, and then resume where they left off later, but not necessarily immediately after the just-called coroutine yields. Think of "yield return" or "await" in C#, which must remember where they were when the next item is requested or the asynchronous operation completes. Languages with coroutines or similar language features require more advanced data structures than a stack in order to implement continuation.

Questo è eccellente per quanto riguarda lo stack, ma mi lascia una domanda senza risposta su quale struttura viene utilizzata quando uno stack è troppo semplice per gestire queste funzionalità linguistiche che richiedono strutture dati più avanzate?

Lo stack sta andando via man mano che la tecnologia progredisce? Cosa lo sostituisce? È un tipo di cosa ibrido? (ad esempio, il mio programma .NET usa uno stack fino a quando non raggiunge una chiamata asincrona, quindi passa a un'altra struttura fino al completamento, a quel punto lo stack viene riportato a uno stato in cui può essere sicuro degli elementi successivi, ecc.? )

Che questi scenari siano troppo avanzati per uno stack ha perfettamente senso, ma cosa sostituisce lo stack? Quando ho imparato a conoscere questo anno fa, lo stack era lì perché era veloce e leggero, un pezzo di memoria assegnato all'applicazione lontano dall'heap perché supportava una gestione altamente efficiente per il compito in questione (gioco di parole?). Cosa è cambiato?

    
posta jleach 11.01.2017 - 04:05
fonte

2 risposte

14

Is it a hybrid type of thing? (e.g., does my .NET program use a stack until it hits an async call then switches over to some other structure until completed, at which point the stack is unwound back to a state where it can be sure of the next items, etc?)

Fondamentalmente sì.

Supponiamo di avere

async void MyButton_OnClick() { await Foo(); Bar(); }
async Task Foo() { await Task.Delay(123); Blah(); }

Ecco una spiegazione estremamente semplificata di come le continuazioni vengono reificate. Il codice reale è considerevolmente più complesso, ma questa è l'idea.

Fai clic sul pulsante. Un messaggio è in coda. Il ciclo dei messaggi elabora il messaggio e chiama il gestore dei clic, inserendo l'indirizzo di ritorno della coda dei messaggi sullo stack. Cioè, la cosa che succede dopo il gestore è fatto è che il ciclo del messaggio deve continuare a funzionare. Quindi la continuazione del gestore è il ciclo.

Il gestore dei clic chiama Foo (), mettendo l'indirizzo di ritorno di se stesso nello stack. Cioè, la continuazione di Foo è il resto del gestore di clic.

Foo chiama Task.Delay, mettendo lo stesso indirizzo di ritorno sullo stack.

Task.Delay fa la magia necessaria per restituire immediatamente un'attività. La pila è spuntata e siamo di nuovo in Pippo.

Foo controlla l'attività restituita per vedere se è stata completata. Non è. La continuazione di attende è di chiamare Blah (), quindi Foo crea un delegato che chiama Blah () e firma che delegano come la continuazione dell'attività. (Ho appena fatto una piccola disapprovazione, l'hai capito? In caso contrario, lo riveleremo tra un momento.)

Foo crea quindi il proprio oggetto Task, lo contrassegna come incompleto e lo restituisce allo stack al gestore dei clic.

Il gestore dei clic esamina l'attività di Foo e scopre che è incompleto. La continuazione dell'attesa nel gestore consiste nel chiamare Bar (), quindi il gestore di clic crea un delegato che chiama Bar () e lo imposta come la continuazione dell'attività restituita da Foo (). Quindi restituisce lo stack al ciclo dei messaggi.

Il loop dei messaggi continua a elaborare i messaggi. Alla fine la magia del timer creata dal task di ritardo fa la sua cosa e invia un messaggio alla coda dicendo che la continuazione dell'attività di ritardo può ora essere eseguita. Quindi il ciclo dei messaggi chiama la continuazione dell'attività, mettendosi in pila come al solito. Quel delegato chiama Blah (). Blah () fa quello che fa e restituisce lo stack.

Ora cosa succede? Ecco il trucco. La continuazione dell'attività di ritardo non chiama solo Blah (). Deve anche attivare una chiamata a Bar () , ma quell'attività non conosce Bar!

Foo in realtà ha creato un delegato che (1) chiama Blah () e (2) chiama la continuazione dell'attività che Foo ha creato e restituita al gestore di eventi. È così che chiamiamo un delegato che chiama Bar ().

E ora abbiamo fatto tutto ciò che dovevamo fare, nell'ordine corretto. Ma non abbiamo mai interrotto l'elaborazione dei messaggi nel loop dei messaggi per molto tempo, quindi l'applicazione è rimasta reattiva.

That these scenarios are too advanced for a stack makes perfect sense, but what replaces the stack?

Un grafico di oggetti task che contengono riferimenti l'uno all'altro tramite le classi di chiusura dei delegati. Queste classi di chiusura sono macchine di stato che tengono traccia della posizione dell'attesa eseguita più recentemente e dei valori dei locali. Inoltre, nell'esempio fornito, una coda di azioni a livello globale implementata dal sistema operativo e il loop di messaggi che esegue tali azioni.

Esercizio: come pensi che tutto funzioni in un mondo senza loop di messaggi? Ad esempio, le applicazioni della console. attendere in un'app console è abbastanza diverso; puoi dedurre come funziona da quello che sai finora?

When I had learned about this years ago, the stack was there because it was lightning fast and lightweight, a piece of memory allocated at application away from the heap because it supported highly efficient management for the task at hand (pun intended?). What's changed?

Le pile sono una struttura dati utile quando le durate delle attivazioni del metodo formano uno stack, ma nel mio esempio le attivazioni del gestore dei clic, Foo, Bar e Blah non formano una pila. E quindi la struttura dati che rappresenta quel flusso di lavoro non può essere uno stack; piuttosto è un grafico di attività e delegati allocati all'heap che rappresenta un flusso di lavoro. Le attese sono i punti nel flusso di lavoro in cui non è possibile progredire ulteriormente nel flusso di lavoro fino al completamento del lavoro iniziato in precedenza; mentre stiamo aspettando, possiamo eseguire un lavoro altro che non dipenda da quelle particolari attività avviate che sono state completate.

Lo stack è solo una serie di frame, dove i frame contengono (1) puntatori al centro delle funzioni (dove è avvenuta la chiamata) e (2) i valori delle variabili locali e delle temp. La continuazione dei compiti è la stessa cosa: il delegato è un puntatore alla funzione e ha uno stato che fa riferimento a un punto specifico nel mezzo della funzione (dove è avvenuta l'attesa) e la chiusura ha campi per ogni variabile locale o temporanea . I fotogrammi non formano più una bella matrice ordinata, ma tutte le informazioni sono uguali.

    
risposta data 11.01.2017 - 10:13
fonte
8

Appel ha scritto un vecchio documento la garbage collection può essere più veloce dell'assegnazione dello stack . Leggi anche il suo Compilazione con continuazioni libro e il manuale della raccolta di dati inutili . Alcune tecniche di GC sono (non intuitivamente) molto efficienti. Lo stile di passaggio continuo definisce una trasformazione canonica whole-program (il CPS trasformazione ) per eliminare gli stack (sostituendo concettualmente i frame di chiamata con allocazione heap close , in altre parole "reificare" i singoli frame di chiamata come singoli "valori" o "oggetti").

Ma lo stack di chiamate è ancora molto utilizzato e i processori attuali dispongono di hardware dedicato (registro dello stack, macchinario di cache, ecc.). ...) dedicato agli stack di chiamate (ed è così perché la maggior parte dei linguaggi di programmazione di basso livello, in particolare C, è più facile da implementare con uno stack di chiamate). Nota anche che gli stack sono cache amichevoli (e questo è importante per un lotto per le prestazioni).

In pratica, gli stack di chiamate sono ancora qui. Ma ora ne abbiamo molti, e a volte lo stack delle chiamate è suddiviso in molti segmenti più piccoli (ad esempio di poche pagine di 4Kbyte ciascuno), che a volte sono garbage collection o heap allocato. Questi segmenti dello stack potrebbero essere organizzati in un elenco collegato (o in una struttura di dati più complessa, se necessario). Ad esempio, i GCC compilatori hanno un'opzione -fsplit-stack (particolarmente utile per Go e le sue "goroutine" e "processi asincroni"). Con stack divisi puoi avere molte migliaia di stack (e le co-routine diventano più facili da implementare) fatte di milioni di piccoli segmenti di stack, e "srotolare" lo stack potrebbe essere più veloce (o almeno altrettanto veloce come con un singolo pezzo stack).

(in altre parole, la distinzione tra stack e heap è sfocata, ma potrebbe richiedere la trasformazione dell'intero programma o la modifica incompatibile della convenzione di chiamata e del compilatore)

Vedi anche questo & che e molti papers (ad es. questo ) discutendo la trasformazione di CPS. Leggi anche su ASLR & chiama / cc . Leggi (& STFW) altro su continuazioni .

Il .CLR & Le implementazioni .NET potrebbero non avere GC & state-of-the-art all'avanguardia; Trasformazione CPS, per molte ragioni pragmatiche. È un compromesso legato alle trasformazioni di interi programmi (e alla facilità di utilizzare routine C di basso livello e un runtime codificato in C o C ++).

Chicken Scheme utilizza lo stack della macchina (o C) in modo non convenzionale con la trasformazione CPS: ogni allocazione avviene sul stack e quando diventa troppo grande una copia generazionale di GC & la fase di inoltro avviene per spostare i valori allocati dello stack recente (e probabilmente la continuazione corrente) nell'heap e quindi lo stack viene drasticamente ridotto con un setjmp elevato.

Leggi anche SICP , Pragmatica del linguaggio di programmazione , Libro del drago , Lisp in piccoli pezzi .

    
risposta data 11.01.2017 - 06:26
fonte

Leggi altre domande sui tag