Costo dell'allocazione di memoria statica rispetto all'allocazione di memoria dinamica in C

Question

Sono molto interessato a sapere qual è il metodo preferito di allocazione di memoria static vs dynamic è buono per le prestazioni (ad esempio, tempo di esecuzione) quando si conosce il numero esatto di oggetti/elementi in C su Linux. Costo per un numero limitato di oggetti (piccola quantità di memoria) e per un numero elevato di oggetti (un'enorme quantità di memoria).

e.g., type A[N] vs type *A = malloc(sizeof(type) * N)

Per favore fatemi sapere. Grazie.

Nota: Possiamo eseguire il benchmark e probabilmente conosciamo la risposta. Ma mi piacerebbe conoscere i concetti che spiegano le differenze di prestazioni tra questi due metodi di allocazione.

Answer 1

L'allocazione statica sarà molto più veloce. L'allocazione statica può avvenire a livello globale e in pila.

Nell'ambito globale la memoria allocata staticamente è incorporata nell'immagine binaria. Questa è la dimensione totale della memoria richiesta, e dove deve essere localizzata nel binario in esecuzione è calcolata in fase di compilazione. Quindi, quando il programma carica il caricatore del sistema operativo, allocherà memoria sufficiente per tutti gli array statici globali. Sono abbastanza sicuro che accada in tempo costante per tutte le allocazioni. (ad esempio, più allocazioni non costano più tempo)

Nell'ambito locale, allocazioni statiche sono allocate nello stack. Ciò comporta semplicemente la prenotazione di un numero fisso di byte nello stack e avviene in un tempo costante per allocazione. Lo spazio dello stack è molto limitato.

La memoria dinamica deve essere allocata da un heap e, anche nel migliore dei casi, la maggior parte delle allocazioni richiederà un tempo maggiore di quello lineare con ciascuna allocazione, ad esempio n log n time o qualcosa del genere.

Inoltre, in pratica, l'allocazione dinamica sarà molto più lenta dell'allocazione statica.

@update: Come è stato sottolineato nei commenti seguenti: le allocazioni dello stack non sono allocazioni tecnicamente statiche (ma sono allocazioni con la forma sintattica utilizzata nella domanda dell'OP).

Anche quando si parla di "tempo di allocazione", sto considerando il tempo totale per gestire la memoria (alloc e gratuita).

In alcuni allocatori dinamici, il tempo di allocazione è più rapido del tempo di liberazione.

È anche vero che alcuni allocatori veloci scambiano l'efficienza della memoria per la velocità di allocazione. In questi casi, la staticità è ancora "migliore" in quella statica e gli stack allocs non sono rispettivamente tempo e tempo costante durante l'allocazione di blocchi di dimensioni esatte.

allocatori dinamiche essere veloce compromesso significativo l'efficienza della memoria (es allocatori compagno completano alla successiva potenza di due blocchi di dimensioni, come 33k alloc utilizzerà 64k)

Answer 2

memoria globale viene normalmente assegnato quando il programma (o shared module/dll) carica e pre-popolata con i suoi valori iniziali. Questo in genere ha una sua sezione di memoria.

Lo stack è un blocco (serie di pagine di memoria) di memoria allocata dal kernel quando si crea un nuovo thread. L'allocazione della memoria dello stack nello stack avviene tipicamente decrittando il puntatore dello stack (una istruzione macchina - (impila una discesa tipicamente completa - le allocazioni più recenti hanno indirizzi inferiori). Quando un oggetto stack viene cancellato, il puntatore dello stack viene incrementato).Le pile quindi hanno il primissimo rigore nell'ultima semantica. Anche lo stack ha dimensioni fisse, quindi quando si esaurisce si ottiene un overflow dello stack.

Quando si utilizza malloc (in C) o nuovo (C++), la memoria viene allocata nell'heap/free-store. Questo è un qualsiasi blocco di memoria numerica. Quando è necessaria più memoria di quella già allocata, malloc va nel kernel per richiedere più memoria dal sistema. Tipicamente malloc utilizzerà la memoria liberata già ottenuta dal sistema.

Le chiamate a malloc devono essere considerate lente e devono essere evitate per qualsiasi routine di prestazioni critica o in tempo reale. Questo è per 2 motivi.

1. L'heap deve allocare e liberare qualsiasi dimensione di memoria in qualsiasi ordine. Algoritmi più vecchi utilizzati per percorrere un elenco di blocchi liberati finché non è stata trovata una delle dimensioni appropriate. Dal momento che la memoria potrebbe essere molto frammentata, questo potrebbe potenzialmente essere lento. Se l'heap viene utilizzato su più thread, è necessario fornire una sorta di blocco. Sono state fatte molte ricerche per migliorare questa situazione e gli heap moderni di jemalloc e tcmalloc migliorano le cose. Tuttavia, non contare su questo.
2. Se la memoria richiesta non può essere allocata da ciò che è già gestito dall'heap allocator, l'allocatore dell'heap dovrà chiedere al kernel più memoria. (Su Unix questo viene fatto con le chiamate di sistema mmap o sbrk). Il kernel deve trovare alcune pagine di memoria non allocate e deve mappare queste pagine nello spazio di memoria dei processi). Qualsiasi forma di memorizzazione nella cache va fuori dalla finestra). Quindi aspettati che questo sia super slow (per un computer).

Quindi, se è necessario eseguire qualsiasi elaborazione critica, allocare tutta la memoria in primo piano e quindi riutilizzare la memoria già allocata. Assumi sempre le chiamate a malloc e il download sarà lento.

Answer 3

Se si sa esattamente quanto spazio è necessario mettere da parte e la vostra preoccupazione principale è la prestazione rispetto alla gestione della memoria e il codice non ha bisogno di essere ri-concorrente, allora si vuole allocare oggetti con durata di memorizzazione statica, dichiarandoli nell'ambito del file o utilizzando lo specificatore della classe di memoria static.

int data[SOME_NUMBER]; 

void foo(/* some list of parameters here */) 
{ 
    static int some_more_data[SOME_OTHER_NUMBER]; 
    ... 
} 

Sia data e some_more_data esistono per tutta la durata del programma, ma some_more_data è visibile solo all'interno della funzione foo .

In pratica, gli elementi con durata di archiviazione statica hanno spazio riservato per loro nell'immagine binaria stessa, in modo che la memoria sia disponibile non appena il programma viene caricato. Questo può avere un vantaggio per quanto riguarda la località; se i dati e il codice si trovano nella stessa pagina, non è necessario scambiare. Certo, dipende dal codice.

Lo svantaggio ovvio è che il file eseguibile avrà un ingombro maggiore. Un altro inconveniente è che il tuo codice non è re-entrant; ogni chiamata di foo sta funzionando sullo stesso blocco di memoria quando legge o scrive some_more_data. A seconda di cosa fa il tuo codice, potrebbe essere o non essere un grosso problema.

Se il codice deve essere rientranti, non è possibile utilizzare oggetti con durata di archiviazione statica. Se il blocco di dati è relativamente piccolo, utilizzare oggetti con durata di archiviazione automatica (ad esempio, variabili locali regolari).

void foo(/* some list of parameters here */) 
{ 
    int some_more_data[SOME_SMALLISH_NUMBER]; 
    ... 
} 

In questo caso, some_more_data esiste solo per la durata della funzione foo; ogni volta che si chiama foo, si assegna automaticamente un altro oggetto . Qualsiasi cosa ci sia in testa nel mettere da parte la memoria fa parte del sovraccarico di chiamare la funzione in primo luogo (almeno nella mia esperienza). Il puntatore allo stack viene comunque aggiustato indipendentemente dal fatto che si stiano utilizzando variabili locali oppure no, quindi l'uso di variabili locali non lo renderà più lento. Il problema principale è che la memoria disponibile per gli oggetti automatici è relativamente piccola; per gli oggetti sopra una certa dimensione, questo approccio semplicemente non funzionerà.

Se il codice deve essere rientrante e è necessario allocare grandi blocchi di memoria, sei praticamente bloccato con la gestione della memoria dinamica (malloc/calloc/realloc e free). A seconda di come si progetta il codice, è possibile ridurre alcuni dei problemi di prestazioni.

---

^{1. Le regole di visibilità vengono applicate durante la conversione dal codice sorgente al codice macchina; in realtà non si applicano in fase di esecuzione.}

Answer 4

allocazioni Veri statici (globali e locali variabili assegnati statico) sono incollati in sezioni e caricati insieme al resto della sezione in fase di carico (execve) utilizzando mmap. Sono essenzialmente gratuiti, già coperti dal costo del caricamento del programma.

Gli array automatici con dimensioni statiche note possono essere uniti insieme ad altre variabili locali e allocati regolando il puntatore dello stack. Si tratta essenzialmente di una sottrazione di interi (lo stack cresce verso il basso) o qualcosa simile a 1 ns sui processori moderni.

Le matrici di lunghezza variabile non possono essere incollate su altre variabili, quindi dovrebbero costare circa 1 ns ciascuna.

Ho provato misurazione malloc s con dimensioni diverse in un unico processo filettato e ho ottenuto questo, che implicherebbe malloc+free coppie costano circa 50-100 volte tanto come variabili di stack di assegnazione < 16MiB. Dopo di che, picchi verso l'alto (32MiB e 64MiB entrambi costo di circa un centinaio di volte tanto quanto le allocazioni < = 16MiB fare):

Questi sono solo i costi per ottenere il puntatore però. L'accesso effettivo può causare errori di pagina e quindi aumentare ulteriormente il costo del blocco di memoria. Gli errori di pagina dovrebbero essere estremamente rari con allocazioni di stack, ma probabilmente con accessi per la prima volta alla memoria allocata dinamicamente.

Inoltre, molte piccole allocazioni dinamiche metteranno a dura prova le cache in quanto la memoria sarà frammentata. (È possibile ridurre questa frammentazione utilizzando i pool di memoria, la propria o la funzionalità di ostacolo disponibile come parte di glibc.)