Come evitare la frammentazione dell'heap?

Question

Attualmente sto lavorando a un progetto per l'elaborazione di immagini mediche, che richiede un'enorme quantità di memoria. C'è qualcosa che posso fare per evitare la frammentazione dell'heap e per accelerare l'accesso ai dati delle immagini che sono già stati caricati in memoria?

L'applicazione è stata scritta in C ++ e funziona su Windows XP.

MODIFICA: L'applicazione esegue una preelaborazione con i dati dell'immagine, come la riformattazione, il calcolo di tabelle di ricerca, l'estrazione di immagini secondarie di interesse ... Durante l'elaborazione, l'applicazione richiede circa 2 GB di RAM, di cui circa 1,5 GB possono essere utilizzati per i dati di immagine.

Answer 1

Se si sta eseguendo l'elaborazione di immagini mediche, è probabile che si stiano allocando blocchi grandi alla volta (immagini 512x512, 2 byte per pixel). La frammentazione ti morde se alloca oggetti più piccoli tra le allocazioni dei buffer di immagine.

Scrivere un allocatore personalizzato non è necessariamente difficile per questo particolare caso d'uso. È possibile utilizzare l'allocatore C ++ standard per l'oggetto Image, ma per il buffer di pixel è possibile utilizzare l'allocazione personalizzata che è gestita all'interno dell'oggetto Image. Ecco uno schema rapido e sporco:

• Utilizza una matrice statica di strutture, ogni struttura ha:
  • Un solido pezzo di memoria che può contenere N immagini - il blocco aiuterà a controllare la frammentazione - prova una N iniziale di circa 5
  • Un array parallelo di bool che indica se l'immagine corrispondente è in uso
• Per allocare, cerca nell'array un buffer vuoto e imposta il suo flag
  • Se non ne viene trovato nessuno, aggiungere una nuova struttura alla fine dell'array
• Per deallocare, trovare il buffer corrispondente nell'array e cancellare il flag booleano

Questa è solo una semplice idea con molto spazio per le variazioni. Il trucco principale è evitare di liberare e riallocare i buffer di pixel dell'immagine.

Answer 2

Ci sono risposte, ma è difficile essere generali senza conoscere i dettagli del problema.

Suppongo che Windows XP a 32 bit.

Cerca di evitare di aver bisogno di centinaia di MB di memoria contigua, se sei sfortunato, alcune dll casuali si caricheranno in punti inconventi attraverso lo spazio degli indirizzi disponibile tagliando rapidamente aree molto grandi di memoria contigua. A seconda delle API di cui hai bisogno, questo può essere abbastanza difficile da prevenire. Può essere abbastanza sorprendente come l'allocazione di un paio di blocchi di memoria da 400 MB oltre a un utilizzo della memoria "normale" non possa lasciarti in nessun posto per allocare un blocco "piccolo" finale da 40 MB.

D'altra parte, preallocate blocchi di dimensioni ragionevoli alla volta. Dell'ordine di circa 10 MB è una buona dimensione del blocco di compromesso. Se riesci a dividere i tuoi dati in questo tipo di blocchi di dimensioni, sarai in grado di riempire lo spazio degli indirizzi in modo ragionevolmente efficiente.

Se stai ancora esaurendo lo spazio degli indirizzi, dovrai essere in grado di eseguire il page page in entrata e in uscita in base a una sorta di algoritmo di memorizzazione nella cache. La scelta dei blocchi giusti per il paging dipenderà molto dalla tua elaborazione algortihm e richiederà un'attenta analisi.

Scegliere dove cercare le cose è un'altra decisione. Potresti decidere di scriverli solo in file temporanei. È inoltre possibile esaminare l'API delle estensioni di Window Windowing di Microsoft. In entrambi i casi è necessario fare attenzione nella progettazione dell'applicazione per ripulire eventuali puntatori che puntano a qualcosa che sta per essere sfogliato, altrimenti accadranno cose davvero brutte (tm).

Buona fortuna!

Answer 3

Se stai per eseguire operazioni su una matrice di immagini di grandi dimensioni, potresti prendere in considerazione una tecnica chiamata "piastrellatura". L'idea è generalmente di caricare l'immagine in memoria in modo che lo stesso blocco contiguo di byte non contenga pixel in una riga, ma piuttosto di un quadrato nello spazio 2D. La logica alla base di ciò è che si farebbero più operazioni più vicine tra loro in 2D piuttosto che su una linea di scansione.

