Perché i programmi utilizzano stack di chiamate, se le chiamate di funzioni nidificate possono essere inline?

32

Perché non fare in modo che il compilatore prenda un programma come questo:

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

e convertilo in un programma come questo:

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

eliminando così la necessità del computer di ricordare l'indirizzo di ritorno di c (b)?

Suppongo che l'aumento di spazio su disco e RAM necessarie per archiviare il programma e supportare la sua compilazione (rispettivamente) sia la ragione per cui utilizziamo gli stack di chiamate. È corretto?

    
posta moonman239 12.06.2015 - 09:56
fonte

6 risposte

74

Questo è chiamato "inlining" e molti compilatori lo fanno come strategia di ottimizzazione nei casi in cui ha senso.

Nel tuo particolare esempio, questa ottimizzazione salverebbe sia lo spazio che il tempo di esecuzione. Ma se la funzione è stata chiamata in più punti del programma (non è raro!), Aumenterebbe la dimensione del codice, quindi la strategia diventa più dubbia. (E naturalmente se una funzione si chiamasse direttamente o indirettamente sarebbe impossibile in linea, dal momento che il codice diventerebbe di dimensioni infinite.)

E ovviamente è possibile solo per le funzioni "private". Le funzioni esposte per i chiamanti esterni non possono essere ottimizzate, almeno non nelle lingue con collegamento dinamico.

    
risposta data 12.06.2015 - 10:07
fonte
51

Ci sono due parti alla tua domanda: Perché avere più funzioni (invece di sostituire le chiamate di funzione con la loro definizione) e perché implementare quelle funzioni con gli stack di chiamate invece di allocare staticamente i loro dati da qualche altra parte?

La prima ragione è la ricorsione. Non solo il tipo "oh facciamo una nuova chiamata per ogni singolo elemento in questa lista", anche il tipo modesto in cui si hanno probabilmente due chiamate di una funzione attive contemporaneamente, con molte altre funzioni tra di loro. Devi mettere le variabili locali su uno stack per supportare questo, e non puoi inline funzioni ricorsive in generale.

Quindi c'è un problema per le librerie: non sai quali funzioni verranno chiamate da dove e quanto spesso, quindi una "biblioteca" non potrà mai essere compilata, spedita a tutti i client in un comodo formato di alto livello che viene quindi inserito nell'applicazione. A parte altri problemi, perdi completamente il collegamento dinamico con tutti i suoi vantaggi.

Inoltre, esistono molte ragioni per non includere funzioni inline anche quando potresti:

  1. Non è necessariamente più veloce. L'impostazione del frame dello stack e la sua eliminazione sono forse una dozzina di istruzioni a ciclo singolo, per molte funzioni di grandi dimensioni o di ciclo che non corrispondono nemmeno allo 0,1% del tempo di esecuzione.
  2. Potrebbe essere più lento. La duplicazione del codice ha dei costi, ad es. Aumenterà la pressione nella cache delle istruzioni.
  3. Alcune funzioni sono molto estese e chiamate da più parti, l'inline ovunque aumenta il binario ben oltre ciò che è ragionevole.
  4. I compilatori spesso hanno difficoltà con funzioni molto grandi. A parità di altre condizioni, una funzione di dimensione 2 * N richiede più di 2 * T time in cui una funzione della dimensione N richiede T time.
risposta data 12.06.2015 - 10:11
fonte
16

Gli stack ci permettono di aggirare elegantemente i limiti imposti dal numero finito di registri.

Immagina di avere esattamente 26 globals "registers a-z" (o anche di avere solo i registri di dimensioni 7 byte del chip 8080) E ogni funzione che scrivi in questa app condivide questo elenco semplice.

Un inizio ingenuo sarebbe quello di allocare i primi registri alla prima funzione, e sapendo che ci sono voluti solo 3, inizia con "d" per la seconda funzione ... Corri velocemente.

