reducir los requisitos de memoria para la lista de adyacencia

Question

Estoy usando adjacency_list extensamente. Tengo tantos gráficos cargados a la vez que la memoria se convierte en un problema. Estoy haciendo el programa de análisis estático y almacenar el callgraph y flowgraphs del binaria desmontado en los gráficos de impulso. De esta manera puedo tener varias funciones == diez mil y uno flowgraphs callgraph gigantesca. Realmente me gustaría reducir el uso de memoria para mi gráficos sin dejar de utilizar el BGL.

Desde mis gráficos son estáticos después de la carga y el borde y el recuento de vértices se sabe de antemano que veo un enorme potencial para la optimización. por ejemplo, me gustaría para asignar una única memoria intermedia para todos los vértices / bordes de un solo gráfico y dejar que la gráfica simplemente almacenar índices en ese búfer.

Más preguntas: Read 1) ¿cuál es la sobrecarga de la memoria de la utilización de propiedades de vértices y los bordes? yo tener un buen número de ellos.
2) ¿Es posible para convencer al BGL utilizar el encogimiento para caber ¿idioma? Como lo entiendo las listas de adyacencia utilizan para agregar push_back bordes. ¿Es posible reducir el uso de memoria mediante el canje de la vector resultante con una copia de sí mismo? Tal vez copiando el conjunto gráfica?
3) ¿Es posible utilizar los colocadores de la piscina impulso con la BGL? Tan lejos que puedo decir el BGL realiza actualmente una gran cantidad de pequeñas asignaciones - Realmente me gustaría evitar que por espacio de eficiencia y tiempo de ejecución razones.

¿Alguien ya construir una versión BGL optimizado para el uso de memoria? Debería tratar de usar las estructuras existentes y gráfico incrementarla con una asignadores personalizados o algo por el estilo o es más fructífera para escribir mi propia implementación y tratar de mantenerse interfaz compatible con el modo BGL Puedo seguir utilizando algoritmos es?

Saludos,

Sören

Answer 1

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

El uso de este para algunos de nuestros gráficos ya he sido capaz de reducir el uso total de memoria en un 20% - por lo que es una optimización que vale la pena en verdad

.

También almacena las propiedades vértice / borde en vectores dando así la sobrecarga más pequeña posible para aquellos también.

Tenga en cuenta que la versión incluida con el último impulso 1.40 sólo es compatible con los gráficos de dirección (en contraposición a bidireccional). Si tiene que ser capaz de recorrer más eficiente fuera de los bordes de un Vértice y en los bordes (como yo) que necesita para comprobar el tronco impulso de la subversión. Jeremías fue muy útil para añadir esa característica en mi solicitud.

Answer 2

1. La sobrecarga depende de la versión que está utilizando y si usted ha pasado por propiedades "paquetes" o no. Sólo he utilizado propiedades agrupadas ya la lectura del código que cabe esperar de cada manojo propiedad que cuesta 2 punteros + sizeof el tipo de paquete que está utilizando + sizeof cada una de las propiedades adjuntas. Ninguna de las cosas el concepto comprobación se deja en la que yo sepa binario. Ya que tienes el código, sin embargo, ¿por qué no medir el costo? Si usted no tiene ninguna herramientas para ayudar a tratar simplemente generando gráficos de tamaños conocidos en tampones de tamaños conocidos. Algo fallará finalmente y en ese punto se debe tener cuenta.

2. ¿Ha intentado llamar adjacency_list<blah>.swap(adjacency_list& x)? Yo espero que se reduciría los contenedores adecuadamente.

3. ???

empecé a escribir algo parecido al sistema que está describiendo, pero finalmente di por vencido en el 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 3

Desde BGL está diseñado para interoperar con el legado o gráficos personalizados , probablemente mejor fuera de la escritura de su propio gráfico.

Answer 4

Como una respuesta a:

  

3) ¿Es posible utilizar los colocadores de la piscina impulso con la BGL? Por lo que yo puedo decir la BGL realiza actualmente una gran cantidad de pequeñas asignaciones -. Me gustaría evitar que por espacio de eficiencia y tiempo de ejecución razones

aquí :

 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;