Struttura dati per memorizzare enormi quantità di dati?

Question

Nella mia applicazione, devo caricare volumedata dal set di immagini (immagini MRC) e mantenere i dati dei pixel in memoria (le immagini sono grigie, quindi un byte per pixel).

Il mio ambiente di sviluppo è QT framework, MinGW per Windows e GCC per Linux.

Al momento, io uso una semplice struttura di dati per memorizzare volumedata come:

unsigned char *volumeData; 

ed eseguire un'allocazione enorme come segue.

volumeData=new unsigned char[imageXsize * imageYsize * numofImages]; 

seguito sono i metodi importanti per accedere immagini-dati in uno stesso piano, come

unsigned char* getXYPlaneSlice(int z_value); 
unsigned char* getYZPlaneSlice(int x_value); 
unsigned char* getZXPlaneSlice(int y_value); 

Con la mia semplice struttura di dati era facile implementare metodi precedenti.

Ma potremmo aver bisogno di adottare le dimensioni del volume come 2000x2000x1000 (~ 3,7 Gb) in futuro. E l'attuale infrastruttura non sarà in grado di gestire tali enormi dati.

1. Come evitare la frammentazione? Ora, anche con dati 1000x1000x200, l'arresto anomalo dell'applicazione ha generato bad_alloc. Qual è il modo migliore per cambiare il datastructure per questo? devo usare qualcosa come lista collegata che ogni pezzo è di dimensione 100mb.

2. Inoltre, l'utente dovrebbe essere in grado di perfezionare alcuni filtri di elaborazione delle immagini sui dati del volume e dovrebbe anche essere in grado di ripristinare il valore originale del pixel. Ciò significa che dovrei conservare due copie di dati volume. Con l'attuale implementazione è come.

   char senza segno * volumeDataOriginale;

   char senza segno * volumeDataCurrent;

Quindi con 2000x2000x1000 intervallo di dati utilizzerà almeno 8 GB (4 GB per volume). Ma in Win32, lo spazio degli indirizzi è 4GB. Come affrontare questo? Dovrei andare con l'applicazione a 64 bit?

EDIT: Ecco un'istantanea della mia domanda

Fondamentalmente, caricare il volume-dati (dal set di immagini, da MRC format..etc) e visualizzarli in diversi piani-visualizzatori (XY , YX, YZ.Image mostra il visualizzatore del piano XY). Devo mantenere più di 3 metodi di accesso ai dati per mostrare un'immagine in un particolare piano. L'utente della barra di scorrimento può modificare l'immagine da mostrare nel piano selezionato)

Grazie in anticipo.

Answer 1

La soluzione più semplice al tuo problema sarebbe quella di utilizzare gli spazi degli indirizzi a 64 bit - i moderni Mac supportano questo fuori dalla scatola, su Windows e Linux è necessario installare la versione a 64 bit del sistema operativo. Credo che Qt possa essere usato per costruire app a 64 bit abbastanza bene. I sistemi a 32 bit non saranno in grado di supportare singole allocazioni della dimensione di cui parli - anche un Mac con 4 GB di spazio di indirizzamento disponibile per le applicazioni non sarà in grado di effettuare una singola allocazione di 3,7 GB in quanto non ci sarà essere uno spazio contiguo di quelle dimensioni disponibili.

Per undo vorrei guardare utilizzando file mappati in memoria e copy-on-write per copiare il blocco:

http://en.wikipedia.org/wiki/Copy-on-write

Questo significa che in realtà non hanno per copiare tutti i dati originali, il sistema eseguirà copie delle pagine così come sono scritte. Questo sarà di grande aiuto se le tue immagini sono molto più grandi della memoria reale e non cambierai ogni parte dell'immagine. Sembra che boost::map_file con accesso "privato" potrebbe essere utile per questo.

Se davvero, davvero bisogno di supportare i sistemi a 32 bit, l'unica alternativa è quella di rompere questi grandi blocchi in qualche modo, in genere in piani o sottolivelli. Entrambe sono orribili su cui lavorare quando si applicano filtri 3D, ecc., Quindi, se possibile, eviterei davvero questo.

Se si passa al percorso del volume secondario, un trucco consiste nel salvare tutti i sottolivelli in file mappati in memoria e mapparli nello spazio indirizzo solo quando sono necessari. Quando vengono decompressi dallo spazio indirizzo, devono rimanere nella cache del buffer unificata fino a quando non vengono eliminati, in pratica ciò significa che è possibile utilizzare più RAM dello spazio indirizzo (in particolare su Windows in cui le applicazioni a 32 bit ricevono solo 2 GB di spazio indirizzo per impostazione predefinita) .