Invece, se hai un metaphorical tape, come il turing machine, potresti avere ciascuna funzione avviare una "call another function" salvando tutte le variabili che è usando e forward () il nastro, e quindi la funzione del callee può confondersi con tutti i registri che vuole. Quando il callee è finito, restituisce il controllo alla funzione genitore, che sa dove intrappolare l'uscita del callee secondo necessità, e quindi riproduce il nastro all'indietro per ripristinarne lo stato.

Il frame di chiamata di base è proprio questo, e vengono creati e rilasciati da sequenze di codice macchina standardizzate che il compilatore inserisce attorno alle transizioni da una funzione all'altra. (È passato molto tempo da quando ho dovuto ricordare i miei frame stack di C, ma puoi leggere i vari modi in cui i doveri di chi rilascia cosa a X86_calling_conventions .)

(la ricorsione è fantastica, ma se avessi mai dovuto manipolare i registri senza uno stack, allora davvero apprezzerai gli stack.)

I suppose the increased hard disk space and RAM needed to store the program and support its compilation (respectively) is the reason why we use call stacks. Is that correct?

Mentre possiamo inline di più in questi giorni, ("più velocità" è sempre buona; "meno kb di assembly" significa molto poco in un mondo di flussi video) La principale limitazione è nella capacità del compilatore di appiattirsi su determinati tipi di pattern di codice.

Ad esempio, oggetti polimorfici - se non conosci l'unico tipo di oggetto che ti verrà consegnato, non puoi appiattirlo; devi guardare il vtable delle caratteristiche dell'oggetto e chiamare attraverso quel puntatore ... banale da fare in fase di runtime, impossibile da allineare in fase di compilazione.

Una moderna toolchain può felicemente inline una funzione definita polimorficamente quando ha appiattito abbastanza dei chiamanti per sapere esattamente quale sapore di 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);
}

in quanto sopra, il compilatore può scegliere di rimanere drasticamente in linea, da InlineMe a qualunque cosa sia all'interno di act (), né la necessità di toccare qualsiasi vtables in fase di runtime.

Ma qualsiasi incertezza in quale sapore di oggetto lo lascerà come una chiamata a una funzione discreta, anche se alcune altre invocazioni della stessa funzione sono in linea.

    
risposta data 13.06.2015 - 06:34
fonte
11

Casi che questo approccio non può gestire:

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); };}

Ci sono lingue e piattaforme con stack di chiamate limitate o senza numero. I microprocessori PIC hanno uno stack hardware limitato a 2 e 32 voci . Questo crea vincoli di design.

COBOL bans recursion: link

Imporre un divieto di ricorsione significa che puoi rappresentare l'intero callgraph del programma staticamente come un DAG. Il tuo compilatore potrebbe quindi emettere una copia di una funzione per ogni posto da cui viene chiamata con un salto fisso invece di un ritorno. Nessuna pila richiesta, solo più spazio sul programma, potenzialmente abbastanza per sistemi complessi. Ma per i piccoli sistemi embedded questo significa che puoi garantire di non avere un overflow dello stack in fase di runtime, che sarebbe una cattiva notizia per il tuo reattore nucleare / turbina jet / controllo acceleratore auto ecc.

    
risposta data 12.06.2015 - 15:59
fonte
8

Vuoi la funzione inlining e la maggior parte ( optimizing ) i compilatori lo stanno facendo.

Si noti che l'inlining richiede che la funzione chiamata sia conosciuta (ed è efficace solo se quella funzione chiamata non è troppo grande), dal momento che concettualmente sostituisce la chiamata mediante la riscrittura della funzione chiamata. Pertanto, generalmente non è possibile incorporare una funzione sconosciuta (ad esempio un puntatore a funzione e include funzioni da collegate dinamicamente librerie condivise -, che è forse visibile come metodo virtuale in alcuni vtable , ma alcuni compilatori potrebbero talvolta ottimizzare con devirtualizzazione tecniche). Naturalmente non è sempre possibile incorporare funzioni ricorsive (alcuni compilatori intelligenti potrebbero usare la valutazione parziale e in alcuni i casi sono in grado di eseguire funzioni ricorsive in linea).

