reduciendo los requisitos de memoria para la lista de adyacencia

Question

Estoy usando adjacency_list < vecS, vecS, bidireccionales ...> ampliamente. Tengo tantos gráficos cargados a la vez que la memoria se convierte en un problema. Estoy haciendo un análisis de programa estático y almacenando el diagrama de call y los gráficos de flujo del binario desensamblado en los gráficos de impulso. Así puedo tener varias diez mil funciones == flowgraphs y un callgraph gigantesco. Realmente me gustaría reducir el uso de memoria para mis gráficos mientras sigo usando el BGL.

Dado que mis gráficos son estáticos después de la carga y los recuentos de flancos y vértices son conocidos de antemano, veo un gran potencial para la optimización. Para el ejemplo , me gustaría asignar un único búfer para todos los vértices/bordes de un solo gráfico y dejar que el gráfico simplemente almacene índices en ese búfer.

más preguntas:
1) ¿Cuál es la sobrecarga de memoria al usar las propiedades de vértice y borde? I tienen bastantes de ellos.
2) ¿es posible convencer al BGL de que use la contracción para ajustarse al idioma ? Según tengo entendido, las listas de adyacencia usan push_back para agregar bordes . ¿Es posible reducir el uso de memoria intercambiando el vector resultante con una copia de sí mismo? ¿Tal vez mediante la copia de todo el gráfico ?
3) ¿Es posible utilizar asignadores de grupo de impulso con BGL? Hasta ahora, ya que puedo decir que BGL actualmente realiza muchas asignaciones pequeñas - Realmente me gustaría evitar eso por razones de espacio y eficiencia de tiempo de ejecución.

¿Alguien ya ha creado una versión BGL optimizada para el uso de la memoria? ¿Debo intentar usar las estructuras de gráficos existentes y aumentarlo con asignadores personalizados o somesuch o es más fructífero escribir mi propia implementación y tratar de mantener la interfaz compatible con el BGL así que puedo seguir utilizando sus algoritmos?

mejores deseos,

Sören 

Answer 1

Hay un tipo de gráfico poco conocido llamado gráfico de "fila dispersa comprimida" en el BGL. Parece ser bastante nuevo y no está vinculado desde las páginas de índice. Sin embargo, emplea un hermoso pequeño truco para obtener la representación gráfica lo más pequeña posible. http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

Utilizando esto para algunos de nuestros gráficos, ya he podido reducir el uso total de la memoria en un 20%, por lo que es una optimización que realmente vale la pena.

También almacena las propiedades de vértice/borde en los vectores, proporcionando así la menor sobrecarga posible para esos también.

Tenga en cuenta que el envío de la versión con el último impulso 1.40 solo admite gráficos direccionales (en lugar de bidireccionales). Si necesitas poder iterar eficientemente sobre los bordes y bordes de un vértice (como yo lo hice), debes verificar el tronco de refuerzo desde la subversión. Jeremiah fue muy útil al agregar esa función en mi solicitud.

Answer 2

Desde BGL está diseñado para interoperate with legacy or custom graphs, usted es probablemente mejor fuera de la escritura de su propio gráfico.

Answer 3

1. La sobrecarga depende de la versión que esté utilizando y de si ha elegido propiedades "agrupadas" o no. Solo he usado propiedades empaquetadas y he leído el código. Esperaría que cada paquete de propiedades le cueste 2 punteros + tamaño del tipo de paquete que está utilizando + tamaño de cada una de las propiedades adjuntas. Ninguno de los conceptos que verifican las cosas queda en el afaik binario. Sin embargo, dado que tiene el código, ¿por qué no solo mide el costo? Si no tiene herramientas, intente generar gráficos de tamaños conocidos en almacenamientos intermedios de tamaños conocidos. Algo fallará eventualmente y en ese punto deberías tener conteos.

2. ¿Has intentado llamar al adjacency_list<blah>.swap(adjacency_list& x)? Espero que reduzca los contenedores de forma adecuada.

3. ???

empecé a escribir algo parecido al sistema que está describiendo, pero finalmente abandonó la BGL y cambió a la codificación de mis propios algoritmos para ejecutarse en una base de datos SQLite de todos los símbolos de engarce.

Answer 4

Como una respuesta a:

3) ¿Es posible utilizar los colocadores de la piscina impulso con la BGL? Por lo que puedo decir, BGL actualmente realiza muchas asignaciones pequeñas. Realmente me gustaría evitar eso por razones de espacio y eficiencia de tiempo de ejecución.

Código copiado de here:

template <class Allocator> 
    struct list_with_allocatorS { }; 

    namespace boost { 
    template <class Alloc, class ValueType> 
    struct container_gen<list_with_allocatorS<Alloc>, ValueType> 
    { 
     typedef typename Alloc::template rebind<ValueType>::other Allocator; 
     typedef std::list<ValueType, Allocator> type; 
    }; 
    } 

    // now you can define a graph using std::list 
    // and a specific allocator 
    typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;