Potrebbe essere più efficiente per i sistemi in generale eliminare gli stack e utilizzare Heap per la gestione della memoria?

14

Mi sembra che tutto ciò che può essere fatto con uno stack possa essere fatto con l'heap, ma non tutto ciò che può essere fatto con l'heap può essere fatto con lo stack. È corretto? Quindi, per ragioni di semplicità, e anche se perdiamo un po 'di prestazioni con determinati carichi di lavoro, non sarebbe meglio andare semplicemente con uno standard (cioè l'heap)?

Pensa al trade-off tra modularità e prestazioni. So che non è il modo migliore per descrivere questo scenario, ma in generale sembra che la semplicità della comprensione e del design possa essere un'opzione migliore anche se esiste un potenziale per prestazioni migliori.

    
posta Dark Templar 08.10.2011 - 23:02
fonte

11 risposte

30

Gli heap sono dannosi per l'allocazione e la deallocazione rapida della memoria. Se vuoi prendere molte piccole quantità di memoria per una durata limitata, un heap non è la scelta migliore. Uno stack, con il suo algoritmo di allocazione / deallocazione super-semplice, eccelle naturalmente a questo (ancor più se è incorporato nell'hardware), motivo per cui le persone lo usano per cose come passare argomenti a funzioni e memorizzare variabili locali - il più uno svantaggio importante è che ha uno spazio limitato, quindi conservare oggetti di grandi dimensioni o tentare di usarlo per oggetti a vita lunga è una pessima idea.

Rimuovere completamente lo stack per semplificare un linguaggio di programmazione è il modo sbagliato IMO - un approccio migliore sarebbe quello di astrarre le differenze, lasciare che il compilatore capisca quale tipo di memoria usare, mentre il programmatore mette insieme a costrutti di livello superiore che sono più vicini al modo in cui gli umani pensano - e in effetti, linguaggi di alto livello come C #, Java, Python ecc. fanno esattamente questo. Offrono una sintassi quasi identica per gli oggetti allocati su heap e le primitive allocate nello stack ('tipi di riferimento' vs. 'tipi di valore' in Lingo .NET), completamente trasparenti o con alcune differenze funzionali che è necessario comprendere per utilizzare la lingua correttamente (ma in realtà non è necessario sapere come funzionano uno stack e un heap internamente).

    
risposta data 09.10.2011 - 00:06
fonte
8

In poche parole, uno stack non è un po 'di prestazioni. È centinaia o migliaia di volte più veloce dell'heap. Inoltre, la maggior parte delle macchine moderne ha il supporto hardware per lo stack (come x86) e quella funzionalità hardware per es. lo stack delle chiamate non può essere rimosso.

    
risposta data 09.10.2011 - 01:00
fonte
8

No

L'area dello stack in C ++ è incredibilmente veloce in confronto. Mi permetto che nessun sviluppatore C ++ esperto sia disponibile a disabilitare tale funzionalità.

Con C ++ hai choice e hai il controllo. I progettisti non erano particolarmente propensi a introdurre funzionalità che aggiungessero tempo o spazio di esecuzione significativi.

Esercizio di quella scelta

Se vuoi creare una libreria o un programma che richiede che ogni oggetto sia assegnato dinamicamente, puoi farlo con C ++. Sarebbe eseguito in modo relativamente lento, ma potreste avere quella "modularità". Per il resto di noi, la modularità è sempre facoltativa, introdurla in base alle necessità perché entrambe sono necessarie per implementazioni valide / veloci.

Alternative

Ci sono altri linguaggi che richiedono che lo spazio di archiviazione per ogni oggetto venga creato nell'heap; è piuttosto lento, tale da compromettere i progetti (programmi del mondo reale) in un modo che è peggio che dover imparare entrambi (IMO).

Entrambi sono importanti e C ++ ti dà il potere di usare entrambi efficacemente per ogni scenario. Detto questo, la lingua C ++ potrebbe non essere l'ideale per il tuo progetto, se questi fattori nel tuo OP sono importanti per te (ad esempio, leggi su linguaggi di livello superiore).

    
risposta data 09.10.2011 - 00:27
fonte
6

Then for simplicity's sake, and even if we do lose a little amount of performance with certain workloads, couldn't it be better to just go with one standard (ie, the heap)?

