¿Contenedor de acceso aleatorio que no cabe en la memoria?

Question

Tengo una matriz de objetos (por ejemplo, imágenes), que es demasiado grande para caber en la memoria (por ejemplo, 40 GB). Pero mi código necesita poder acceder aleatoriamente a estos objetos en tiempo de ejecución.

¿Cuál es la mejor manera de hacerlo?

Desde el punto de vista de mi código, no debería importar, por supuesto, si algunos de los datos están en el disco o almacenados temporalmente en la memoria; debe tener acceso transparente:

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

Pero, ¿cómo debo implementar este contenedor? ¿Debería simplemente enviar las solicitudes a una base de datos? Si es así, ¿cuál sería la mejor opción? (Si es una base de datos, entonces debería ser gratuita y no demasiada complicación administrativa, ¿tal vez Berkeley DB o sqlite?)

¿Debo implementarlo yo mismo, memorizando objetos después del acceso y purgando la memoria cuando está llena? ¿O hay buenas bibliotecas (C++) para esto por ahí?

Los requisitos para el contenedor serían que minimiza el acceso al disco (algunos elementos pueden ser accedidos con más frecuencia por mi código, por lo que deben mantenerse en la memoria) y permite un acceso rápido.

ACTUALIZACIÓN: que resulta que STXXL no funciona para mi problema porque los objetos guardo en el contenedor tienen un tamaño dinámico, es decir, el código puede actualizarlos (aumentando o disminuyendo el tamaño de algunos objetos) en tiempo de ejecución. Pero STXXL no puede manejar eso:

contenedores STXXL asumen que los datos tipos que almacenan los datos son llanura de edad tipos (POD). http://algo2.iti.kit.edu/dementiev/stxxl/report/node8.html

¿Podría comentar sobre otras soluciones? ¿Qué tal usar una base de datos? ¿Y cuál?

Answer 1

Podrías buscar en la memoria los archivos mapeados, y luego acceder a uno de esos también.

Answer 2

Considere el uso de la STXXL:

El núcleo de STXXL es una implementación de la biblioteca de C++ plantilla estándar STL para la memoria externa (fuera de núcleo) cálculos, es decir, STXXL implementa contenedores y algoritmos que pueden procesar grandes volúmenes de datos que solo caben en los discos. Si bien la compatibilidad con el STL admite la facilidad de uso y la compatibilidad con con las aplicaciones existentes , otra prioridad de diseño es de alto rendimiento.

Answer 3

Implementaré un caché básico. Con este tamaño de conjunto de tareas, obtendrá los mejores resultados con un conjunto de caché asociativo con líneas de caché de x bytes (x == lo que mejor se adapta a su patrón de acceso). Solo implemente en el software lo que todo procesador moderno ya tiene en el hardware. Esto debería darte los mejores resultados. Podría optimizarlo aún más si puede optimizar el patrón de acceso de alguna manera lineal.

Answer 4

Una solución es utilizar una estructura similar a un B-Tree, índices y "páginas" de matrices o vectores.El concepto es que el índice se usa para determinar qué página cargar en la memoria para acceder a su variable.

Si reduce el tamaño de la página, puede almacenar varias páginas en la memoria. Un sistema de almacenamiento en caché basado en la frecuencia de uso u otra regla reducirá el número de cargas de página.

Answer 5

He visto un código muy inteligente que sobrecarga operator[]() para realizar el acceso al disco sobre la marcha y cargar datos requeridos del disco/base de datos de forma transparente.