High memory requirement of adjacency_list

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

High memory requirement of adjacency_list

Pratyush-2
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

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: High memory requirement of adjacency_list

Doug Gregor

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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: High memory requirement of adjacency_list

Sebastian Weber
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
> [hidden email]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: High memory requirement of adjacency_list

Doug Gregor

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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: High memory requirement of adjacency_list

Pratyush-2
In reply to this post by Doug Gregor
> > 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


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: High memory requirement of adjacency_list

Doug Gregor-2

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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: High memory requirement of adjacency_list

Pratyush-2
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

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: High memory requirement of adjacency_list

Doug Gregor-2

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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Bivariate Interpolation Functions?

Greg Link
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
_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users