High memory requirement of adjacency_list

older
Release Candiate Download Location?

Pratyush

11 Apr 2006 11 Apr '06

8:23 a.m.

Hi, It seems that adjacency list takes up lot of memory than what I was expecting. Below is the code that I used for testing. int main() { typedef boost::adjacency_list<> graph_t; graph_t g(6045064); } The graph populated is taking about 190MB of memory, i.e., 32 bytes/vertex approx. I was expecting it to take 4 bytes/vertex. Am I doing something wrong? My intent is to use "vec_adj_list_impl" having no properties at all. Thanks & regards, Pratyush

Show replies by date

Douglas Gregor

11 Apr 11 Apr

5:11 p.m.

On Apr 11, 2006, at 4:23 AM, Pratyush wrote:

...

The graph populated is taking about 190MB of memory, i.e., 32 bytes/ vertex approx. I was expecting it to take 4 bytes/vertex.

That does sound high... are you using a 32- or 64-bit platform? Each vertex needs to store a vector, which is typically 3 pointers (12 or 24 bytes, depending on platform). We may be able to shrink the data structures a little more, but the adjacency list representation itself can only be compressed so far.

...

Am I doing something wrong? My intent is to use "vec_adj_list_impl" having no properties at all.

The next release of the Graph library will have the compressed_sparse_row_graph graph type, which requires much less memory than adjacency_list. Naturally, it's also less flexible. Doug

Sebastian Weber

5:46 p.m.

Hi!

...

The next release of the Graph library will have the compressed_sparse_row_graph graph type, which requires much less memory than adjacency_list. Naturally, it's also less flexible.

When will this stuff be released? What do you mean by less flexible and what graph sizes are manageable with this kind of graph on a 32-bit machine with sparse graph as <k>=3 ?? 1e8, 1e9 ?? Sorry for beeing so curious. But anyway: How does this compressed_sparse_row_graph thing work? Sebastian

...

Doug _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Douglas Gregor

6:23 p.m.

On Apr 11, 2006, at 1:46 PM, Sebastian Weber wrote:

...

Hi!

...
The next release of the Graph library will have the compressed_sparse_row_graph graph type, which requires much less memory than adjacency_list. Naturally, it's also less flexible.

When will this stuff be released?

It'll be a part of Boost 1.34.0. No solid date on when that will be released. Of course, you can grab the code straight out of Boost CVS.

...

What do you mean by less flexible

You need to order the edges by their source vertex when adding them, and at present it only supports directed graphs.

...

and what graph sizes are manageable with this kind of graph on a 32-bit machine with sparse graph as <k>=3 ?? 1e8, 1e9 ??

If you're okay with only storing 2B vertices but need > 2B edges, you can crunch a graph into 8 bytes per vertex and 4 bytes per edge. With < 2B edges, you can knock that down to 4 bytes per edge.

...

Sorry for beeing so curious. But anyway: How does this compressed_sparse_row_graph thing work?

There is some documentation about the actual format here: http://www.boost-consulting.com/boost/libs/graph/doc/ compressed_sparse_row.html Doug

Pratyush

12 Apr 12 Apr

9:01 a.m.

New subject: [Boost-users] High memory requirement of adjacency_list

...

...
The graph populated is taking about 190MB of memory, i.e., 32 bytes/ vertex approx. I was expecting it to take 4 bytes/vertex.

That does sound high... are you using a 32- or 64-bit platform? Each vertex needs to store a vector, which is typically 3 pointers (12 or 24 bytes, depending on platform).

I should have been specific about the machine that I was using. I used 64-bit platform. That explains 24 bytes out of 32 bytes. I am not clear about the remaining 8 bytes. It could be seen from the code that I posted, there are no edges in the graph at all - only vertices. The vectors used for storing the out edges should be empty. Maybe, instead of vecS as OutEdgeList, I should be using listS (or slistS) if number of out edges per vertex is less, say, 2 or 3.

...

The next release of the Graph library will have the compressed_sparse_row_graph graph type, which requires much less memory than adjacency_list. Naturally, it's also less flexible.

That's good news! I am eagerly looking for the next release. Thanks for your reply Doug. My doubts have been clarified. Regard, Pratyush

