Perché abbiamo bisogno di un Heap se tutto ciò può essere fatto in modo molto più efficiente sullo Stack?

22

Questo è in qualche modo correlato alla domanda che ho posto ieri su perché entrambi gli e un heap sono necessari nelle applicazioni che usiamo oggi (e perché non possiamo vai con un Heap invece di entrambi, per avere uno standard semplice e singolare da seguire).

Tuttavia, molte delle risposte indicano che uno Stack è insostituibile a causa del fatto che è molte centinaia (o migliaia) di volte più veloce rispetto al tentativo di allocare / fare riferimento all'Heap. So che c'è un problema con l'allocazione dello storage dinamico se eliminiamo l'heap, ma non c'è un modo per aggirare questo, o forse, un modo per migliorare lo stack in modo che possa gestire l'allocazione dinamica della memoria?

    
posta Dark Templar 09.10.2011 - 19:53
fonte

6 risposte

23

Il problema con gli stack è che non è possibile "liberare" la memoria a meno che non sia in cima allo stack. Ad esempio, supponi di aver assegnato 3 elementi di dimensioni diverse:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

Lo stack avrebbe a in basso, b nel mezzo e c in alto. Questo diventa problematico se vogliamo liberare b :

free(b); // b is not on top! We have to wait until c is freed!

La soluzione alternativa è spostare tutti i dati dopo b e spostare se è così dopo a . Funziona, ma in questo caso richiede 5000000 copie - qualcosa che sarà molto più lento di un heap.

Ecco perché abbiamo un mucchio. Mentre l'allocazione può essere più lenta di uno stack ( O(log n) rispetto a O(1) ), gli heap consentono di liberare memoria in una posizione arbitraria per essere veloci - O(log n) , rispetto a O(n) di uno stack

    
risposta data 09.10.2011 - 22:20
fonte
4

Lo stack è una struttura LIFO (last-in-first-out), in cima alla quale viene mantenuto un puntatore di riferimento (generalmente supportato dall'hardware). Detto questo, tutto ciò che si sta tentando di allocare sullo stack anziché sull'heap dovrebbe essere una variabile locale in ogni funzione, nella parte superiore di questo stack. Quindi, la ragione principale contro una pila è che la tua routine main () dovrebbe preallocare tutte le strutture di dati che il tuo programma usa (che dovrebbero essere presenti per tutta la durata del tuo programma) in anticipo poiché tutte le strutture dati allocate entro la funzione le chiamate verranno rimosse alla fine quando quelle chiamate di funzione ritornano e i loro frame o record di attivazione vengono cancellati dallo stack.

    
risposta data 09.10.2011 - 20:05
fonte
4

Lo stack è per-thread, Heap è a livello di processo

Se ho 100 thread tutti gli elementi di lavoro di elaborazione che metto in coda, esattamente dove allocare gli elementi di lavoro in modo tale che uno qualsiasi dei 100 thread possa vederli?

Esistono anche altri tipi di memoria

es. file mappati in memoria, memoria condivisa, mappatura I / O (modalità kernel). L'argomento dell'efficienza è discutibile in queste situazioni.

    
risposta data 10.10.2011 - 13:57
fonte
3

Le pile funzionano molto bene per le allocazioni di memoria che obbediscono alle regole di Last in First Out (LIFO), ovvero, si libera la memoria nell'esatto ordine inverso che viene allocata. Il LIFO è uno schema di allocazione di memoria molto comune, forse il più comune. Ma non è l'unico modello, o addirittura l'unico modello comune. Per scrivere un programma efficiente in grado di affrontare una vasta gamma di problemi, dobbiamo tenere conto dei modelli meno comuni, anche se ciò significa una infrastruttura più complessa.

Se riesco a ottenere tutti i meta per un paragrafo: sei un principiante, come un principiante apprezzi la semplicità e le regole in bianco e nero. Tuttavia, come principiante si ha solo una visione spettrale della gamma di problemi e vincoli che devono essere soddisfatti dai programmi per computer. Stai entrando in una tecnologia in sviluppo attivo da 75 anni. Non c'è niente di sbagliato nel chiedere perché le cose sono come sono, ma la risposta sarà generalmente "Sì, abbiamo provato il metodo semplice e diretto 50 anni fa, e si è scoperto che non funzionava molto bene per intere classi di problemi, quindi abbiamo dovuto fare qualcosa di più complicato ". Come tecnologia, la semplicità deve generalmente lasciare spazio a efficienza e flessibilità.

    
risposta data 09.10.2011 - 22:27
fonte
0

Per un altro esempio, chiusure. Se impili pop, puoi perdere il record di attivazione della chiusura. Quindi, se vuoi che la funzione anonima e i suoi dati persistano, devi salvarla da qualche altra parte rispetto allo stack di runtime.

    
risposta data 11.10.2011 - 04:22
fonte
0

Tra molti altri motivi per l'allocazione dell'heap storage.

Se si desidera passare l'indirizzo di un oggetto a un programma chiamante, non si deve passare l'indirizzo di una variabile stack, poiché l'archiviazione dello stack verrà riutilizzata e probabilmente sovrascritta dalla funzione successiva chiamata. È necessario ottenere la memoria richiesta usando malloc () per assicurarsi che non venga sovrascritta dalle chiamate alle funzioni successive.

Puoi passare gli indirizzi degli elementi dello stack dalla tua funzione alle funzioni che chiami, perché puoi garantire che esisteranno fino a quando il tuo programma "ritorna ()". Ma non appena la tua funzione ritorna, tutto lo stack è in palio.

    
risposta data 11.10.2011 - 05:42
fonte

Leggi altre domande sui tag