David Abrahams | 1 Feb 15:21 2003
Picon
Picon

Re: [BGL] Using BGL for huge graphs

Erik Arner <yg-boost-users <at> m.gmane.org> writes:

> My first thought is that it should be fairly straightforward: simply 
> construct classes that model Sequence or RandomAccessContainer for the 
> VertexList parameter etc. The classes store part of the data in memory 
> and read/write data to disc when necessary.
>
> Any pitfalls, gotchas or other stuff I should be aware of before 
> embarking on this?

Modelling Sequence or RandomAccessContainer correctly for data that is
not always in-memory is notoriously difficult.  Typically it requires
iterators which store their value_type internally, so dereferencing
returns an internal reference to the iterator itself.  The Boost
Iterator Adaptors library can be a help with constructing conforming
iterators (also notoriously difficult).  Of course, the BGL's use of
descriptors instead of heavy data may help get you around this problem.

You might consider whether the problem gets any easier if you don't
try to use adjacency_list, but instead model the Graph concept
yourself.  I've done that several times; it's not as hard as it might
seem.

HTH,
--

-- 
                       David Abrahams
   dave <at> boost-consulting.com * http://www.boost-consulting.com
Boost support, enhancements, training, and commercial distribution

Info: <http://www.boost.org>
(Continue reading)

Erik Arner | 3 Feb 11:21 2003
Picon

Re: [BGL] Using BGL for huge graphs


David Abrahams wrote:
> Erik Arner <yg-boost-users <at> m.gmane.org> writes:
> 
> Modelling Sequence or RandomAccessContainer correctly for data that is
> not always in-memory is notoriously difficult.  Typically it requires
> iterators which store their value_type internally, so dereferencing
> returns an internal reference to the iterator itself.

OK, as my knowledge regarding this is fairly limited, do you have any 
pointers to books or articles (on paper or on the web) that discuss this 
technique?

> The Boost
> Iterator Adaptors library can be a help with constructing conforming
> iterators (also notoriously difficult).

Point taken.

> Of course, the BGL's use of
> descriptors instead of heavy data may help get you around this problem.

If you have the time, please elaborate!

> You might consider whether the problem gets any easier if you don't
> try to use adjacency_list, but instead model the Graph concept
> yourself.  I've done that several times; it's not as hard as it might
> seem.

This certainly seems like a better solution than my original idea. Thanks!
(Continue reading)

Erik Arner | 3 Feb 11:11 2003
Picon

Re: [BGL] Using BGL for huge graphs


Chris Russell wrote:
> Erik, how huge is huge? Heap requirements in excess of 2^64 bytes huge? If
> so, that's one _massive_ graph and some supercomputer programmer will have
> to help. 

Well, 2^64 bytes is several orders of magnitude larger than I had in 
mind. I guess my graph would be something like 1000 GB tops. It's still 
a pretty massive graph though...

> If not, then why not leverage the full virtual memory space
> allocated to your process and let the OS worry about paging the data in/out
> of physical memory?

This is definitely an alternative, but my worry is that this solution 
might be much slower than it needs to be. When swapping back and forth, 
the OS doesn't really know what's going on, whereas I might have the 
knowledge of the order in which the different parts of the graph are 
processed etc.

Then again, maybe this argument is bogus and the OS actually is better 
at deciding what parts should be kept in memory for the moment.

