[SOLUCIONADO] Quien tiene mayor capacidad vector o list

[dmorill]

Hola amigos,

Tengo un algoritmo muy grande que guarda un arreglo de vector<vector<int>> el algoritmo me fallaba (en release) cuando hacía un push_back más (luego de hacer muchos otros claro) y me fije que el tamaño del vector era de más de 7 millones.

Entonces verifiqué la función max_size y era mucho más grande que 7 millones, por tanto pensé que el lío era que cuando superaba su capacidad el, como es vector, debe mudarse a otro sector de la memoria donde si alcance, pero no encontraba un bloque de memoria tan grande para alcanzar.

Por tanto dije vale usaré entonces las listas list<list<int>> que al ser listas enlazadas no necesitan mudarse a otro sector pues están desperdigados los elementos por toda la memoria, cual fue mi sorpresa de que no solo fallaba enlo mismo sino que el tamaño era de 1 millón algo, mucho menos que el vector (7 millones). Eso realmente no me lo esperaba. No se supone que la lista debería poder almacenar mucho más según esta lógica?

saludos

[eferion]

vector

La clase vector almacena todos los datos de forma secuencial. Esta mecánica hace que cada vez que se llene tenga que hacerse un realloc a una región más grande... con la penalización de rendimiento que conlleva copiar regiones grandes de memoria. Como toda la información está contenida en una única región de memoria, para gestionar los datos únicamente hacen falta tres variables:

• Un puntero que apunte al inicio de la región de memoria
• Un entero que indique el número máximo de elementos
• Un entero que indique la cantidad de posiciones ocupadas

Asumiendo que un entero y un puntero son 4 bytes, almacenar 1 millón de elementos de 4 bytes ocuparía: 1.000.000 * 4 + 3 * 4 = 4.000.012 bytes

list

La clase lista implementa una lista doblemente enlazada. En este caso añadir nuevos elementos supone un coste más o menos estable y constante de tiempo ya que no implica reallocs. La penalización de este contenedor la encontramos al acceder a un elemento aleatorio, ya que obliga a recorrer diferentes nodos para dar con el elemento en cuestión... en listas largas la penalización aumenta.

Una lista doblemente enlazada necesita dos punteros por cada elemento de la lista... uno apuntando al elemento anterior y otro al siguiente. Además necesitamos un puntero al primer nodo de la lista. Para almacenar un millón de elementos tenemos que: 3 * 4 * 1.000.000 + 4 = 12.000.004 bytes

¿De dónde sale ese 3? puntero al elemento anterior + puntero al elemento siguiente + el dato a almacenar = 3 * 4 bytes

Estos cálculos son a grandes rasgos, pero sirven para hacerse una idea de los requisitos de memoria.

¿Soluciones?

Lo más óptimo sería usar std::vector pero reservando la memoria previamente. De esta forma evitamos reallocs y nos aseguramos de disponer de la memoria necesaria para ejecutar nuestro algoritmo.

Para que el vector reserve memoria hay que llamar al método reserve(). Este método fuerza al vector a reservar memoria para almacenar, al menos la cantidad de elementos que le indiquemos.

Si no tenemos a priori ninguna certeza ni aproximación sobre cuáles van a ser los recursos de la aplicación puedes tener un problema. Piensa que al hacer reallocs el sistema operativo tiene que ser capaz de encontrar regiones de memoria cada vez más grandes...y eso puede ser un problema debido a que la memoria tiende a fragmentarse... usar listas enlazadas no es la solución debido a su mayor consumo de recursos.

Tienes una alternativa y es implementar un contenedor que gestione bloques de memoria... estaría a medio camino entre los dos contenedores de los que hablamos... la clase en cuestión reservaría la memoria en bloques de X elementos... cuando el bloque se llene reserva uno nuevo. Este diseño podría adaptarse mejor a los requisitos de tu aplicación... pero te tocaría implementarlo de 0 salvo que encuentres una implementación ya hecha.

Un saludo.

[dmorill]

Gracias, lo entiendo, pero en teoría el list puede almacenar más pues, si el vector no encuentra un bloque de memoria suficientemente grande no pude aumentar de tamaño. Pero las list pueden meterse en "huecos" en la memoria, no en bloques.

He hecho esta prueba, uso visualStudio 2013 por eso el tamaño del int es de 2147483647.

Código C++:

#include <iostream> 
#include <vector>
#include <list>
 
