Asignación de memoria dinámica basada en disco

Question

Tengo un programa en el que deseo poder almacenar ciertos datos (bloques asignados dinámicamente) en el disco para reducir el uso de memoria y la persistencia.

Mi primer pensamiento fue escribir mi propio asignador personalizado que administraba el contenido de los archivos en el disco, pero quiero ver qué alternativas hay también.

He examinado asignadores de memoria personalizados y temas sobre la serialización de objetos, pero existen diferencias sutiles, buenas y malas, al adaptar esos principios a la gestión del espacio de direcciones de un archivo.

En esta situación: se accede

1. memoria sólo a través de IO (lectura/escritura) funciones en lugar de directamente

2. se almacenan No hay objetos (métodos/punteros), sólo los datos.

3. El tamaño de un archivo no es estático, por lo que debe crecer cuando sea necesario en lugar de ser grande y estática

4. Para mis usos, es aceptable para volver a punteros existentes después de la desfragmentación

Debido a que los datos no son de un tamaño fijo, la mayoría de las implementaciones de bases de datos parecen no ser adecuadas.

Pregunto, ¿cuál es el mejor enfoque para este problema? ¿Debería implementar un simple asignador de memoria que trate un archivo como el montón?

Como referencia, estoy usando C++ en dispositivos integrados.

---

Editar: Implementé mi propio administrador de memoria que usa asignación de memoria de amigos y tamaños de bloque de potencias de dos. Estoy convencido de que es correcto y no se filtra, combina bloques libres y puede hacer una desfragmentación 'detener el mundo'.

El problema es que, como era de esperar, existe una gran fragmentación interna y externa. No soy un experto en este campo y aunque me parece fascinante (todavía soy un estudiante), me pregunto si hay otras implementaciones que hayan hecho lo mismo o algo similar. Seguramente no puedo ser el único?

---

Algunos temas útiles, pero hasta ahora incompatibles son:

mmap TBH que no he utilizado pero mmap lo que aborda el archivo IO, pero no la gestión del espacio de direcciones de archivos.

BOOST:serialization Tengo una (probablemente injustificada) renuencia a usar las bibliotecas de impulso en este momento.

STXXL dirección de memoria de tamaño variable de asignación interesante pero tampoco

Doug Lea Memory Allocator tiene muy buenas ideas sobre los problemas con los asignadores de memoria, pero no estoy en condiciones de tratar de hacer mi propia aplicación

Answer 1

Sus dos objetivos son reducir el uso de memoria y conservar sus datos. Eso definitivamente suena como un trabajo para una base de datos . Pero luego dices

Debido a que los datos no son de un tamaño fijo , la mayoría de las implementaciones de bases de datos no parece muy adecuado.

creo que usted estará interesado en este distinctive feature of SQLite (una base de datos multiplataforma muy ligero con el código fuente de dominio público):

registros de longitud variable

...

SQLite, por el contrario, usa solo la cantidad de espacio en disco realmente necesario para almacenar la información en una fila. Si almacena un solo carácter en una columna VARCHAR (100) , solo se consumirá un solo byte de espacio en disco. (En realidad dos bytes - hay cierta sobrecarga en el comienzo de cada columna para grabar su tipo de datos y longitud.)

También es un good choice for embedded development:

dispositivos y aplicaciones embebidas

Porque una base de datos SQLite requiere poca o ninguna administración, SQLite es a buena opción para dispositivos o servicios que deben funcionar sin supervisión y sin soporte humano. SQLite es una buena opción para su uso en teléfonos celulares, PDAs, decodificadores cajas y/o electrodomésticos. También funciona bien como una base de datos incrustada en aplicaciones de consumo descargables.

Answer 2

para dispositivos embebidos Ciertamente haría una implementación simple en lugar de usar una base de datos. El archivo directo IO evita algunos gastos generales de las bases de datos. Y los recursos a menudo son limitados en entornos integrados.

Su idea de escribir un asignador de memoria es probablemente la mejor manera. Debería proporcionar algún tipo de capa API que aísle la administración de memoria basada en archivos tanto como sea posible del resto de la aplicación. De esta forma, debería ser fácil cambiar (sin juego de palabras) para una implementación diferente más adelante y, por lo tanto, optimizar si surge la necesidad.

Answer 3

Definitivamente usaría mmap para la E/S. Esto haría que sea más fácil acceder directamente a los datos y descargarlos al disco cuando sea necesario. Lo único que tendría que controlar es dónde se asigna el archivo en el espacio de direcciones, para que pueda moverlo.

Una posibilidad para la administración de la memoria es crear un archivo diferente para cada objeto y usar la desfragmentación a nivel de sistema de archivos en lugar de implementarlo usted mismo. Nunca mencionó qué SO/sistema de archivos está usando, pero si ya tiene desfragmentación en línea, lo usaría. Si está utilizando Linux y puede usar XFS, puede usar xfs_fsr. Esperaría que la desfragmentación del sistema de archivos fuera altamente optimizada y requeriría mucho menos esfuerzo que implementarlo en un gran archivo.

Answer 4

Implementé mi propio administrador de memoria que utiliza la asignación de memoria de amigos y el tamaño de bloque de potencias de dos. Estoy satisfecho de que es correcto y no tiene fugas, fusiona bloques libres y puede hacer una desfragmentación 'detener el mundo'.