In realtà è probabile che il risultato in termini di prestazioni sia considerevole!

Come altri hanno sottolineato, gli stack sono una struttura estremamente efficiente per la gestione dei dati che obbedisce alle regole LIFO (last in first out). L'allocazione di memoria / la liberazione nello stack di solito è solo una modifica di un registro sulla CPU. Cambiare un registro è quasi sempre una delle operazioni più veloci che un processore possa eseguire.

L'heap di solito è una struttura di dati abbastanza complessa e allocare / liberare memoria richiederà molte istruzioni per eseguire tutta la contabilità associata. Ancor peggio, nelle implementazioni comuni, ogni chiamata a lavorare con l'heap ha il potenziale di provocare una chiamata al sistema operativo. Le chiamate al sistema operativo richiedono molto tempo! Il programma in genere deve passare dalla modalità utente alla modalità kernel e ogni volta che ciò accade il sistema operativo può decidere che altri programmi hanno esigenze più urgenti e che il programma dovrà attendere.

    
risposta data 09.10.2011 - 00:46
fonte
5

Simula usava l'heap per tutto. Mettere tutto sull'heap induce sempre un ulteriore livello di riferimento per le variabili locali, e mette ulteriore pressione sul Garbage Collector (devi tenere in conto che i Garbage Collector veramente risucchiati allora). Questo è in parte il motivo per cui Bjarne ha inventato il C ++.

    
risposta data 08.10.2011 - 23:07
fonte
3

Le pile sono estremamente efficienti per i dati LIFO, come ad esempio i meta-dati associati alle chiamate di funzione. Lo stack sfrutta anche le caratteristiche intrinseche del design della CPU. Dato che le prestazioni a questo livello sono fondamentali per quasi tutto il resto in un processo, prendere quel colpo "piccolo" a quel livello si propagherà molto ampiamente. Inoltre, la memoria heap è mobile dal sistema operativo, che sarebbe letale per gli stack. Mentre uno stack può essere implementato nell'heap, è necessario un sovraccarico che influirà letteralmente su ogni parte di un processo al livello più granulare.

    
risposta data 09.10.2011 - 00:09
fonte
2

"efficiente" in termini di scrittura del codice, forse, ma certamente non in termini di efficienza del software. Le allocazioni di stack sono essenzialmente gratuite (bastano poche istruzioni per spostare il puntatore dello stack e riservare spazio nello stack per le variabili locali).

Poiché l'allocazione dello stack non richiede quasi tempo, un'allocazione anche su un heap molto efficiente sarà 100k (se non 1M +) di volte più lento.

Ora immagina quante variabili locali e altre strutture di dati utilizzano un'applicazione tipica. Ogni singolo piccolo "i" che usi come contatore di loop viene assegnato un milione di volte più lentamente.

Se l'hardware è abbastanza veloce, è possibile scrivere un'applicazione che utilizza solo l'heap. Ma ora immagina quale tipo di applicazione potresti scrivere se hai sfruttato l'heap e utilizzato lo stesso hardware.

    
risposta data 09.10.2011 - 00:02
fonte
2

Potresti avere un interesse in "Garbage Collection è veloce, ma uno stack è più veloce".

link

Se l'ho letto correttamente, questi ragazzi hanno modificato un compilatore C per allocare "stack frames" nell'heap e quindi utilizzare garbage collection per de-allocare i frame invece di fare scoppiare lo stack.

Gli "stack frames" allocati allo stack superano in modo decisivo gli "stack frames" allocati all'heap.

    
risposta data 09.10.2011 - 05:13
fonte
1

Come funziona lo stack delle chiamate su un heap? Essenzialmente, dovresti allocare una pila nell'heap in ogni programma, quindi perché non fare l'hardware OS + per te?

Se vuoi che le cose siano davvero semplici ed efficienti, dai semplicemente un po 'di memoria all'utente e lascia che si occupino di esso. Certo, nessuno vuole implementare tutto da solo ed è per questo che abbiamo uno stack e un mucchio.

    
risposta data 09.10.2011 - 00:09
fonte
1

