High memory requirement of adjacency_list
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
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
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
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
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
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<some_user_defined_class_type>) 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
Doug Gregor <dgregor <at> cs.indiana.edu> 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<some_user_defined_class_type>) 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<vector<any_type> >. 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
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<vector<any_type> >. I will file a bug report with gcc.
The extra bytes may be due to the alignment requirements of your platform. Doug
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
participants (5)
-
Doug Gregor -
Douglas Gregor -
Greg Link -
Pratyush -
Sebastian Weber