¿Buena clase de matriz C++ para manejar grandes conjuntos de datos de una manera rápida y eficiente?

Question

Siguiendo a partir de previous question relating to heap usage restrictions, estoy buscando una buena clase estándar de C++ para tratar con grandes conjuntos de datos de una manera que sea eficiente desde el punto de vista de la memoria y eficiente en velocidad. Había estado asignando la matriz usando un solo Malloc/HealAlloc, pero después de múltiples intentos usando varias llamadas, seguí fallando por la fragmentación del montón. Así que la conclusión a la que he llegado, aparte de la conversión a 64 bits, es usar un mecanismo que me permita tener una matriz grande que abarca múltiples fragmentos de memoria más pequeños. No quiero una asignación por elemento, ya que es muy ineficiente en la memoria, por lo que el plan es escribir una clase que anule al operador [] y seleccione un elemento apropiado según el índice. ¿Ya hay una clase decente para hacer esto, o es mejor que haga lo mío?

Desde mi entendimiento, y algunos googling, un proceso de Windows de 32 bits debería ser teóricamente capaces dirección de hasta 2 GB. Ahora suponiendo que tengo 2GB instalados, y varios otros procesos y servicios están acaparando unos 400MB, ¿cuánta memoria utilizable cree que mi programa puede razonablemente esperar obtener del montón?

Actualmente estoy usando distintas versiones de Visual C++.

Editar Según el post de poita, he intentado un std :: deque , utilizando la siguiente prueba en VS2008;

#include <deque> 
using namespace std; 
struct V  
{ 
    double data[11]; 
}; 

struct T 
{ 
    long data[8];  
}; 


void dequeTest() 
{ 
    deque<V> VQ; 
    deque<T> TQ; 

    V defV; 
    T defT; 

    VQ.resize(4000000,defV); 
    TQ.resize(8000000,defT); 
} 

La memoria total para los datos anteriores sale a 608MB, Si yo utilizo malloc lineal o HeapAlloc, y toma < 1 segundo. El tamaño de deque tomó originalmente 950 MB, y luego comenzó a disminuir lentamente. 15 minutos más tarde, dequeTest() finalizó, utilizando solo 6MB de memoria para el proceso que probablemente tenía más que ver con los tiempos de ejecución. También traté de poblar la deque utilizando varias opciones de inserción, pero el rendimiento fue tan malo que tuve que salir temprano. Posiblemente podría proporcionar un mejor asignador que el defualt para obtener una mejor respuesta, pero a primera vista, deque no es la clase para este trabajo. Tenga en cuenta que esto también podría estar relacionado con la implementación de deque de MS VS2008, ya que parece haber mucho en esta clase que depende mucho de la implementación en lo que respecta al rendimiento.

tiempo para escribir mi propia clase de gran variedad, calculo.

Segunda edición: La asignación de cantidades más pequeñas arrojó 1.875GB inmediatamente usando lo siguiente;

#define TenMB 1024*1024*10 

void SmallerAllocs() 
{ 

    size_t Total = 0; 
    LPVOID p[200]; 
    for (int i = 0; i < 200; i++) 
    { 
     p[i] = malloc(TenMB); 
     if (p[i]) 
      Total += TenMB; else 
      break; 
    } 
    CString Msg; 
    Msg.Format("Allocated %0.3lfGB",Total/(1024.0*1024.0*1024.0)); 
    AfxMessageBox(Msg,MB_OK); 
} 

edición final he decidido aceptar el puesto de poita y los diversos comentarios que le sigue, no porque voy a utilizar directamente la clase deque, pero más por la matriz como una baraja de cartas noción en el comentarios que siguieron Esto debería ser sencillo de implementar con O (1) acceso aleatorio a elementos, basado en un número fijo de elementos por bloque, que es lo que necesito. ¡Gracias a todos por los comentarios!

Answer 1

¿Ha intentado utilizar un std::deque? A diferencia de std::vector, que usa una gran asignación de montón, deque generalmente asigna porciones pequeñas, pero aún proporciona la indexación de tiempo constante amortizada a través de operator[].

Answer 2

Desde el punto de vista de su programa siempre tiene 2 GB disponibles en el arranque, no importa lo que está pasando en el sistema. No creo que Windows proporcione una forma de detectar si tienes memoria en el disco o no. En lo que respecta a las estructuras de datos, parece que está describiendo algo similar a cómo se implementa un deque en el STL.

Answer 3

¿Qué tan escasa es esta matriz? Si hay grandes cantidades de espacio vacío (sin usar) en él, es posible que desee tomar otro enfoque. El answer to this question sugiere un mapa stl.

Si no es escaso (como se menciona en los comentarios), una cosa que puede considerar desde que está ejecutando en Windows es usar un memory-mapped file. Aunque su sistema operativo puede ser de 32 bits, su sistema de archivos no lo es. Esto, por supuesto, significa que habrá un intercambio continuo, que es bastante más lento que si pudieras poner todo en la memoria RAM.

Además, realmente debería considerar golpear la RAM del sistema hasta el máximo (3GB en Windows de 32 bits, creo) para ver si eso lo arregla para usted. Eso solo debería costarle alrededor de $ 100, y está gastando mucho más que eso en horas-hombre simplemente preocupándose por esto.

Answer 4

std :: deque hace exactamente lo que está describiendo, pero generalmente en la granularidad del tamaño de página del sistema operativo (es decir, los fragmentos que asigna son generalmente de 4 kB).

Si no está satisfecho con el rendimiento predeterminado de deque, es posible que pueda escribir un asignador personalizado que capture fragmentos más grandes, es decir, obtenga 1 MB o más a la vez.

Como han dicho otros, el espacio de direcciones virtuales de su proceso es completamente independiente de todos los demás procesos, por lo que puede abordar 2GB sin importar qué más esté sucediendo en su sistema. El SO cambiará sus páginas de memoria a/desde el disco según sea necesario para ajustarse a las limitaciones de la cantidad de memoria instalada y todos los procesos que compiten por ella. Esto ocurrirá en el tamaño de página de 4 kB, independientemente de cuán grandes sean sus fragmentos.