- Boost - lists.boost.org

[trac] New components
by Daniel James 12 May '10

12 May '10

Hi, Please can someone add functional/foward and functional/factory to the components on trac? They should be owned by t_schwinger. thanks, Daniel

2 1

IOChain Old Version
by Sebastian Redl 12 May '10

12 May '10

Hi, You can download the code of the old IOChain version here: http://www.cornedbee.com/iochain.tar.bz2 Sebastian

1 0

[Trac] Where's the SPAM?
by Rene Rivera 12 May '10

12 May '10

Since we've had a variety of SPAM that we have not been able to delete for some time it's likely that it's accumulated in Trac. So if you notice some of it during your trac reading, either delete it (assuming you have the permission) or post the link to the ticket so I can delete it. Delete happy, Rene :-) -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail

3 3

[Trac] We're getting spammed!
by John Maddock 12 May '10

12 May '10

The Trac ticket system seems to be getting spammed on a regular basis at the moment, here are *four* of my old tickets that just got hit today: https://svn.boost.org/trac/boost/ticket/3632 https://svn.boost.org/trac/boost/ticket/1648#comment:4 https://svn.boost.org/trac/boost/ticket/2445#comment:2 https://svn.boost.org/trac/boost/ticket/3425#comment:2 Is there anything we can do to prevent this? John.

3 9

"Is Boost Broken?". - post script
by Robert Ramey 12 May '10

12 May '10

Last night I gave my presentation "Is Boost Broken?". I just wanted to add a few observations now that I've had an opportunity to sleep on it. Those who are interested, can download the powerpoint presentation at http://www.rrsd.com/software_development/boost/BoostCon2010/index.htm . A large part of the content was really contained in the response from the participants which is not available. Someday there maybe a video in which you'll be able to appreciate my bombastic personal delivery. I was surprised at how positively the proposals presented were received. I had feared the worst but hoped that some of the ideas presented might worm their way into Boost. It seems that there was more interest than that. I had crafted my proposal after having spent a lot of time following the mailing lists and I believe that proposal reflects a lot of the concerns that others have raised in piecemeal fashion. So in retrospect maybe I should have been more optimistic. I was careful to keep the focus on what facilities I think Boost needs and not get too involved in what it would take to implement these ideas or the specific form they might take. But given the interest, I'm now thinking more seriously of what it would take to make the ideas in this proposal reality. I'm here at Boost Con 2010 if you want to help in some way with this. Also, tonight, Dave Abrahams is scheduled to present his project "ryppl". I'm not privy to any of the details, but I suspect that this might dovetail with my own presentation. It will very likely bring out more discussion on the future of Boost. Robert Ramey BoostCon 2010 Aspen, Colorado

5 6

BOOST_NO_EXTERN_TEMPLATE check is broken
by Doug Gregor 12 May '10

12 May '10

The current Boost.Config check for BOOST_NO_EXTERN_TEMPLATE uses incorrect syntax. The test, in libs/config/test/boost_no_extern_template.ipp, looks like this: namespace boost_no_extern_template { extern template<class T> void f(T); int test() { return 0; } } The "extern" in C++0x extern templates can only be placed on explicit template instantiations. Here's a better test: namespace boost_no_extern_template { template<typename T, typename U> void f(T* p1, U* p2) { p1 = p2; } extern template void f(int*, float*); int test() { return 0; } } If the compiler rejects or ignores the "extern" in that explicit template instantiation declaration, we'll get an (invalid) compiler error. Grepping through the compiler configurations, BOOST_NO_EXTERN_TEMPLATE is set for several compilers that do in fact have support for C++0x extern templates, namely GCC and EDG-based compilers (when in either in C++0x or non-strict mode). - Doug

2 1

[fusion] [mpl] associative containers, compile time performance
by Domagoj Saric 12 May '10

12 May '10