Es un gran primer paso. ¡Una vez que tenga un asignador de memoria personalizada que funcione, puede, por supuesto, hacerlo mejor!

El problema es que, como es de esperar, hay un poco de fragmentación interna (potencia de 2 bloques) y externa. No soy un experto en este campo y aunque me parece fascinante (todavía soy estudiante), me pregunto si hay otras implementaciones que hayan hecho lo mismo o algo similar. Seguramente no puedo ser el único?

El poder de dos es un enfoque genérico. Sin embargo, tenga en cuenta que esto puede no ser el mejor simplemente porque su patrón de asignación puede no seguir la misma progresión geométrica. En tal caso, es mejor probar todo lo que pueda y ver qué tamaños de bloques se asignan más y optimizar en consecuencia.

También me gustaría sugerir este es un maravilloso artículo de Andrei Alexandrescu y Emery Berger sobre el tema de asignación de memoria: Policy-Based Memory Allocation y el trabajo de este último en particular: The Hoard Memory Allocator.

Si es posible, revise las referencias mencionadas al final de ese artículo. También pueden proporcionar información adicional.

Answer 5

Según tengo entendido, necesita un sistema de archivos y no un sistema de asignación de memoria. Al principio, en los sistemas integrados la asignación dinámica de memoria en un disco es un término contradictorio. Un disco, ya sea un disco duro o un dispositivo flash, utilizado para el almacenamiento persistente es muy diferente a la memoria.No es solo la forma de acceder a ella, sino el hecho de que el almacenamiento en disco no es 100% confiable. Al escribir en un disco, debe tener un algoritmo para evitar sectores defectuosos. ¿Has pensado en esto o puedes considerar tu disco libre de fallas?

Un sistema de archivos se ocupará de la asignación de espacio y problemas de sectores defectuosos. FAT se usa generalmente en dispositivos integrados. Aunque el rendimiento de fragmentación de FAT es bastante pobre, esto no ha impedido su uso en muchos dispositivos integrados. La mayoría de los dispositivos basados ​​en flash realmente usan FAT.

De todos modos, sugiero comenzar con lo que tiene ahora: su sistema operativo (si usa alguno) y el controlador para su disco. Investigue si una solución adecuada ya es compatible con estos. También tenga en cuenta que los dispositivos integrados son más difíciles de depurar: si configura implementar sus propios algoritmos, se esperan tiempos de desarrollo más largos.

Answer 6

Creo que tendrías menos fragmentación interna con un simple heap allocator. Simplemente asigna la cantidad de memoria que realmente usa (más la sobrecarga para el encabezado). Si ya te has resignado a realizar una compactación de parada en el mundo, puedes combinar esto con una nueva asignación de arena, y asignar una nueva arena (más grande) y copiar todos tus bloques en vivo en la nueva arena.

Answer 7

Recientemente he codificado una clase de heap virtual para un problema de uso de memoria alto que tuve. El código se LGPL'ed y está alojada en code.google.com en:

http://code.google.com/p/kgui/source/browse/trunk/vheap.cpp

http://code.google.com/p/kgui/source/browse/trunk/vheap.h

Básicamente funciona de la siguiente manera:

1) Definir un tamaño de bloque y número de bloques para dejar en la memoria y un nombre de archivo para el almacenamiento en caché del sistema de archivos. En mi caso de uso tengo 200 bloques de 1MB en memoria en cualquier momento.

2) A continuación, llame a Asignar para reservar un trozo de "memoria virtual". Le devuelven un "mango" de 8 bytes a la memoria. Puede asignar trozos más grandes que el tamaño del bloque si lo desea.

3) Para escribir en el "montón virtual" hay una función de escritura donde se pasa el "identificador", el puntero a los datos y el tamaño de los datos.

4) Para leer desde el "montón virtual" hay una función de lectura donde se pasa el "identificador", el puntero al destino y el tamaño de los datos a leer.

El código maneja automáticamente el intercambio entre lo que está en la memoria y lo que está almacenado en el disco. Es bastante simple en realidad.

Answer 8

Su mejor opción sería key-value store rápido. La ventaja sobre RDBMS es que no necesitará todos los gastos generales de la base de datos.

Answer 9

Tome un vistazo a HDF5 http://www.hdfgroup.org/HDF5/whatishdf5.html

Esto debería servir a su propósito.

Answer 10

Voy a hacer eco kgiannakakis - lo que está describiendo es un sistema de archivos, no un sistema de administración de memoria.

Como todo su acceso es a través de las funciones de E/S, no es necesario que su objeto sea contiguo en el disco. En lugar de colocar cada objeto en un bloque de tamaño dinámico, divida el objeto en varios bloques de tamaño fijo. Los bloques se pueden ubicar en cualquier lugar, todo lo que necesita es una forma de vincularlos. Sus funciones de E/S se dividirán y aglutinarán los bloques según sea necesario.

Answer 11

Hmmh. Esto suena como un caso de uso muy común para BDB (Berkeley DB). Es una biblioteca eficiente de calidad de producción que realiza "bases de datos" persistentes con valores clave (~ = tablas con otros DB), código abierto y todo.

No creo que las DB relacionales (SQL) tengan mucho sentido, pero bdb et al (gnu db y estoy seguro de que hay otras) ciertamente sí.

Answer 12

Es posible que desee consultar las instalaciones provistas por Boost.Interprocess, en particular, consulte las instalaciones de archivos mapeados de memoria administrada.