> Seems like if you can fit into 2^32 (Xeon workstation)
> or 2^64 then an Itanium or Alpha (4-processor Alpha servers running DEC UNIX
> are real cheap on eBay these days) with a fiber channel drive array (striped
> config for maximum throughput) might do the trick? If this is even close to
> reasonable suggestion then you might check out the non-linear video editing
> guys for ideas on drive arrays (e.g. http://www.avid.com,
> http://www.media100.com).
(Continue reading)

charlie_zhang66 | 3 Feb 08:07 2003
Picon

using boost graph library in VC++

Hi,

I downloaded the boost graph library  and extract the zip file to 
root directory C:\boost_1_29_0 . I tried to use it to develope a 
project in VC++. I built the example file adj_list_cc.cpp, but the 
compiler give message "can not open boost/graph/graph_concepts.hpp".
Based on the installation on the website, I added 'c:/boost_1_29_0' 
to the #include<...> line. Then, I builted it again, the compiler 
said other library could not be opened. I want to know whether I 
should add 'c:/boost_1_29_0' to all the related #include<...>. Is 
there an easier way to use the library?

Thanks

Charlie

Info: <http://www.boost.org>
Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
Unsubscribe: <mailto:boost-users-unsubscribe <at> yahoogroups.com>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 

Amittai Aviram | 2 Feb 00:21 2003

More on static linkage

I have been trying to link the boost::regex library to a DLL (Release 
build) without success and I really need help.  I have learned 
something new.  Hitherto, I have put this line right above my code in 
one of my header files, i.e., within the "#if !defined()" block that 
prevents duplicate inclusion:

#define BOOST_REGEX_STATIC_LINK

This has no effect on the build whatsoever.  The resulting DLL is no 
bigger and the client will not work if you rename 
boost_regex_vc6_mdi.dll from its place.  You get an error message 
from the client saying that this file is missing.

If, however, I place the line above as the very first line in a 
header file, then, instead, I simply cannot compile and build the 
project at all.  The compile error I am getting states that there 
are "multiply defined symbols"!  I.e., the symbols defined in the 
library are being defined twice.  

This is driving me nuts.

Thanks for any help.

Amittai Aviram
amittai <at> amittai.com

Info: <http://www.boost.org>
Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
Unsubscribe: <mailto:boost-users-unsubscribe <at> yahoogroups.com>

(Continue reading)

Amittai Aviram | 1 Feb 02:45 2003

Re: Static linkage in VC++

--- In Boost-Users <at> yahoogroups.com, "John Maddock" 
<john_maddock <at> c...> wrote:
> > I am trying to get my DLL to get linked statically with the
> > boost::regex library and having _no success_.  I have tried 
putting
> > this line into one of the header files:
> >
> > #define BOOST_REGEX_STATIC_LINK
> 
> That will do the job, provided you don't want the regex code 
exposed from
> the dll.

Sorry!  Just wanted to add a piece of information to my previous 
reply (to the effect that, alas, no, this does _not_ work).  Both DLL 
and client are built as "Release" versions, using the "Multithreaded 
DLL" C Runtime Library (Projects->Settings->C/C++->Code Generation). 
I have no idea whether that might have any bearing, but I might as 
well try to mention everything I can think of.  Thanks.

Amittai

Info: <http://www.boost.org>
Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
Unsubscribe: <mailto:boost-users-unsubscribe <at> yahoogroups.com>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 

Amittai Aviram | 1 Feb 02:21 2003

Re: Static linkage in VC++

--- In Boost-Users <at> yahoogroups.com, "John Maddock" 
<john_maddock <at> c...> wrote:
> > I am trying to get my DLL to get linked statically with the
> > boost::regex library and having _no success_.  I have tried 
putting
> > this line into one of the header files:
> >
> > #define BOOST_REGEX_STATIC_LINK
> 
> That will do the job, provided you don't want the regex code 
exposed from
> the dll.

I'm afraid that it didn't do it.  I am working in Microsoft Visual 
C++ 6 and building the project as a "Release" build (as the 
documentation requires), but I still find that, if I then change the 
name of boost_regex_vc6_mdi.dll on my machine (to, 
say, "xboost_regex_vc6_mdi.dll"), I get a message box when running 
the DLL's client that says that that file is missing and must be 
installed.  Why isn't this working?  Is there anything else I need to 
attend to in the Projects->Settings options?  Should the .lib be 
listed among the include files in Projects->Settings or not?  
Anything else?  

I'd appreciate your help.  Thanks.

Amittai

Info: <http://www.boost.org>
Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
(Continue reading)

Chris Russell | 3 Feb 15:16 2003

Re: [BGL] Using BGL for huge graphs

Erik, your problem is interesting.

Erik wrote:
...
When swapping back and forth,
the OS doesn't really know what's going on, whereas I might have the
knowledge of the order in which the different parts of the graph are
processed etc.

Then again, maybe this argument is bogus and the OS actually is better
at deciding what parts should be kept in memory for the moment.

---

You hit on a key point - you do have some knowledge of your graph's
semantics and the algorithms you're running so you it's likely that you
_can_ make some assertions about what the memory access patterns are likely
to be. I'll let Dave step in elaborate further on exactly what he was
talking about but I think that generally speaking, if your runtime heap
requirements exceed physical memory, then ultimately you need to worry about
paging virtual memory to/from physical memory. This brings up an interesting
question: how best to minimize the paging? Several general truisms: when
you're executing your graph algorithm (regardless of if using BGL or your
own hand-coded graph abstraction) you want to work hard to get the memory
footprint of the algorithm aligned with a page boundary and hopefully small
enough to remain resident in the CPU's cache memory. Similarly, as your
algorithm processes data addressed in process virtual memory space, you
would like to minimize the frequency of cross paging boundaries. Now this
depends on your graph topology and algorithm - but I guess you have some
data about this. I think Dave was eluding to the fact that you might be able
(Continue reading)

