Contenitore ad accesso casuale che non si adatta alla memoria?

Question

Ho una matrice di oggetti (ad esempio, immagini), che è troppo grande per adattarsi alla memoria (ad esempio 40 GB). Ma il mio codice deve essere in grado di accedere in modo casuale a questi oggetti in fase di runtime.

Qual è il modo migliore per farlo?

Dal punto di vista del mio codice, non dovrebbe essere importante, ovviamente, se alcuni dati sono presenti su disco o temporaneamente memorizzati in memoria; dovrebbe avere accesso trasparente:

container.getObject(1242)->process(); 
container.getObject(479431)->process(); 

Ma come devo implementare questo contenitore? Dovrebbe semplicemente inviare le richieste a un database? Se sì, quale sarebbe l'opzione migliore? (Se un database, quindi dovrebbe essere libero e non troppo fastidio amministrativo, forse Berkeley DB o sqlite?)

Devo solo implementarlo da solo, memoizing oggetti dopo aver scaricato la memoria quando è pieno? O ci sono buone librerie (C++) per questo là fuori?

I requisiti per il contenitore consistono nel minimizzare l'accesso al disco (alcuni elementi potrebbero essere utilizzati più frequentemente dal mio codice, quindi dovrebbero essere tenuti in memoria) e consentire un accesso rapido.

UPDATE: mi scopre che STXXL non funziona per il mio problema perché gli oggetti sono Conservare nel contenitore hanno dimensione dinamica, cioè il mio codice può aggiornarli (aumentando o diminuendo la dimensione di alcuni oggetti) in fase di esecuzione. Ma STXXL non può gestire che:

contenitori STXXL per scontato che i dati tipi che immagazzinano sono vecchi dati semplici tipi (POD). http://algo2.iti.kit.edu/dementiev/stxxl/report/node8.html

Potresti commentare altre soluzioni? Che ne dici di usare un database? E quale?

Answer 1

È possibile esaminare i file mappati in memoria e quindi accedere a uno di questi.

Answer 2

Considerare usando l'STXXL:

Il nucleo di STXXL è un'implementazione della libreria C++ modello standard STL per la memoria esterna (out-of-core) calcoli, cioè, STXXL implementa contenitori e gli algoritmi in grado di elaborare enormi volumi di dati che solo si adattano ai dischi. Mentre la compatibilità da a STL supporta la facilità d'uso e la compatibilità dello con le applicazioni esistenti, un'altra priorità di progettazione è ad alte prestazioni.

Answer 3

Vorrei implementare una cache di base. Con questa dimensione della workingset si otterranno i migliori risultati con una cache associativa-set con linee di cache x byte (x == che corrisponde meglio al proprio modello di accesso). Basta implementare nel software ciò che ogni processore moderno ha già nell'hardware. Questo dovrebbe darti imho i migliori risultati. Si potrebbe ottimizzare ulteriormente se è possibile ottimizzare l'accesspattern per essere in qualche modo lineare.

Answer 4

Una soluzione consiste nell'utilizzare una struttura simile a un B-Tree, indici e "pagine" di array o vettori.Il concetto è che l'indice viene utilizzato per determinare quale pagina caricare in memoria per accedere alla variabile.

Se si riduce la dimensione della pagina, è possibile memorizzare più pagine in memoria. Un sistema di memorizzazione nella cache basato sulla frequenza di utilizzo o altra regola ridurrà il numero di caricamenti della pagina.

Answer 5

Ho visto un codice molto intelligente che sovraccarica lo operator[]() per eseguire l'accesso al disco in tempo reale e caricare i dati richiesti dal disco/database in modo trasparente.