Re: [Boost-users] CSR graph and Dijkstra's to lower graph memory

On Mon, 8 Oct 2012, Jeremy Kawahara wrote:

Hello,

Sorry for such a late response - I was pulled to some other tasks. The suggestions to lower the needed memory helped immensely. Thank you :) I am wondering if there are still more optimizations I could look at to further lower the required memory.

A better description can be found below...

On Sun, Sep 23, 2012 at 12:29 PM, Leo Hidd wrote: and, since you are in a cluster, you could also try the distributed (parallel) version of SSSP. It will probably boost your running time.

Yes thanks! This is a good point. I might try this later once I get all the space issues sorted out.

  About your memory usage, let's see. You have ~580,000,000 edges, 2 fixed point of 4 bytes (vertex indices) plus one floating point of 8 bytes (edge cost) per edge, totalizing  ~9.3 GB. If your graph is undirected, but if you use a directed CSR, than you multiply this by 2 (to include both senses), totalizing  ~19GB. Now if your 35GB takes into account only the Boost graph size, it would seem a little too much, however if you also consider your own structure to load your information on RAM, it is just fine.

Sorry I made a bit of an error in my original calculations here. However I'm curious about your estimate of the amount of needed space.

It seems to me that we need to store the following arrays: (here I assume that the total number of vertices is less than 2^32 (4 bytes) but the total number of edges will likely be greater than 2^32 (8 bytes).

An "edge array" that stores the vertex indices. 2 vertices per edge at 4 bytes each

Usually (for the directed case where incoming edges aren't stored) there is only one vertex (the target) stored per edge.

An "edge cost" array the stores the cost at each edge. 1 edge cost per edge at 4 bytes (say we use a float) each

Yes.

These arguments are than passed to the CSR constructor. I THINK the CSR then sorts and copies these values into an internal structure (I'm basing this off the documentation which states that "The CSR format stores vertices and edges in separate arrays" - but perhaps I misunderstood it).

The CSR graph takes roughly (nvertices + 1) * sizeof(EdgeIndex) + nedges * sizeof(VertexIndex) bytes for a directed graph, excluding properties.

So I think we need to have enough memory to store the "edge array", the "edge cost array" AND the newly created CSR (the_number_of_edges x 4 bytes + the_number_of_nodes x 8 bytes) all at the same time.

Is my understanding of this correct?

Yes, except that you need another copy of the edge properties that are sorted along with the edges.

If so, I'm wondering if there is a way we can somehow lower this memory usage where we only store these structures once? I looked at using the "edges_are_unsorted_multi_pass" parameter but the memory differences did not seem to make a significant difference.

There is an in-place version (construct_inplace_from_sources_and_targets_t) that saves memory by requiring particular input layouts, but it is also slower. You should always use the _multi_pass version when you can since the other one does a copy of the data first. How much more memory are you looking to save? Are you hitting an out-of-memory condition on graphs above a certain size?

Le 23/09/2012 18:23, Jeremiah Willcock a écrit : If you know that you are going to have fewer than 2^32 vertices and/or 2^32 edges, you can also turn down the sizes of the integers used as indices in the graph's representation; see the documentation for details. On a 64-bit machine, they both default to 64 bits, but you can save a lot of storage by reducing their sizes.

Thanks! This did help quite a bit with the space requirements.

For the reference of others, I added the last "unsigned int" parameter to the call below since I expect the number of nodes to be less than 2^32 but the number of edges will likely be more.

typedef compressed_sparse_row_graph graph_t;

Yes, that is how you want to do it in that case. You might want to use uint32_t instead to get more control over the exact data size. -- Jeremiah Willcock