Jeppe N. Madsen | 3 Feb 15:55 2003
Picon

Re: [BGL] Using BGL for huge graphs


>  
>  Chris Russell wrote:
> > Erik, how huge is huge? Heap requirements in excess of 2^64 bytes
> > huge? If so, that's one _massive_ graph and some supercomputer
> > programmer will have to help.
>  
>  Well, 2^64 bytes is several orders of magnitude larger than I had
>  in mind. I guess my graph would be something like 1000 GB
>  tops. It's still a pretty massive graph though...

I think the term you're looking for is "External-Memory Graph
Algorithms".....googling turns up some stuff which may be
interesting. Note that this is an active area of research so it
may not be easy to make these algorithms work with BGL....

 
> > If not, then why not leverage the full virtual memory space
> > allocated to your process and let the OS worry about paging the
> > data in/out of physical memory?
>  
>  This is definitely an alternative, but my worry is that this
>  solution might be much slower than it needs to be. When swapping
>  back and forth, the OS doesn't really know what's going on, whereas
>  I might have the knowledge of the order in which the different
>  parts of the graph are processed etc.

Letting the OS worry about paging is usually not a good idea if you
have some advance knowledge on how you'll use your data. Running times
can be decreased by several orders of magnitude by paying attention to
(Continue reading)

dlux42 | 3 Feb 16:52 2003
Picon

HP, aCC and the standards

Hello Guys!

I am now fighting with HP to recognize that their compiler is buggy. I
am one of their customer and would like to get help with this fight.

I want to use the boost.org format and regex libraries on HP-UX 11.00
with aCC, and I got contacted the local HP office about that.

I told that I want to use modern libraries like the "boost.org"
library. They answered that the HP aCC is the implementation of the
ISO/IEC 14882 standard of the C++ language.

They provided two links about the compiler:

http://www.software.hp.com/DTDC_products_list.html (follow the aC++ link).
http://docs.hp.com/hpux/onlinedocs/2213/libs.htm#slIntro
(introductionary concepts).

Do you have any evidence that the HP implementation of C++ language
breaks the standard and that's why the regex library and format
library does not compile on those platform? (if you need sample error
message, then I can send it to the list).

I am using stlport 4.5-119, aCC A.03.33.

Please Cc: the replies to my private email-address also.

Thanks for your help in advance,

dLux
(Continue reading)


Gmane