Ciò non ridurrà l'utilizzo della memoria, ma potrebbe avere un impatto enorme sullo scambio e sulle prestazioni della pagina.

Answer 4

Senza molte più informazioni sul problema (ad esempio la lingua), una cosa che puoi fare è evitare l'abbandono delle allocazioni riutilizzando le allocazioni e non allocare, operare e liberare. Allocatore come dlmalloc gestisce la frammentazione meglio degli heap di Win32.

Answer 5

Quello che colpirai qui è il limite dell'intervallo di indirizzi virtuali, che con Windows 32b ti dà al massimo 2 GB. Dovresti anche essere consapevole che l'utilizzo di un'API grafica come DirectX o OpenGL utilizzerà porzioni estese di quei 2 GB per frame buffer, texture e dati simili.

1,5-2 GB per un'applicazione a 32b è piuttosto difficile da ottenere. Il modo più elegante per farlo è utilizzare il sistema operativo 64b e l'applicazione 64b. Anche con il sistema operativo 64b e l'applicazione 32b questo può essere in qualche modo praticabile, purché si usi LARGE_ADDRESS_AWARE .

Tuttavia, poiché è necessario archiviare i dati delle immagini, è possibile aggirare il problema utilizzando Mappatura dei file come archivio di memoria - questo può essere fatto in modo da avere una memoria impegnata e accessibile, ma senza utilizzare alcun indirizzo virtuale .

Answer 6

Indovinare qui che intendevi evitare la frammentazione e non evitare la deframmentazione . Indovina anche che stai lavorando con un linguaggio non gestito (probabilmente c o C ++). Vorrei suggerire di allocare grandi blocchi di memoria e quindi servire allocazioni di heap dai blocchi di memoria allocati. Questo pool di memoria perché contiene grandi blocchi di memoria è meno soggetto alla frammentazione. Per riassumere, è necessario implementare un allocatore di memoria personalizzato.

Vedi alcune idee generali su questo qui .

Answer 7

Suppongo che tu stia usando qualcosa di non gestito, perché nelle piattaforme gestite il sistema (garbage collector) si occupa della frammentazione.

Per C / C ++ è possibile utilizzare un altro allocatore rispetto a quello predefinito. (c'erano alrady alcuni thread sugli allocatori su stackowerflow).

Inoltre, puoi creare la tua memoria dati. Ad esempio, nel progetto su cui sto attualmente lavorando, abbiamo un archivio personalizzato (pool) per bitmap (li archiviamo in un grosso pezzo di memoria contiguo), perché ne abbiamo molti e teniamo traccia dell'heap frammentazione e deframmenta quando la frammentazione è troppo grande.

Answer 8

Potrebbe essere necessario implementare la gestione manuale della memoria. I dati dell'immagine sono di lunga durata? In caso contrario, è possibile utilizzare il modello utilizzato dal server Web Apache: allocare grandi quantità di memoria e avvolgerle nei pool di memoria. Passare quei pool come ultimo argomento nelle funzioni, in modo che possano utilizzare il pool per soddisfare la necessità di allocare memoria temporanea. Una volta terminata la catena di chiamate, tutta la memoria nel pool non può più essere utilizzata, quindi è possibile strofinare l'area di memoria e riutilizzarla. Le allocazioni sono veloci, poiché significano solo aggiungere un valore a un puntatore. La deallocazione è molto veloce, poiché libererai blocchi di memoria molto grandi contemporaneamente.

Se l'applicazione è multithread, potrebbe essere necessario archiviare il pool nell'archiviazione locale thread, per evitare sovraccarico di comunicazione cross-thread.

Answer 9

Se riesci a isolare esattamente quei posti in cui è probabile che allochi blocchi di grandi dimensioni, puoi (su Windows) chiamare direttamente VirtualAlloc invece di passare attraverso il gestore della memoria. Ciò eviterà la frammentazione all'interno del normale gestore della memoria.

Questa è una soluzione semplice e non richiede l'utilizzo di un gestore di memoria personalizzato.