using namespace std;
 
 
int main(){
    int i,j;
    
    vector<int> vAux;
    for (i = 0; i < 50; i++)vAux.push_back(i);
    list<int> lAux;
    for (i = 0; i < 50; i++)lAux.push_back(i);
    i = 0;
    j = 111222000;  //max 2147483647;
    vector<vector<int>> v;
    cout << "max size: " << v.max_size() << endl;
    cout << "j.......: " << j << endl;
    cout << "i.......: " << i << endl;
 
    for (i = 0; i < j; i++){
        v.push_back(vAux); 
        if (i % 500000 == 0) cout << " i: " << i << endl;
        if (i > 7500000 && i % 100000==0) cout << " ii: " << v.size() << endl;
    }
    cout << i << endl;
 
    cin.sync();
    cin.get();
    return 0;
}
 

Y es muy raro, el maxi size (tengo 16 gigas de ram) es de 357.913.941 y el código falla cuando el vector tiene poco más de 7.900.000.

Otra cosa que no entiendo bien es porqué este resultado se altera si lo corro en debug, es decir falla a los 5 millones en debug no a los 7 millones como en release.

El problema no es que falte memoria creo, sino que el vector no aumenta más a pesar de que está dentro de sus capacidades.

Haciendo lo que me recomendó eferion hice esta prueba:

Código C++:

int main(){
    int i, j;
 
    vector<int> vAux;
    for (i = 0; i < 50; i++)vAux.push_back(i);
    list<int> lAux;
    for (i = 0; i < 50; i++)lAux.push_back(i);
    i = 0;
    j = 111222000;  //max 2147483647;
    vector<vector<int>> v;
    cout << "max size: " << v.max_size() << endl;
    cout << "j.......: " << j << endl;
    cout << "i.......: " << i << endl;
    v.reserve(j);
    for (i = 0; i < j; i++){
        v.push_back(vAux);
        if (i % 500000 == 0) cout << " i: " << i << endl;
        if (i > 7500000 && i % 100000 == 0) cout << " ii: " << v.size() << endl;
    }
    cout << i << endl;
 
    cin.sync();
    cin.get();
    return 0;
}
 

Y el problema es que el vector es lo suficientemente grande pero para mi sorpresa da el mismo error de bad_alloc at memory location a pocos más de 3.500.000 menos que antes.

Qué es lo que pasa, no tiene sentido. En todo esto el proceso sólo usa casi 2 gb de memoria ram, y mi windows usa más o menos 4 para un total de 6 de mis 16gb. No creo que el problema sea de memoria.

Saludos,

[eferion]

Iniciado por dmorill

Gracias, lo entiendo, pero en teoría el list puede almacenar más pues, si el vector no encuentra un bloque de memoria suficientemente grande no pude aumentar de tamaño. Pero las list pueden meterse en "huecos" en la memoria, no en bloques.

Sí, pero cada elemento de un list ocupa más que un elemento de vector... luego el consumo de memoria de un list siempre va a ser superior....

Iniciado por dmorill

He hecho esta prueba, uso visualStudio 2013 por eso el tamaño del int es de 2147483647.

Ya lo he comentado otras veces... usar los tipos nativos de C++ empieza a considerarse una práctica obsoleta por lo variable del rango de valores. La librería stdint tiene disponibles tipos de tamaño fijo independiente de la plataforma, lo cual garantiza un rango de valores fijo... algo extremadamente importane en muchísimos algoritmos.

Por cierto, como complemento a stdint, tienes a tu disposición inttypes, que te proporciona macros útiles para imprimir variables de rango fijo independientemente de la plataforma utilizada.

Iniciado por dmorill

Y es muy raro, el maxi size (tengo 16 gigas de ram) es de 357.913.941 y el código falla cuando el vector tiene poco más de 7.900.000.

¿Por qué es raro? Estás creando un vector de vectores. Estás creando 7.900.000 vectores y en cada vector almacenas 50 elementos. Si haces un sizeof de vector en mi caso da 12 bytes. A esto tienes que añadir la información RTTI que acompaña por defecto a cada clase de C++ (lo que permite que funcione dynamic_cast entre otras cosas y que no sale con sizeof, por lo que no se tendrá en cuenta en los cálculos pero que sepas que también está)

Con todo esto el consumo aproximado de memoria es:

Por cada vector: 12 + 50 * 4 = 212
En total: 7.900.000 * 212 = 1.674.800.000 bytes = 1.56 GB... como puedes ver el consumo no es despreciable. A eso tienes que añadirle que cuando v hace un realloc fuerza un realloc en cascada de todos los vectores almacenados en v, luego el consumo de memoria implicado en el realloc es considerable. Piensa que detrás de una simple acción puede desatarse una cadena de acontecimientos castastrófica.

Iniciado por dmorill

Otra cosa que no entiendo bien es porqué este resultado se altera si lo corro en debug, es decir falla a los 5 millones en debug no a los 7 millones como en release.

