August 2006 - Boost - lists.boost.org

[BGL] Performance improvement minimum spanning tree
by Magnus Ekdahl 24 Aug '06

24 Aug '06

A while ago I had a problem with the MST algorithm in boost. Essentially profiling reviled that the MST algorithm was a bottleneck for the computation I was performing. Thus I had to investigate the performance bottlenecks in boost mst and with this mail I want to investigate the potential for improving current boost implementation. What is the proposed way of getting the prim algorithm updated in boost? First let me argue that there is room for improvement. I have made a test program that constructs 1000 random complete graphs with 1000 nodes and the execution time is as follows actually implementing jarniks algorithm prim_minimum_spanning_tree 47.585s current prim (djikstra wrapper) 3m2638s (338% slower) kruskal_minimum_spanning_tree 40m57s (5063% slower) The 47.585s performance is achieved by just implementing Jarnik/Prims algorithm using the relaxed_heap (that is already in boost, but code is available if necessary). As a side effect it seems to be a good test for the relaxed_heap, given that it revealed problems with the Fibonacci heap[1]. 1. http://lists.boost.org/boost-users/2006/07/20876.php I also want to take the opportunity to ask about the meaning of the minimum spanning tree algorithm as such, since efficient implementations in the future could be helped a lot by knowing exactly what the problem that should be solved is. Given the hardness to understand the actual generality of the MST problem the current implementation tries to solve, I find it difficult to see how efficient algorithms can be heuristically selected. I.e. can you use num_edges(g) as an indicator of sparseness? -- Magnus Ekdahl

2 2

Re: [boost] Boost Units library preview
by Eric Lemings 24 Aug '06

24 Aug '06

> -----Original Message----- > From: boost-bounces(a)lists.boost.org > [mailto:boost-bounces@lists.boost.org] On Behalf Of David Abrahams > Sent: Wednesday, August 23, 2006 2:22 PM > To: boost(a)lists.boost.org > Subject: Re: [boost] Boost Units library preview > > "Eric Lemings" <lemings(a)roguewave.com> writes: > > >> Here's an example of a quantity. The distance from > >> here->| |<-to here is a quantity with a > > > > Well there is supposed to be a lot more whitespace between those > > vertical bars. Let's try a quantity of horizontal length. > > Eric, > > For your own sake, get a new mailer, or at least a new > mailreader. Or read Boost through gmane on a decent > newsreader. Your posts are showing up just as you intend > them, but your mailreader is making you think they're garbled. Well that time I was responding the appearance of the message in the Boost lists archive (using Firefox): http://lists.boost.org/Archives/boost/2006/08/index.php Gmane sounds like a good option though. Eric.

2 1

extensions and repository
by Jeremy Pack 24 Aug '06

24 Aug '06

I've used Boost for a little while in image processing research, and found it to be quite useful. Though the image processing algorithms I've used are probably too specialized for Boost, I've created a couple of libraries to aid in the development of this software that I realized might work as part of Boost. Could I get some thoughts? One library is used for handling linked libraries. It basically makes it possible to extend an application's functionality by adding new linked libraries without recompiling the application itself. It eases the creation of plug-ins, in what is a relatively object-oriented fashion. (inheritance, virtual functions etc.) The other library is used as a repository for variables of any type. It includes the following (each of the following is optional for each value): - callbacks when a data value is updated (methods or functions) (not using boost::signals, but it probably could) - checks that a data value is consistent (i.e. within the correct range) when it is updated - mutexes for data access - useable (though not yet completed) in a distributed environment If there is anything like either of these already in development, I would be interested on working on them. If not, I could work on rewriting them to be considered for inclusion, if there is interest. Also, if there are any projects that could use some help, I have some experience in the following areas: 3D graphics Graphical user interfaces Numerical algorithms Distributed systems Parallel algorithms Jeremy Pack

2 1

Patch: unused variables
by Vince Tse 24 Aug '06

24 Aug '06

When compiling the Boost source tree (Aug 22, 2006 snapshot) with GCC 3.4 on Gentoo Linux on AMD64, you¹ll get 3 warnings about unused variables. The patch is attached. Building: bjam -sTOOLS=gcc -s"GCC=gcc -Wall -Werror" -s"GXX=g++ -Wall -Werror" -q stage Compiler: gcc (GCC) 3.4.4 (Gentoo 3.4.4-r1, ssp-3.4.4-1.0, pie-8.7.8) Copyright (C) 2004 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Uname: Linux ses0247 2.6.15-gentoo-r5-1 #2 SMP Fri Mar 10 17:11:28 UTC 2006 x86_64 Dual Core AMD Opteron(tm) Processor 275 AuthenticAMD GNU/Linux The 3 variables concerned are created to be used in an assert() statement, but any asserts get replaced with static_cast<void>(0), thus resulting in an unused variable. Breaking up declaration and initialization fixes this issue.

2 1

[Boost-bugs] [ boost-Support Requests-1545941 ] Having problems with building boost
by SourceForge.net 24 Aug '06

24 Aug '06

