efficiente della memoria domanda di riassegnazione

StackOverflow https://stackoverflow.com/questions/3140517

Domanda

Diciamo che ho un programma (C ++, ad esempio) che alloca più oggetti, non più grandi di una determinata dimensione (chiamiamolo MAX_OBJECT_SIZE).

Ho anche una regione (lo chiamerò una "pagina") sul mucchio (assegnato con, diciamo, malloc (REGION_SIZE), dove REGION_SIZE> = MAX_OBJECT_SIZE).
Continuo a riservare uno spazio in quella pagina fino a quando lo spazio pieno è uguale PAGE_SIZE (o almeno si> PAGE_SIZE - MAX_OBJECT_SIZE).

Ora, voglio allocare più memoria. Ovviamente la mia "pagina" precedente non sarà sufficiente. Così ho almeno due opzioni:

  1. Usa realloc (pagina NEW_SIZE), dove NEW_SIZE> PAGE_SIZE;
  2. allocare una nuova "pagina" (pagina 2) e mettere il nuovo oggetto lì.

Se volevo avere un costume allocare funzione, quindi:

  1. Utilizzando il primo metodo, mi piacerebbe vedere quanto mi aveva riempito, e poi mettere il mio nuovo oggetto di lì (e aggiungere la dimensione dell'oggetto alla mia variabile di memoria piena).
  2. Uso il secondo metodo, avrei una lista (vettore? Array?) Di pagine, quindi cercare la pagina corrente, e quindi utilizzare un metodo simile a 1 per la pagina selezionata.

Alla fine, avrei bisogno di un metodo per liberare la memoria troppo, ma posso capire che una parte.

Quindi la mia domanda è: Qual è il modo più efficace per risolvere un problema come questo? E 'l'opzione 1, l'opzione 2 o qualche altra opzione non ho considerato qui? È un piccolo punto di riferimento necessaria / sufficiente per trarre conclusioni per situazioni del mondo reale? Capisco che le operazioni diverse possono eseguire in modo diverso, ma sto cercando una metrica generale.

È stato utile?

Soluzione

Nella mia esperienza l'opzione 2 è molto più facile lavorare con ha un overhead minimo. Realloc non garanzia che farà aumentare la dimensione della memoria esistente. E in pratica quasi mai fa. Se lo si utilizza è necessario tornare indietro e rimappare tutti i vecchi oggetti. Ciò richiederebbe che ti ricordi dove ogni oggetto assegnata era ... Che può essere una tonnellata sopra testa.

Ma è difficile qualificare "più efficiente" senza sapere esattamente cosa metriche che si usa.

Questo è il gestore della memoria che uso sempre. Si lavora per l'intera applicazione non solo un oggetto.

Allocati:

per ogni allocazione determinare la dimensione dell'oggetto allocato.

1 un'occhiata a un elenco di link di frees per gli oggetti di queste dimensioni per vedere se qualcosa è stato liberato in tal caso prendere la prima libera

2 cerchi in un tabella di ricerca e se non trovato

2.1 allocare una matrice di N oggetti della dimensione allocata.

3 ripristinare l'oggetto successivo libera della dimensione desiderata.

3.1 se la matrice è piena aggiungere una nuova pagina.

N oggetti può essere programmatore tunned. Se sai di avere oggetti un byte milioni 16 si potrebbe desiderare che N sia leggermente più alto.

oggetti oltre una certa dimensione X, non tenere un array semplicemente assegnare un nuovo oggetto.

FreeS:

determinare le dimensioni dell'oggetto, aggiungerlo alla lista link del frees.

se la dimensione dell'oggetto allocato è inferiore alla dimensione di un puntatore dell'elenco di collegamento non deve subire alcun overhead di memoria. è sufficiente utilizzare la memoria già allocata per memorizzare i nodi.

Il problema di questo metodo è la memoria non viene mai restituito al sistema operativo fino a quando l'applicazione è uscito o il programmatore decide di deframmentare la memoria. deframmentazione è un altro post. si può fare.

Altri suggerimenti

Non è chiaro dalla tua domanda il motivo per cui è necessario allocare un grande blocco di memoria in anticipo piuttosto che l'allocazione di memoria per ogni oggetto, se necessario. Sto assumendo che si sta utilizzando come un array contiguo. Altrimenti, sarebbe più senso malloc memoria di ogni oggetto in quanto è necessario.

Se è effettivamente agisce come un array, malloc-ing un altro blocco ti dà un altro pezzo di memoria che si deve accedere tramite un altro puntatore (nel tuo caso page2). Pertanto non è più il blocco contiguo è e non è possibile utilizzare i due blocchi come parte di un array.

realloc, invece, alloca un blocco di memoria contiguo. È possibile utilizzarlo come un unico array e fare ogni sorta di aritmetica dei puntatori non è possibile se non ci sono blocchi separati. realloc è utile anche quando si vuole realmente ridurre il blocco si sta lavorando, ma che probabilmente non è quello che si sta cercando di fare qui.

Quindi, se si utilizza questo come un array, realloc è fondamentalmente l'opzione migliore. In caso contrario, non c'è niente di sbagliato con malloc. In realtà, si potrebbe desiderare di utilizzare malloc per ogni oggetto creato, piuttosto che dover tenere traccia e micro-gestire blocchi di memoria.

Non hanno dato alcun dettaglio su quale piattaforma si stanno sperimentando. Ci sono alcune differenze di prestazioni per realloc tra Linux e Windows, per esempio.

A seconda della situazione, realloc potrebbe essere necessario assegnare un nuovo blocco di memoria se non può crescere a quello attuale e copiare la vecchia memoria a quello nuovo, che è costoso . Se non si ha realmente bisogno di un contiguo blocco di memoria si dovrebbe evitare di utilizzare realloc.

Il mio sugestion sarebbe quella di utilizzare il secondo approccio, o utilizzare un allocatore personalizzato (si potrebbe implementare un semplice compagno di allocatore [2] ).

Si potrebbe anche usare ripartitori di memoria più avanzate, come

Nel peggiore dei casi, l'opzione 1 potrebbe causare una "mossa" della memoria originale, che è un extrawork da fare. Se la memoria non viene spostato, in ogni caso la dimensione "extra" viene inizializzato, che è un altro lavoro troppo. Così realloc sarebbe stato "sconfitto" dal metodo malloc, ma per dire quanto, si dovrebbe fare i test (e penso che ci sia un pregiudizio su come il sistema è quando le richieste di memoria sono fatte).

A seconda di quante volte ci si aspetta il realloc / malloc deve essere eseguita, potrebbe essere un'idea utile o uno inutile. Vorrei usare comunque malloc.

La strategia libera dipende dall'implementazione. Per liberare tutte le pagine come complesso, è sufficiente "traverse" loro; invece di un array, userei collegato "pagine": add sizeof (void *) alla "pagina" dimensioni, ed è possibile utilizzare i byte in più per memorizzare il puntatore alla pagina seguente

.

Se si deve liberare un singolo oggetto, con sede in tutto una delle pagine, diventa un po 'più complessa. La mia idea è quella di mantenere una lista di non sequenziale libera / "slot" "block" (adatto per contenere qualsiasi oggetto). Quando si richiede un nuovo "blocco", in primo luogo si pop un valore da questa lista; se è vuota, allora si ottiene il prossimo "slot" in ultima pagina in uso, e, infine, una nuova pagina viene attivato. Liberare un oggetto, mezzi solo per mettere l'indirizzo slot vuoto in una pila / list (qualunque cosa si preferisce utilizzare).

In Linux (e probabilmente altri sistemi POSIX) c'è una terza possibilità, che è quella di utilizzare una memoria mappata regione con shm_open. Tale regione è inizializzato da zero una volta che vi si accede, ma le pagine AFAIK che mai l'accesso venire senza alcun costo, se non è solo l'indirizzo di gamma nella memoria virtuale di prenotare. Quindi, si può solo prenotare un grande pezzo della memoria all'inizio (più di quanto mai avrebbe bisogno) della vostra esecuzione e poi riempirla in modo incrementale sin dall'inizio.

  

Qual è il modo più efficace per risolvere un problema come questo? E 'l'opzione 1, l'opzione 2 o qualche altra opzione non ho considerato qui? È un piccolo punto di riferimento necessaria / sufficiente per trarre conclusioni per situazioni del mondo reale?

Option 1. Per essere efficace, NEW_SIZE deve dipendere vecchio formato non-lineare. In caso contrario, si rischia di incorrere in O (n ^ 2) le prestazioni di realloc () a causa della copia ridondante. Io in genere faccio new_size = old_size + old_size/4 (aumento del 25% per cento), come teoricamente migliore potrebbe new_size = old_size*2 in riserva caso peggiore troppa memoria inutilizzata.

Opzione 2. Dovrebbe essere più ottimale come la maggior parte moderne OSs (grazie a C ++ 's STL) sono già ben ottimizzato per la marea di piccole allocazioni di memoria. E piccole allocazioni hanno minore possibilità di frammentazione della memoria causa.

Alla fine tutto dipende quanto spesso si assegnano i nuovi oggetti e come si fa a gestire liberando. Se si alloca un sacco con 1 # si dovrebbe avere un po 'ridondante copia se in espansione, ma liberazione è morto semplice dal momento che tutti gli oggetti sono nella stessa pagina. Se si avrebbe bisogno di / libera il riutilizzo degli oggetti, con # 2 avrebbe trascorso qualche tempo a piedi attraverso la lista delle pagine.

Dalla mia esperienza # 2 è migliore, come lo spostamento blocchi di memoria intorno a grandi potrebbe aumentare il tasso di frammentazione mucchio. Il 2 # è anche permette di utilizzare i puntatori come oggetti non cambiano la loro posizione in memoria (anche se per alcune applicazioni preferisco coppie uso pool_id / indice invece di puntatori prime). Se a piedi attraverso le pagine diventa un problema più tardi, può essere troppo ottimizzato.

Alla fine si dovrebbe anche prendere in considerazione l'opzione # 3: libc. Credo che malloc di libc () è abbastanza efficiente per molti molti compiti. Si prega di provarlo prima di investire più del vostro tempo. A meno che non si sono bloccati su alcuni all'indietro * NIX, non ci dovrebbe essere alcun problema utilizzando malloc () per ogni oggetto piuttosto piccolo. Ho usato la gestione della memoria personalizzati solo quando ho avuto bisogno di mettere gli oggetti in luoghi esotici (ad esempio shm o mmap). Tenete a mente il multi-threading troppo: malloc () / realloc () / free () in genere sono già ottimizzato e MT-ready; si dovrebbe reimplementare le ottimizzazioni di nuovo a discussioni evitare di essere costantemente in collisione sulla gestione della memoria. E se si vuole avere pool di memoria o zone, ci sono già sacco di librerie anche per questo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top