(Boost 1.42, MSVC++ 9.0 SP1) Recently, I was finally forced to do some serious refactoring because the 'unbareable' turned to 'not working at all' (read: the compiler was hitting the 32 bit limit with 'out of heap space' errors), I got from hundreds of thousands of template instantiations down to 'just' thousands in a particular TU [meassured with Steven Watanabe's profiler...Steven you do miracles ;-D ...I also managed to get the Templight profiler to work with MSVC++ 9.0 but it just crashed with a project like this one...], and a peak cl.exe allocation of about 0.5 GB with a clean rebuild taking under 2 minutes which is acceptable... In the process I found out that: - the Fusion associative containers are always slower than random access containers (even if you use them only for/with by-key access). For example, I have a Fusion vector of different 'parameter' classes (it is therefore a 'unique random access set') for which a I wish to genereate a container of corresponding widget classes. Considering I later need to access the widget container using a parameter type as a key ('give me the widget for this parameter') it seems logical to use a map ( of pair<Parameter, Widget>s) but as it turns out accessing this map is several times! slower (compile-time wise) than using a plain vector for the widgets and then doing a linear search on the original parameter container to find the index of the parameter and then accessing the widget vector using that index... - the MPL associative containers are faster than random access ones only if you use them solely for by-key access, if any sequential or indexed access (using begin+advance) is also used (even if 'minor' to the amount of by-key access) this immediately kills the compiler. The size of the container might have also played a part in the distinction...in the end what worked best for me was to use mpl::maps for smaller collections (less than 10 types) that are only accessed by key, and mpl::vectors for large collections (50 types) that need to be accessed by index and by key... If these things are somehow 'ancient knowledge' maybe it would be worthwhile to document them so...In fact the Fusion documentation for associative sequences actually states "An Associative Sequence allows efficient retrieval of elements based on keys..." while in my case this turned out quite the opposite of truth...maybe this was referening to runtime-efficiency but then again this should be more clearly stated in the documentation (especially considering that, given the compile time nature of Fusion, it is reasonable to apriori expect that there is no runtime/generated code difference between different Fusion containers with most half decent compilers)... Looking at the implementations of Fusion associative containers it can be seen that, in fact, they do use vectors for implementation and do linear searches... One more thing that might help with Fusion associative container related compile-time defficiencies is to add the non-variadic/fixed sized versions for sets and maps (e.g. I frequently have this information and could specify the size exactly instead of being forced to use the variadic versions)...Just specifying FUSION_MAX_SET_SIZE=10 instead of 20 provided a measurable compile-time improvement... Additionaly, fusion::joint_view lacks the vital at<>() implementation(s) even though it states it is a model of a forward sequence so one is forced to use begin+advance... As for MPL, it still lacks the implementation of at<Seq, Key, Default> (that would be of significant help for my case) even though it is documented for 'who knows how long'... Even more usefull would be if MPL associative containers would not only provide the order<> 'getter' but also allow access using the order value (with same efficiency as key-based access of course)...this is usefull when you need to 'export' your 'typelist' outside of your library/'DLL' and allow outside code to specify the type that it wishes to create using an ID (like a factory that takes an ID as a parameter)...without the ability to use the 'order' as the ID you are forced to use the index...which then forces you to use vectors (because indicies simply 'kill' the compiler when used with a set) even though you also need key-based access at other places... ps. What does BOOST_MPL_LIMIT_UNROLLING actually do/configure? :) -- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman

1 0

Interlibrary version cchecking
by Robert Ramey 12 May '10

12 May '10

Turns out that the idea of a single boost library deployment has come up a couple of times here at BoostCon 2010. While preparing my presentation I considered the problem of what would happen if one installed one library which depended on an newer version of a different library than the user already had installed. I actually woke up in the middle of the night imagining someone would ask about that during my talk. I puzzled about it for some time and the day before I found a way to address it - in my own mind at least. It also seems that it turns out that there are tools that can also manage this. It's not that I don't trust tools but I wear a belt AND suspenders. So I would like a method which guarentees that when I build one library, I don't accidently include code from a prerequisite library which is a version so old that things won't work. I would also like to know that I'm not accidently running with a DLL built with an old version. Basically each library includes a file "manifest.hpp". This get's included when any header get's includes (once at most due to include guards). This includes a static assert that checks that the prequiste libraries are of sufficiently recent version that a dependent library (or user application) requires. There is also a manifest.cpp file included in the library which checks any prequiste DLLS. This would be an exheedingly small overhead to avoid what could be an incredibly large headache. I just verified that the code compiles so at this point it's only an idea. But it seems that some kind of check like this is un-avoidable of one want's to deploy libraries as needed rather than as a monolithic distribution. FYI - no one asked me about this problem at my presentation. Add one more confirmation of Murphy's law. Robert Ramey begin 666 manifest.hpp M(VEF;F1E9B!"3T]35%]315))04Q)6D%424].7TU!3DE&15-47TA04 T*(V1E M9FEN92!"3T]35%]315))04Q)6D%424].7TU!3DE&15-47TA04 T*#0HO+R!- M4R!C;VUP871I8FQE(&-O;7!I;&5R<R!S=7!P;W)T("-P<F%G;6$@;VYC90T* M(VEF(&1E9FEN960H7TU30U]615(I("8F("A?35-#7U9%4B ^/2 Q,#(P*0T* M(R!P<F%G;6$@;VYC90T*(V5N9&EF#0H-"B\O+R\O+R\O+S$O+R\O+R\O+R\R M+R\O+R\O+R\O,R\O+R\O+R\O+S0O+R\O+R\O+R\U+R\O+R\O+R\O-B\O+R\O M+R\O+S<O+R\O+R\O+R\X#0HO+R!M86YI9F5S="YH<' Z(%9E<FEF>2!T:&%T M(&%L;"!D97!E;F1E;G0@;&EB<F%R:65S(&%R92!A="!T:&4@8V]R<F5C= T* M+R\@=F5R<VEO;G,-"@T*+R\@*$,I($-O<'ER:6=H=" R,#$P(%)O8F5R="!2 M86UE>2 M(&AT=' Z+R]W=W<N<G)S9"YC;VT@+B -"B\O(%5S92P@;6]D:69I M8V%T:6]N(&%N9"!D:7-T<FEB=71I;VX@:7,@<W5B:F5C="!T;R!T:&4@0F]O M<W0@4V]F='=A<F4-"B\O($QI8V5N<V4L(%9E<G-I;VX@,2XP+B H4V5E(&%C M8V]M<&%N>6EN9R!F:6QE($Q)0T5.4T5?,5\P+G1X="!O<B!C;W!Y(&%T#0HO M+R!H='1P.B\O=W=W+F)O;W-T+F]R9R],24-%3E-%7S%?,"YT>'0I#0H-"@T* M(VEN8VQU9&4@/&)O;W-T+VET97)A=&]R+VUA;FEF97-T+FAP<#X-"@T*(VEN M8VQU9&4@/&)O;W-T+VUP;"]I;G0N:'!P/@T*(VEN8VQU9&4@/&)O;W-T+W-T M871I8U]A<W-E<G0N:'!P/@T*#0IN86UE<W!A8V4@8F]O<W0@>PT*;F%M97-P M86-E('-E<FEA;&EZ871I;VX@>PT*#0IC;&%S<R!M86YI9F5S="![#0HO+R!V M97)I9GD@870@8V]M<&EL92!T:6UE('1H870@=&AE('-E<FEA;&EZ871I;VX@ M;&EB<F%R>2!I<R!C;VUP:6QE9 T*+R\@=VET:"!T:&4@8V]R<F5C="!V97)S M:6]N<R!O9B!I="=S('!R97%U:7-I=&5S#0I"3T]35%]35$%424-?05-315)4 M* T*"3$@/#T@8F]O<W0Z.FET97)A=&]R.CIM86YI9F5S=#HZ:6YT97)F86-E M7W9E<G-I;VXZ.G9A;'5E#0H)+R\@)B8@8F]O<W0Z.FUP;#HZ8F]O;%\\=')U M93X@+RH@>6]U(&]T:&5R(&-O;F1I=&EO;G,@:&5R92 A("HO#0HI.PT*#0IP M<FEV871E.@T*"7-T871I8R!M86YI9F5S="!M7W9A;&ED871O<CL-"@T*<'5B M;&EC.@T*"2\O('-P96-I9GD@=&AE(&-U<G)E;G0@=F5R<VEO;B!N=6UB97)S M(&9O<B!T:&ES(&QI8G)A<GD-"@ET>7!E9&5F(&)O;W-T.CIM<&PZ.FEN=%\\ M,CX@:6YT97)F86-E7W9E<G-I;VX[#0H)='EP961E9B!B;V]S=#HZ;7!L.CII M;G1?/#,^(&EM<&QE;65N871I;VY?=F5R<VEO;CL-"@T*"2\O('9E<FEF:7D@ M870@<G5N('1I;64@=&AA="!T:&4@<V5R:6%L:7IA=&EO;B!L:6)R87)Y(&ES M(&QI;FME9"!W:71H( T*"2\O(&-O<G)E8W0@1$Q,4PT*"7-T871I8R!I;G0- M"@EG971?:6YT97)F86-E7W9E<G-I;VXH*3L-"@ES=&%T:6,@:6YT#0H)9V5T M7VEM<&QE;65N=&%T:6]N7W9E<G-I;VXH*3L-"@T*"2\O(&UA:V4@<W5R92!C M;VYS=')U8W1O<B!C<F%S:&5S(&EF('1H97)E)W,@82!P<F]B;&5M('=I=&@@ M=F5R<VEO;G,-"@EM86YI9F5S="@I.PT*?3L-"@T*?2 O+R!S97)I86QI>F%T M:6]N#0I]("\O(&)O;W-T#0H-"B-E;F1I9B O+R!"3T]35%]315))04Q)6D%4 224].7TU!3DE&15-47TA04 T* ` end begin 666 manifest.hpp M(VEF;F1E9B!"3T]35%])5$52051/4E]-04Y)1D535%](4% -"B-D969I;F4@ M0D]/4U1?251%4D%43U)?34%.249%4U1?2%!0#0H-"B\O($U3(&-O;7!A=&EB M;&4@8V]M<&EL97)S('-U<'!O<G0@(W!R86=M82!O;F-E#0HC:68@9&5F:6YE M9"A?35-#7U9%4BD@)B8@*%]-4T-?5D52(#X](#$P,C I#0HC('!R86=M82!O M;F-E#0HC96YD:68-"@T*+R\O+R\O+R\O,2\O+R\O+R\O+S(O+R\O+R\O+R\S M+R\O+R\O+R\O-"\O+R\O+R\O+S4O+R\O+R\O+R\V+R\O+R\O+R\O-R\O+R\O M+R\O+S@-"B\O(&UA;FEF97-T+FAP<#H@5F5R:69Y('1H870@86QL(&1E<&5N M9&5N="!L:6)R87)I97,@87)E(&%T('1H92!C;W)R96-T#0HO+R!V97)S:6]N M<PT*#0HO+R H0RD@0V]P>7)I9VAT(#(P,3 @4F]B97)T(%)A;65Y("T@:'1T M<#HO+W=W=RYR<G-D+F-O;2 N( T*+R\@57-E+"!M;V1I9FEC871I;VX@86YD M(&1I<W1R:6)U=&EO;B!I<R!S=6)J96-T('1O('1H92!";V]S="!3;V9T=V%R M90T*+R\@3&EC96YS92P@5F5R<VEO;B Q+C N("A3964@86-C;VUP86YY:6YG M(&9I;&4@3$E#14Y315\Q7S N='AT(&]R(&-O<'D@870-"B\O(&AT=' Z+R]W M=W<N8F]O<W0N;W)G+TQ)0T5.4T5?,5\P+G1X="D-"@T*(VEN8VQU9&4@/&)O M;W-T+VUP;"]I;G0N:'!P/@T*#0IN86UE<W!A8V4@8F]O<W0@>PT*;F%M97-P M86-E(&ET97)A=&]R('L-"@T*8VQA<W,@;6%N:69E<W0@>PT*<'5B;&EC.@T* M"2\O('-P96-I9GD@=&AE(&-U<G)E;G0@=F5R<VEO;B!N=6UB97)S(&9O<B!T M:&ES(&QI8G)A<GD-"@ET>7!E9&5F(&)O;W-T.CIM<&PZ.FEN=%\\,CX@:6YT M97)F86-E7W9E<G-I;VX[#0H)='EP961E9B!B;V]S=#HZ;7!L.CII;G1?/#,^ M(&EM<&QE;65N871I;VY?=F5R<VEO;CL-"GT[#0H-"GT@+R\@<V5R:6%L:7IA M=&EO;@T*?2 O+R!B;V]S= T*#0HC96YD:68@+R\@0D]/4U1?251%4D%43U)? ,34%.249%4U1?2%!0 ` end begin 666 manifest.cpp M+R\O+R\O+R\O,2\O+R\O+R\O+S(O+R\O+R\O+R\S+R\O+R\O+R\O-"\O+R\O M+R\O+S4O+R\O+R\O+R\V+R\O+R\O+R\O-R\O+R\O+R\O+S@-"B\O(&UA;FEF M97-T+F-P<#H-"@T*+R\@*$,I($-O<'ER:6=H=" R,#$P(%)O8F5R="!286UE M>2 M(&AT=' Z+R]W=W<N<G)S9"YC;VT@+B -"B\O(%5S92P@;6]D:69I8V%T M:6]N(&%N9"!D:7-T<FEB=71I;VX@:7,@<W5B:F5C="!T;R!T:&4@0F]O<W0@ M4V]F='=A<F4-"B\O($QI8V5N<V4L(%9E<G-I;VX@,2XP+B H4V5E(&%C8V]M M<&%N>6EN9R!F:6QE($Q)0T5.4T5?,5\P+G1X="!O<B!C;W!Y(&%T#0HO+R!H M='1P.B\O=W=W+F)O;W-T+F]R9R],24-%3E-%7S%?,"YT>'0I#0H-"B\O("!3 M964@:'1T<#HO+W=W=RYB;V]S="YO<F<@9F]R('5P9&%T97,L(&1O8W5M96YT M871I;VXL(&%N9"!R979I<VEO;B!H:7-T;W)Y+@T*#0HC:68@*&1E9FEN960@ M7TU30U]615(I("8F("A?35-#7U9%4B ]/2 Q,C P*0T*(R @<')A9VUA('=A M<FYI;F<@*&1I<V%B;&4@.B T-S@V*2 O+R!T;V\@;&]N9R!N86UE+"!H87)M M;&5S<R!W87)N:6YG#0HC96YD:68-"@T*+R\@=&AI<R!M;V1U;&4@:7,@<&QA M8V5D(&EN(&$@;&EB<F%R>2!T;R!P97)M:70@<G5N=&EM92!V86QI9&%T:6]N M#0HO+R!O9B!M86YI9F5S=',@=7-E9"!W:71H($1,3%,N($ET)W,@:G5S="!A M;B!E>&%M<&QE+B @5&AE('-E<FEA;&EZ871I;VX-"B\O(&QI8G)A<GD@9&]E M<VXG="!U<V4@86YY(&]T:&5R(')U;G1I;64@;&EB<F%R:65S('-O('1H:7,@ M:6X-"B\O(&9A8W0@=V]U;&1N)W0@8F4@;F5C97-S87)Y+@T*#0HC9&5F:6YE M($)/3U-47U-%4DE!3$E:051)3TY?4T]54D-%#0H-"B-I;F-L=61E(#QS=&1E M>&-E<'0^#0HC:6YC;'5D92 \8F]O<W0O<V5R:6%L:7IA=&EO;B]M86YI9F5S M="YH<' ^#0H-"FYA;65S<&%C92!B;V]S="![#0IN86UE<W!A8V4@<V5R:6%L M:7IA=&EO;B![#0H-"B\O('1H:7,@9V5T)W,@8V]N<W1R=6-T960@:6X@82!$ M3$P-"G-T871I8R!M86YI9F5S="!M7W9A;&ED871O<CL-"@T*;6%N:69E<W0Z M.FUA;FEF97-T*"E[#0H)+R\@=VAI8V@@<')O=F]K97,@=&AE(&-H96-K:6YG M(&]F('9E<G-I;VYS(&%T(')U;G1I;64-"@D-"@DO+R!T:&4@<V5R:6%L:7IA M=&EO;B!L:6)R87)Y(&1O97-N)W0@=7-E(&%N>2!O=&AE<B!R=6YT:6UE#0H) M+R\@;&EB<F%R:65S('-O('1H:7,@8V%N(&)E(&$@;F\@;W -"@EI9B@@(2@- M"@D)+R\@=&AE(&ET97)A=&]R(&QI8G)A<GD@9&]E<VXG="!N965D('1O(&EM M<&QE;65N="!T:&ES( T*"0DO+R!S:6YC92!I="=S(&$@:&5A9&5R(&]N;'D@ M;&EB<F%R>2X-"@D)+R\Q(#P](&)O;W-T.CII=&5R871O<CHZ;6%N:69E<W0Z M.F=E=%]I;G1E<F9A8V5?=F5R<VEO;B@I#0H)"2\O)B8@( T*"0ET<G5E("\O M(')E<&QA8V4@=VET:"!Y;W5R(&]T:&5R(')U;G1I;64@8V]N:61I;VYS("$- M"@D)+R\@+BXN#0H)*2D-"@D)=&AR;W<@<W1D.CIO=71?;V9?<F%N9V4H(DEN M=F%L:60@;&EB<F%R>2!V97)S:6]N(BD[#0I]#0H-"B\O(&EM<&QE;65N="!R M=6YT:6UE(')E=')I979A;"!O9B -"FEN= T*;6%N:69E<W0Z.F=E=%]I;G1E M<F9A8V5?=F5R<VEO;B@I>PT*"7)E='5R;B!I;G1E<F9A8V5?=F5R<VEO;CHZ M=F%L=64[#0I]#0II;G0-"FUA;FEF97-T.CIG971?:6UP;&5M96YT871I;VY? M=F5R<VEO;B@I>PT*"7)E='5R;B!I;7!L96UE;F%T:6]N7W9E<G-I;VXZ.G9A K;'5E.PT*?0T*#0I]("\O('-E<FEA;&EZ871I;VX-"GT@+R\@8F]O<W0-"@`` ` end