Doug Gregor

3:16 p.m.

On Apr 12, 2006, at 5:01 AM, Pratyush wrote:

...

...
...
The graph populated is taking about 190MB of memory, i.e., 32 bytes/ vertex approx. I was expecting it to take 4 bytes/vertex.

That does sound high... are you using a 32- or 64-bit platform? Each vertex needs to store a vector, which is typically 3 pointers (12 or 24 bytes, depending on platform).

I should have been specific about the machine that I was using. I used 64-bit platform. That explains 24 bytes out of 32 bytes. I am not clear about the remaining 8 bytes.

Neither am I. It's *possible* that the vector has some extra data in it (say, something for the allocator?) that is taking up the extra 8 bytes. What is sizeof(vector) on your platform?

...

Maybe, instead of vecS as OutEdgeList, I should be using listS (or slistS) if number of out edges per vertex is less, say, 2 or 3.

A list typically uses 2 pointers; I'm not sure about slist.

...

...
The next release of the Graph library will have the compressed_sparse_row_graph graph type, which requires much less memory than adjacency_list. Naturally, it's also less flexible.

That's good news! I am eagerly looking for the next release.

You can always grab the compressed_sparse_row.hpp header from Boost CVS. It isn't likely to change before the release, unless someone finds a problem with it. Doug

Pratyush

13 Apr 13 Apr

9:42 a.m.

New subject: [Boost-users] High memory requirement of adjacency_list

Doug Gregor writes:

...

On Apr 12, 2006, at 5:01 AM, Pratyush wrote:

...
...
...
The graph populated is taking about 190MB of memory, i.e., 32 bytes/ vertex approx. I was expecting it to take 4 bytes/vertex.

That does sound high... are you using a 32- or 64-bit platform?

I used 64-bit platform. That explains 24 bytes out of 32 bytes. I am not clear about the remaining 8 bytes.

Neither am I. <snip> What is sizeof(vector) on your platform?

It seems that the problem is with the STL implementation that ships with gcc. I am using 3.4.2 version. Even though sizeof operator gives the correct result, valgrind (or memusage) shows that somewhere extra bytes are eaten up whenever I use vector >. I will file a bug report with gcc.

...

...
...
The next release of the Graph library will have the compressed_sparse_row_graph graph type, which requires much less memory than adjacency_list.

That's good news! I am eagerly looking for the next release.

You can always grab the compressed_sparse_row.hpp header from Boost CVS. It isn't likely to change before the release, unless someone finds a problem with it.

I checked it out! I will have to write a routine to read the graph in sorted order from a file. Anyways, thanks a lot for your support. Regards, Pratyush

Doug Gregor

4:05 p.m.

On Apr 13, 2006, at 5:42 AM, Pratyush wrote:

...

It seems that the problem is with the STL implementation that ships with gcc. I am using 3.4.2 version. Even though sizeof operator gives the correct result, valgrind (or memusage) shows that somewhere extra bytes are eaten up whenever I use vector >. I will file a bug report with gcc.

The extra bytes may be due to the alignment requirements of your platform. Doug

Greg Link

7:12 p.m.

New subject: Bivariate Interpolation Functions?

Fellow Boost Users - I'm interested in doing bivariate interpolation (Shepard's, for example) in C++, and can't find a library with a suitable routine just yet. I've tried Matpack ( http://users.physik.tu-muenchen.de/ gammel/matpack/html/matpack_frame.html ), but found that their class, while seemingly functional, does quite a bit more smoothing than I'd like, and I can't seem to tweak it in any way to make it less aggressive in it's smoothing. Does anyone know of a library/source for a bivariate interpolation method other than Matpack? Boost's Math library seems fairly lightweight, so doesn't seem much help. I apologize if this seems a bit off-topic (as boost doesn't satisfy my need) but it's an interesting library question, so I'm hoping it's not too offensive. Any reommendations as to other lists that might be better suited (and their sign-up URL/info) are also appreciated. - Greg Link

6963

Age (days ago)

6965

Last active (days ago)

List overview

Download

8 comments

5 participants

participants (5)

Doug Gregor
Douglas Gregor
Greg Link
Pratyush
Sebastian Weber