Notate anche che l'inlining, anche quando è facilmente possibile, non è sempre efficace: voi (in realtà il vostro compilatore) potrebbe aumentare così tanto la dimensione del codice che cache della CPU (o predittore di ramo ) funzionerebbero in modo meno efficiente e ciò renderebbe il tuo programma corri più lentamente.

Mi concentro un pò sullo stile programmazione funzionale , dal momento che hai codificato la tua qestione in quanto tale.

Si noti che non è necessario disporre di stack di chiamate (almeno in il senso macchina dell'espressione "stack chiamate"). Potresti usare solo l'heap.

Quindi, dai un'occhiata a continuazioni e leggi ulteriori informazioni su stile di passaggio alla chiusura (CPS) e Trasformazione di CPS (intuitivamente, è possibile utilizzare le chiusure di seguito come "riquadri di chiamata" reificati allocati nell'heap e sono in grado di imitare uno stack di chiamate, quindi è necessario un efficiente garbage collector ).

Andrew Appel ha scritto un libro Compiling with Continuations e una vecchia carta la garbage collection può essere più veloce dell'assegnazione dello stack . Vedi anche il documento di A.Kennedy (ICFP2007) Compilare con le continuazioni, continua

Raccomando anche di leggere il libro Lisp In Small Pieces di Queinnec, che ha diversi capitoli relativo alla continuazione & compilazione.

Nota anche alcune lingue (es. Brainfuck ) o macchine astratte (ad es. OISC , RAM ) non hanno chiamare le strutture ma sono ancora Turing-complete , quindi non è (in teoria) necessario alcun meccanismo di chiamata di funzione, anche se è estremamente conveniente. A proposito, alcune vecchie set di istruzioni architetture (ad es. IBM / 370 ) non ha nemmeno uno stack di chiamate hardware o un'istruzione push call machine (l'IBM / 370 aveva solo un'istruzione macchina Branch and Link )

Infine, se l'intero programma (incluse tutte le librerie necessarie) non ha alcuna ricorsione, è possibile memorizzare l'indirizzo di ritorno (e le variabili "locali", che in realtà stanno diventando statiche) di ciascuna funzione in posizioni statiche. I vecchi compilatori Fortran77 l'hanno fatto nei primi anni '80 (quindi i programmi compilati non utilizzavano alcun stack di chiamate in quel momento).

    
risposta data 12.06.2015 - 10:59
fonte
7

Inlining (sostituendo le chiamate di funzione con funzionalità equivalenti) funziona bene come strategia di ottimizzazione per piccole funzioni semplici. Il sovraccarico di una chiamata di funzione può essere efficacemente scambiato per una piccola penalità nella dimensione del programma aggiunto (o in alcuni casi, nessuna penalità).

Tuttavia, le grandi funzioni che a loro volta chiamano altre funzioni potrebbero portare a un'enorme esplosione nelle dimensioni del programma se tutto fosse stato allineato.

L'intero punto delle funzioni callable è di facilitare un riutilizzo efficiente, non solo dal programmatore, ma dalla macchina stessa, e che include proprietà come memoria ragionevole o ingombro su disco.

Per quel che vale: puoi avere funzioni chiamabili senza uno stack di chiamate. Ad esempio: IBM System / 360. Quando si programma in lingue come FORTRAN su quell'hardware, il contatore del programma (indirizzo di ritorno) verrebbe salvato in una piccola sezione di memoria riservata appena prima del punto di ingresso della funzione. Consente di utilizzare le funzioni riutilizzabili, ma non consente la ricorsione o il codice multi-thread (un tentativo di chiamata ricorsiva o rientrante comporterebbe la sovrascrittura di un indirizzo di ritorno precedentemente salvato).

Come spiegato da altre risposte, gli stack sono cose buone. Facilitano la ricorsione e le chiamate multi-thread. Mentre qualsiasi algoritmo codificato per utilizzare la ricorsione potrebbe essere codificato senza fare affidamento sulla ricorsione, il risultato potrebbe essere più complesso, più difficile da mantenere e potrebbe essere meno efficiente. Non sono sicuro che un'architettura senza stack possa supportare il multi-threading.

    
risposta data 13.06.2015 - 05:13
fonte

Leggi altre domande sui tag