Infine, su Windows a 32 bit è possibile anche guardare l'opzione/3GB in boot.ini. Ciò consente di allocare 3 GB di spazio di indirizzamento alle applicazioni anziché i normali 2 GB. Dal problema che descrivi non credo che questo ti darà abbastanza spazio per l'indirizzamento, tuttavia potrebbe aiutarti con alcuni volumi più piccoli. Notare che l'opzione/3GB può causare problemi con alcuni driver in quanto riduce la quantità di spazio di indirizzamento disponibile per il kernel.

Answer 2

64 bit è probabilmente il modo più semplice per gestire questo ... lasciare il sistema operativo guasto nelle pagine man mano che vengono utilizzate. Altrimenti, è difficile pensare molto senza conoscere i tuoi modelli di accesso attraverso i dati. Se si esegue regolarmente la scansione delle immagini per trovare il valore con le stesse coordinate pixel, è inutile parlare di avere puntatori a immagini che salvano e ricaricano su richiesta.

Per annullare i dati, è possibile mantenere una copia di backup completa come suggerito, oppure è possibile provare a eseguire un'operazione di annullamento che consideri le modifiche apportate ed è responsabile della ricerca di un'implementazione efficiente. Ad esempio, se hai appena capovolto i bit, allora non è distruttivo e hai solo bisogno di un funtore per la stessa operazione di bit-flip per annullare la modifica. Se l'impostazione di tutti i pixel con lo stesso tono era un'operazione comune (ad esempio riempimento, cancellazione), è possibile avere un valore booleano e un singolo pixel per codificare lo stato dell'immagine e utilizzare il buffer completo per gli annullamenti.

Answer 3

Penso che dovresti dare un'occhiata a hdf5. Questo è un formato binario per la memorizzazione di enormi quantità di dati raccolti da cose come telescopi, esperimenti di fisica e macchine di sequenziamento dei geni. I vantaggi dell'utilizzo di qualcosa di simile sono molti, ma tre pensieri immediati sono: (1) testato, (2) supporta la selezione di iperslab e (3) si ottiene la compressione gratuitamente.

Sono disponibili librerie C/C++, java, python, matlab.

Answer 4

Un'opzione che vorrei considerare è la mappatura della memoria, invece di mappare tutte le immagini, mantenere un elenco collegato di immagini che sono caricate pigramente. Mentre il filtro funziona attraverso l'elenco di immagini, caricare secondo necessità. Nella fase di caricamento, mappare un blocco anonimo (o di alcuni file temporanei fissi) della stessa dimensione e copiare l'immagine lì come backup. E mentre applichi i filtri, esegui il backup su questa copia. Come detto in precedenza da @Tony, 64-bit è la tua migliore opzione, e per i file mappati in memoria multipiattaforma, guarda all'interprocess boost.

Answer 5

È possibile utilizzare un file mappato in memoria per gestire dataset di grandi dimensioni con memoria limitata. Tuttavia, se le dimensioni del file saranno 4 GB, si consiglia di passare a 64 bit. Il progetto boost ha una buona libreria di mappatura della memoria multi-piattaforma che si avvicina molto a ciò che stai cercando.

http://en.wikipedia.org/wiki/Memory-mapped_file http://www.boost.org/doc/libs/1_44_0/libs/iostreams/doc/classes/mapped_file.html per iniziare. Alcuni esempi di codice qui sotto -

#include <boost/iostreams/device/mapped_file.hpp> 
boost::iostreams::mapped_file_source input_source; 
input_source.open(std::string(argv[1])); 
const char *data = input_source.data(); 
long size = input_source.size(); 
input_source.close(); 

Grazie, Nathan

Answer 6

si potrebbe utilizzare una struttura a due livelli: Un array di puntatori alle singole immagini o (molto meglio) un gruppo di immagini. Quindi è possibile conservare 20 immagini in un blocco di memoria e inserire i puntatori nei blocchi di 20 immagini nell'array. Questo è ancora veloce (rispetto a una lista concatenata) quando si effettua un accesso casuale.

È quindi possibile implementare un semplice algoritmo di paging: inizialmente tutti i puntatori dell'array sono NULL. Quando accedi per la prima volta a un blocco immagine, carichi le 20 immagini di quel blocco in memoria e scrivi il puntatore nell'array. Il prossimo accesso a quelle immagini non carica nulla.

Se la memoria si riduce perché sono stati caricati e caricati molti blocchi immagine, è possibile rimuovere il blocco immagine che è stato meno utilizzato (è necessario aggiungere un secondo campo accanto al puntatore dove si inserisce il valore di un contatore che fai il conto alla rovescia ogni volta che carichi un blocco immagine). Il blocco immagine con il contatore più basso è quello meno utilizzato e può essere rilasciato (la memoria viene riutilizzata per il nuovo blocco e il puntatore è impostato su NULL).

Answer 7