Esto es porque en debug se añaden marcas que facilitan la depuración del código... y esas marcas tienen la mala costumbre de ocupar recursos.

Iniciado por dmorill

El problema no es que falte memoria creo, sino que el vector no aumenta más a pesar de que está dentro de sus capacidades.

Iniciado por dmorill

Haciendo lo que me recomendó eferion hice esta prueba...

Y "sorprendentemente" falla antes. Lo único que has hecho con eso es que el vector principal acapare más memoria... más memoria consumida por el vector principal = menos cantidad de vectores secundarios... ¿sigues pensando que no es un problema de memoria?

La memoria tiende a fragmentarse... esto es, empieza a tener huecos. Cuanto más uso se le da a un equipo más fragmentada suele estar. Si resulta que el sistema operativo no es capaz de encontrar un hueco lo suficientemente grande como para ubicar la cantidad de memoria que se le pide, el proceso simplemente falla. Si tienes 16 GB de memoria bastan 15 bytes ocupando puntos estratégicos para que tu sistema operativo no sea capaz de reservar paquetes superiores a 1GB

[dmorill]

Iniciado por eferion

Y "sorprendentemente" falla antes. Lo único que has hecho con eso es que el vector principal acapare más memoria... más memoria consumida por el vector principal = menos cantidad de vectores secundarios... ¿sigues pensando que no es un problema de memoria?

La memoria tiende a fragmentarse... esto es, empieza a tener huecos. Cuanto más uso se le da a un equipo más fragmentada suele estar. Si resulta que el sistema operativo no es capaz de encontrar un hueco lo suficientemente grande como para ubicar la cantidad de memoria que se le pide, el proceso simplemente falla. Si tienes 16 GB de memoria bastan 15 bytes ocupando puntos estratégicos para que tu sistema operativo no sea capaz de reservar paquetes superiores a 1GB

Hola, según ésto si lo hago con listas (aunque ocupe más por elemento) debería poder llenar la lista hasta la capacidad de la ram, cierto? lo probé con el código de antes cambiándolo a list<list<int>> v;.

Código C++:

int main(){
    int i,j;
    
    vector<int> vAux;
    for (i = 0; i < 50; i++)vAux.push_back(i);
    list<int> lAux;
    for (i = 0; i < 50; i++)lAux.push_back(i);
    i = 0;
    j = 111222000;  //max 2147483647;
    list<list<int>> v;
    cout << "max size: " << v.max_size() << endl;
    cout << "j.......: " << j << endl;
    cout << "i.......: " << i << endl;
 
    for (i = 0; i < j; i++){
        v.push_back(lAux); 
        if (i % 500000 == 0) cout << " i: " << i << endl;
        //if (i > 7500000 && i % 100000==0) cout << " ii: " << v.size() << endl;
    }
    cout << "Presione cualquier tecla para salir..." << endl;
 
    cin.sync();
    cin.get();
    return 0;
}
 

Y si falló antes, lo que concuerda con lo que dices acerca de que usa más memoria, pero parece que los dos llegan a un "tope" o limite, y en el vector la respuesta es la que tu me dices, que la memoria se fragmenta y se llena de huecos, pero con el caso de las listas, porqué ocurre? ellas no necesitan bloques grandes de memoria.

Saludos,

[eferion]

Estás compilando la aplicación en modo 32 bits o 64???

32 bits limita la redirección a 2GB...

[xKuZz]

Varias aclaraciones extra:
1) max_size() te devuelve una supuesta capacidad máxima teórica basada en las especificaciones del sistema, lo único que puedes estar seguro es que si se alcanza ese número de elementos ese va a ser el máximo, pero lo normal es que mucho antes de alcanzarlos se produzca la excepción por falta de memoria, puesto que max_size no sabe los procesos que hay activos en el SO etc.

2) La memoria virtual está paginada (esto en realidad es un poco más complejo pero para que te hagas a la idea) si una página direcciona pongamos 1 KB de RAM y un proceso necesita 10 bytes de RAM al proceso se le asigna la página entera y los 1014 bytes restantes quedan desperdiciados. Esto ocurre si dicho proceso no puede ser retirado de memoria principal porque es un proceso del núcleo que no puede ser retirado o algo del estilo. Esta paginación es una de las cosas que producen la fragmentación.

3) Como te ha dicho eferion si trabajas con 32 bits el límite de ram disponible queda reducido considerablemente y si no me equivoco creo que son 2^32 direcciones = 4 GB

[dmorill]

Hola amigos, gracias de nuevo por su ayuda. En efecto la cuestión fue que estaba compilando en 32 bits, con 64 ya me funciona hasta que se llena mi memoria ram jeje