Support Requests item #1545941, was opened at 2006-08-24 15:13 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1545941&group_… Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: Building Boost Group: None Status: Open Resolution: None Priority: 5 Submitted By: Abrok (abrok) Assigned to: Nobody/Anonymous (nobody) Summary: Having problems with building boost Initial Comment: Having problems while trying to build boost. Using Windows 2000 Professional, ActiveState Python and i have visual studio .net 2003 installed as well. I downloaded boost_1_33_0 and bjam. Used command "bjam "-sTOOLS=vc-7_1" install" but I keep getting error: ...skipped <@boost!include!boost-1_33!boost!mpl!aux_!preprocessed!no_ctps>lambda _no_ctps.hpp for lack of <directory-grist>C:\Boost\include\boost-1_33\boost\mpl\ aux_\preprocessed\no_ctps... ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1545941&group_… ------------------------------------------------------------------------- Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[typeof] nested_typedef_emulation/cw-9.4
by Vladimir Prus 24 Aug '06

24 Aug '06

Hi, the error at http://tinyurl.com/pdte2 looks like compler-specific library problem. Eric, can you look into that? Thanks, Volodya

5 5

Re: [boost] Boost Units library preview
by Eric Lemings 24 Aug '06

24 Aug '06

> -----Original Message----- > From: boost-bounces(a)lists.boost.org > [mailto:boost-bounces@lists.boost.org] On Behalf Of Phil Richards > Sent: Wednesday, August 23, 2006 8:58 AM > To: boost(a)lists.boost.org > Subject: Re: [boost] Boost Units library preview > > On 2006-08-23, Matthias Troyer <troyer(a)itp.phys.ethz.ch> wrote: > > - Nm would be a "dimension" > > Not really. It is the unit. Correct. A newton is a derived unit composed of base units, specifically kilogram, meter, and second. Meter is of course a base unit. > The dimension is: MASS * LENGTH^2 * TIME^2 Also correct. Every unit, whether a base unit or derived, has a corresponding dimension. > > - 1 Nm would be a "quantity" No. This is a measure. It has a specific unit and a specific value. Here's an example of a quantity. The distance from here->| |<-to here is a quantity with a dimension of length. You don't know what its value is exactly but you do know that it has a value and can be measured. Until you actually measure this length with a particular unit does the "quantity" become a "measure". Converting a measure into a quantity is essentially the same as stripping away the unit but keeping the dimension. Does that make sense? > > - a torque measured in Nm or an energy measured in Nm > would be two distinct units Dimensions and units are C++ types. They have no "value" in the conventional sense. > > - 1 Nm as torque, 1 Nm as energy or 1 J as energy would be > > three distinct measures > > I think as far as a dimensionality checking goes, they are > all the same. As far as a units checking goes, Nm and J > *could* be distinguished. It's an interesting question as to > what, exactly, "energy" and "torque" are once you try to > separate away the dimensionality and units bits... :-) Yep, if the units are the same and the value is the same then they are (or should be) considered the same measure. I think it should be left up to users to interpret these measures and how they are used. Eric.

4 4

[utility] operators_test/gcc-3.4.5/64 bit
by Vladimir Prus 23 Aug '06

23 Aug '06

Hi, the above test fails with ICE: http://tinyurl.com/pw2qu Is any maintainer willing to sumbit a bug report? In any case, can this failure be marked as expected? Thanks, Volodya

5 6

Re: [boost] Boost Units library preview
by Eric Lemings 23 Aug '06

23 Aug '06

> -----Original Message----- > From: Eric Lemings > Sent: Wednesday, August 23, 2006 10:24 AM > To: 'boost(a)lists.boost.org' > Subject: RE: [boost] Boost Units library preview > > > > > -----Original Message----- > > From: boost-bounces(a)lists.boost.org > > [mailto:boost-bounces@lists.boost.org] On Behalf Of Phil Richards > > Sent: Wednesday, August 23, 2006 8:58 AM > > To: boost(a)lists.boost.org > > Subject: Re: [boost] Boost Units library preview > > > > On 2006-08-23, Matthias Troyer <troyer(a)itp.phys.ethz.ch> wrote: > > > - Nm would be a "dimension" > > > > Not really. It is the unit. > > Correct. A newton is a derived unit composed of base units, > specifically kilogram, meter, and second. Meter is of course > a base unit. > > > The dimension is: MASS * LENGTH^2 * TIME^2 > > Also correct. Every unit, whether a base unit or derived, > has a corresponding dimension. > > > > - 1 Nm would be a "quantity" > > No. This is a measure. It has a specific unit and a specific value. > > Here's an example of a quantity. The distance from > here->| |<-to here is a quantity with a Well there is supposed to be a lot more whitespace between those vertical bars. Let's try a quantity of horizontal length. >From here ------------------------- ------------------------- to here. Hopefully that will appear as a significant distance. Eric.

2 1

Re: [boost] Boost Units library preview
by Eric Lemings 23 Aug '06

23 Aug '06

> -----Original Message----- > From: boost-bounces(a)lists.boost.org > [mailto:boost-bounces@lists.boost.org] On Behalf Of Matthias Troyer > Sent: Saturday, August 19, 2006 1:55 AM > To: boost(a)lists.boost.org > Subject: Re: [boost] Boost Units library preview > > ... > If I understand the above concepts correctly then we only need three > terms: > > - named unit > - unnamed unit > - quantity (value + unit) I try to keep the definitions as simple as possible. IMHO, there are really only four distinct concepts: dimension - an "abstract" type quantity - an "abstract" object whose "type" is a dimension unit - a type "derived" from a particular dimension measure - an arithmetic object whose "type" is a unit The last term is a term I introduced to distinguish an object with a dimension from an object with a unit. Very important distinction. Eric.

5 4