Sono richiesti sia lo stack sia l'heap. Sono utilizzati in diverse situazioni, ad esempio:

  1. L'allocazione degli heap ha una limitazione a sizeof (a [0]) == sizeof (a [1])
  2. L'allocazione dello stack ha una limitazione che sizeof (a) è costante in fase di compilazione
  3. L'allocazione dell'heap può fare loop, grafici ecc. strutture di dati complesse
  4. L'allocazione dello stack può eseguire alberi di dimensioni in fase di compilazione
  5. Heap richiede il monitoraggio della proprietà
  6. L'allocazione e deallocazione dello stack è automatica
  7. La memoria heap può essere facilmente trasferita da un ambito a un altro tramite i puntatori
  8. memoria stack è locale per ogni funzione e gli oggetti devono essere spostati portata superiore a prolungare la durata (o memorizzati all'interno di oggetti invece di funzioni membro all'interno)
  9. L'accumulo è negativo per le prestazioni
  10. Lo stack è abbastanza veloce
  11. Gli oggetti heap vengono restituiti dalle funzioni tramite puntatori che diventano proprietari. O shared_ptrs.
  12. Gli oggetti stack vengono restituiti dalle funzioni tramite riferimenti che non ne assumono la proprietà.
  13. L'heap richiede la corrispondenza di ogni nuovo con il tipo corretto di eliminazione o eliminazione []
  14. Gli oggetti stack utilizzano elenchi di inizializzazione RAII e costruttore
  15. Gli oggetti heap possono essere inizializzati in qualsiasi punto all'interno di una funzione e non possono utilizzare i parametri del costruttore
  16. Gli oggetti stack utilizzano i parametri del costruttore per l'inizializzazione
  17. Heap usa matrici e le dimensioni dell'array possono cambiare in runtime
  18. Lo stack è per singoli oggetti e la dimensione è fissa in fase di compilazione

Fondamentalmente, i meccanismi non possono essere confrontati perché molti dettagli sono diversi. L'unica cosa comune con loro è che entrambi gestiscono la memoria in qualche modo.

    
risposta data 09.10.2011 - 01:07
fonte
1

I computer moderni hanno diversi livelli di memoria cache oltre a un grande, ma lento, sistema di memoria principale. Si possono fare dozzine di accessi alla memoria cache più veloce nel tempo necessario per leggere o scrivere un byte dal sistema di memoria principale. Pertanto, l'accesso a una posizione migliaia di volte è molto più rapido rispetto all'accesso a 1.000 (o addirittura 100) posizioni indipendenti una volta ciascuna. Poiché la maggior parte delle applicazioni assegna e rilascia deallocate piccole quantità di memoria in cima allo stack, le posizioni in cima allo stack vengono utilizzate e riutilizzate in quantità enormi, ad esempio nella stragrande maggioranza (99% + in un'applicazione tipica) degli accessi allo stack possono essere gestiti utilizzando la memoria cache.

Al contrario, se un'applicazione dovesse creare e abbandonare ripetutamente oggetti heap per archiviare le informazioni di continuazione, ogni versione di ogni oggetto stack che sia stato creato dovrebbe essere scritta nella memoria principale. Anche se la maggior parte di tali oggetti sarebbe completamente inutile dal momento in cui la CPU voleva riciclare le pagine della cache in cui erano state avviate, la CPU non avrebbe avuto modo di saperlo. Di conseguenza, la CPU dovrebbe sprecare un sacco di tempo per eseguire scritture di memoria lente di informazioni inutili. Non esattamente una ricetta per la velocità.

Un'altra cosa da considerare è che in molti casi è utile sapere che un riferimento a un oggetto passato a una routine non verrà utilizzato una volta che la routine si chiude. Se i parametri e le variabili locali vengono passati tramite lo stack e se l'ispezione del codice della routine rivela che non persiste una copia del riferimento passato, il codice che chiama la routine può essere sicuro che se non ci sono riferimenti esterni al oggetto esisteva prima della chiamata, nessuno esiste in seguito. Al contrario, se i parametri venivano passati tramite oggetti heap, concetti come "dopo una routine restituisce" diventano un po 'più nebulosi, poiché se il codice mantenesse una copia della continuazione, sarebbe possibile che la routine "restituisse" più di una volta dopo un chiamata singola.

    
risposta data 27.10.2012 - 21:09
fonte

Leggi altre domande sui tag