1 0

performance of a linear algebra/matrix library
by DE 11 May '10

11 May '10

hi all i work on a linear algebra library with an intent to propose it for inclusion into boost collection of libs so my question is: how fast such a lib should be to make everybody happy? i found that to increase the performance of a generic linear algebra library one must complicate the implementation to a very high degree (though this statement should be obvious to everyone) i struggled with poor performance of matrix multiplication and finally identified the bottleneck i improved the implementation (seriosly complicating it, i'm afraid i will forget how it works in a month) and now it performs some 33% slower than C code for virtually any size of matrix the C code is as follows: typedef double type; const size_t n = 42; type *a = new type[n*n], *a1 = new type[n*n], *a2 = new type[n*n]; //filling 'a1' and 'a2' for (size_t i = 0; i<n; ++i) { type * const a_i = a + i*n; for (size_t j = 0; j<n; ++j) a_i[j] = 0.; for (size_t k = 0; k<n; ++k) { type *a = a_i; const type a1_ik = a1[i*n + k]; const type *a2_k = a2 + k*n; for (size_t j = 0; j<n; ++j, ++a, ++a2_k) *a += a1_ik*(*a2_k); } } the C++ code is just matrix<type> m(n, n), m1(n, n), m2(n, n); //filling 'm1' and 'm2' m.assign(m1, m2); more detailed results: 'n' is the dimensions of matrices, 'ratio' is runtime of C++ code divided by runtime of C code (time_cpp/time_c) n | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 ratio | 1,77 | 1,57 | 1,34 | 1,12 | 1,05 | 1,12 | 1,32 | 1,33 | 1,23 | 1,23 | 1,23 as you can see starting with 8 by 8 matices C++ code is roughly 33% slower than C code is that enough to make you (the reader) happy? -- Pavel

9 24

Re: [boost] Parallel Boost Algorithm
by anil khadka 10 May '10

10 May '10

Thanks for the prompt response. I haven't tried the non-distributed (name is confusing though) version. I am using regular version with unweighted graph (I am not passing any weight parameter, as default is unweighted). I used "0.7.0 beta" (parallel-bgl-0.7.0.tar.gz). I think i should try the non-distributed version as 80K quite smaller than 2^20 nodes. (BTW, I also have a graph with more than millions nodes too, but that comes later.) You said that we can have each process read a disjoint portion of the edge set and use the in-place CSR ctors to build the graph, Are there any examples in the source code for this?? One more thing, I also want to calculate the Closeness Centrality, and i do not want to re-processed the whole graph, as most of the calculation(like shortest path) is same as betweenness. Can't we calculate Closeness centrality on the same pass? I'll also tune the parameters(like message-buffer), and post the result here. Metanil. ________________________________ From: Nick Edmonds <ngedmond(a)cs.indiana.edu> To: boost(a)lists.boost.org Sent: Sat, May 1, 2010 9:14:39 PM Subject: Re: [boost] Parallel Boost Algorithm On Apr 30, 2010, at 11:49 AM, anil khadka wrote: > I am pretty new to both boost and parallel boost. > > I am using Brandes Centrality algorithm, but the performance really doesn't meet my expectation. > > If I used Java, which is only using 1 CPU core would complete it in around 30 hrs. > The parallel version which use 8 CPU cores tooks 17 hours!! > > I don't know why there is just around 13 hours gain if i use 8 cores against 1, unless there are lots and lots of communication between each cores. > I am using just 1 machine (not a cluster), right now. > > Graph size is Node 80K, edges 120K > > I am reading edges from files. I used distributed compressed_sparse_row to represent graph. > Right now, it seems like all the cpu cores are reading files on its own, I am assuming each CPU core will takes its graph part automatically (distributed algorithm do it ?). > > Note: I downloaded the parallel version from: http://osl.iu.edu/research/pbgl/software/ > > Any help/suggestions would be really appreciated. Which version of the parallel Betweenness Centrality algorithm are you using? There's a non-distributed version that replicates the graph as opposed to distributing it that should be much faster for small graphs like the one you describe. This algorithm should scale much closer to linearly than the distributed version. I've used the non-distributed version to solve instances up to 2^20 vertices and 2^23 edges if I remember right (it might be 2^19/2^22). The non-distributed version parallelizes the outer loop over source vertices, while the distributed version computes one shortest-path tree at a time using a distributed SSSP algorithm. Is your graph weighted or unweighted? This determines whether the algorithm is O(n^2) or O(n^2 log n). The scaling you're seeing is about what I'd expect for a very small graph instance distributed 8-ways, there simply isn't enough work to hide the latency in the MPI layer. You can try adjusting the size of message buffers in the process group (smaller buffers mean less coalescing, lower latency, and potentially more computation/communication overlap). Check out the --batch-buffer-size parameter to libs/graph_parallel/test/algorithm_performance for an example of how to specify a message buffer size to the process group ctor and then pass the process group to a graph instance. The distributed-memory implementation in PBGL is sub-optimal for shared memory because accessing data stored on other processes goes through the entire MPI layer as opposed to simply reducing to a memory reference. The non-distributed BC algorithm only performs communication to perform property map reductions so this is much less of a problem in that case though you still replicate the graph once per process. In either case the distributed data structures impose some overhead, as does the serialization performed in Boost.MPI (there's a BOOST_MPI_HOMOGENOUS (IIRC) compile time flag that disables some serialization though a 'null-serialization' option that doesn't perform any serialization would be a very useful performance optimization). I'm in the process of rewriting the PBGL to leverage shared-memory parallelism more effectively, though it's unlikely it will every be an optimal shared-memory-only library (because of the overhead imposed by the distributed addressing sche me etc.). There's definitely room for a "Multicore BGL" library, though my lab doesn't have the resources/interest to do it at the moment. All the graph generators in the PBGL assume that every node reads the entire graph's edge set and filters out non-local edges. It's possible to write scalable graph generators which don't do this (the indexed dimacs reader is one example), but this generally requires some sort of preprocessing. Alternately you can have each process read a disjoint portion of the edge set and use the in-place CSR ctors to build the graph. This last approach is how we fit graphs that take a very large fraction of main memory to represent. The PBGL svn trunk at http://osl.iu.edu/research/pbgl/software should be a proper superset of the 1.42 Boost release, the 0.7 tarball should be almost exactly equivalent. New features are pushed to Boost in a coarse-grained fashion when they're tested/stable. Let me know if you have any more questions. Thanks, Nick _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

2 1