Dai un'occhiata allo SciDB.Non sono un esperto di esso, ma dalla sua sample use cases e a paper describing it, che consente di mappare naturalmente i dati in un 3D (+ 1D per il tempo/versioning) serie come questa:

CREATE ARRAY Pixels [ 
    x INT, 
    y INT, 
    z INT, 
    version INT 
] (
    pixel INT 
); 

E per implementare la query getXYPlaneSlice :

Slice (Pixels, z = 3, version = 1); 

per evitare la duplicazione dei dati quando solo una parte dei dati è cambiato, non è necessario compilare l'intera matrice per la versione 1 dal SciDB supporta array sparso. Quindi, quando è necessario caricare i dati più recenti, è possibile caricare con version = 0 per ottenere la versione precedente e aggiornare il risultato con un altro carico con version = 1.

Answer 8

Utilizzare STXXL: libreria di modelli standard per set di dati di grandi dimensioni.

ho sentito parlare su SO :)

Answer 9

La tendenza in questi giorni a lavorare con grande volume di dati è quello di rompere i dati fino in piccoli mattoni di dati di dire 64x64x64. Se si desidera eseguire il rendering del volume con l'illuminazione, si dovrebbe avere una sovrapposizione di 1 voxel tra i mattoni vicini in modo che i singoli mattoni possano essere resi senza l'uso di mattoni vicini. Se si desidera eseguire un'elaborazione dell'immagine più complessa con i mattoni, è possibile aumentare la sovrapposizione (a scapito dello spazio di archiviazione).

Il vantaggio di questo approccio è che è sufficiente caricare i mattoni necessari in memoria. Il tempo di rendering/elaborazione per un volume basato su brick non è significativamente più lento di un volume di base non in brick.

Per una discussione più approfondita di questo dal lato di rendering del volume, consultare i documenti su Octreemizer. Here is a link to one on citeseer.

Answer 10

Il problema principale è probabilmente se si desidera accesso casuale totale ai dati.

L'approccio migliore sarebbe quello di pensare alle algoritmi che si desidera utilizzare, e di essi non possono essere scritte che la falcata principalmente attraverso i dati in un solo una direzione. Ok, questo non è sempre possibile.

Se si vuole codificare una soluzione mezza peso te stesso, si dovrebbe fare in questo modo:

• uso mmap() per mappare fette della vostra struttura di dati nella memoria
• incapsulare i dati in un classe, in modo da poter accedere ai dati attualmente non mappati
• mmap() la regione richiesta su richiesta, quindi.

(In realtà, questo è ciò che il sistema operativo sta facendo in ogni caso, se si mmap() l'intero file in una sola volta, ma prendendo un po 'di controllo, si potrebbe rendere il on-demand algoritmo intelligente, nel corso del tempo e soddisfare i tuoi requisiti).

Ancora una volta, questo non è divertente se si salta su quei voxel immagine. L'algoritmo deve adattarsi all'accesso ai dati - per ogni soluzione scelta per memorizzare i dati.Totale Accesso casuale "interromperà" tutto, se i tuoi dati sono più grandi della tua memoria fisica.

Answer 11

Se hardware e sistema operativo lo consentono, andrei a 64 bit e mapperò il file in memoria (vedi CreateFileMapping su Windows e mmap su Linux).

Su Windows, è possibile visualizzare il file mappato che consente la copia su scrittura. Sono sicuro che puoi ottenere questa funzionalità anche su Linux. Ad ogni modo, se crei una vista di sola lettura sul file sorgente, questi saranno i tuoi "dati originali". Quindi crei una vista copy-on-write sul file sorgente: saranno i "dati correnti".

Quando si modificano i dati correnti, le pagine sottostanti modificate verranno copiate e allocate per l'utente e le pagine per i dati di origine rimarranno intatte. Se si accerta di non scrivere dati identici sui "dati attuali", si otterrà anche un utilizzo ottimale della memoria, poiché i dati correnti e i dati originali condivideranno le pagine di memoria. Devi prendere in considerazione l'allineamento della pagina, perché la copia su scrittura funziona sulla base della pagina.

Inoltre, il ripristino da dati correnti a dati originali è un lavoro semplice. Tutto ciò che devi fare è ricreare la mappatura per i "dati attuali".

Utilizzando la mappatura dei file, il faticoso lavoro di gestione della memoria verrà gestito dal sistema operativo. Sarà in grado di utilizzare tutta la memoria disponibile in modo molto efficiente. Molto più efficiente di quanto si possa mai fare con le normali allocazioni dell'heap.

Vorrei iniziare ricercando CreateFileView() e MapViewOfFile() per l'utilizzo su Windows. Per Linux hai mmap(), ma per quanto ne so io. Non ho toccato nulla * nix dal 2000 ...