- Boost - lists.boost.org

MPL compilation speed trade-offs...
by Jaap Suter 16 Nov '04

16 Nov '04

Hello, can any compiler expert give me feedback on whether there should be a noticable difference in compilation speed between the following two meta-functions: template<class N, class M, class Q, class P> struct foo : mpl::plus < N, typename mpl::minus < M, typename mpl::divides < Q, P >::type >::type >::type {}; and template<int N, int M, int P, int Q> struct foo { enum { value = N + (M - (Q/P)) }; typedef boost::mpl::int<value> type; } The second version saves me a lot of template instantiations and many header inclusions, at the cost of losing some genericity. On the other hand, if the calculation becomes complicated, I find myself using many enums to hold intermediate values, resulting in code like the following: template<class T> struct next_number_with_same_num_bits { enum { lowest_bit_set = T::value & (-T::value), lowest_bit_set_index = count_leading_zeroes<T>::type::value, next_t = T::value + lowest_bit_set, next_lowest_set_bit = next_t & (-next_t), mask = next_lowest_set_bit - lowest_bit_set, result_t = next_t | (mask >> (lowest_bit_set_index + 1)) }; typedef boost::mpl::int_<result_t> type; }; which leads MSVC to run out of so-called compiler-keys much quicker than if I reduce the above to the completely unreadable: template<class T> struct next_number_with_same_num_bits { enum { result_t = (T::value + (T::value & (-T::value))) | ((((T::value + (T::value & (-T::value))) & (-T::value - (T::value & (-T::value)))) - (T::value & (-T::value))) >> (count_leading_zeroes<T>::type::value + 1)) }; typedef boost::mpl::int_<result_t> type; }; Does anybody have any thoughts or comments on this technique, and is anybody else using tricks around MPL to make sure your compiler still handles things? Thanks, Jaap Suter

2 1

performance using accumulate, bind, and make_transform_iterator
by Richard Newman 16 Nov '04

16 Nov '04

I'm a newbie to the list; if an answer to my question is in a FAQ I'm not aware of, please let me know; but I've googled the documentation and don't see it. In fact, I see little regarding performance factors to consider when using boost, so I may not be looking in the right places. We're running a performance-sensitive application and so I've begun to find points to optimize the code. The following is a digest of our experience bringing boost functionality into this effort (forgive the generic code; it was sanitized for intellectual property perservation, etc.): I am posting this experience in hopes that someone can confirm our reasoning and perhaps point us in the right direction for information, etc., for thinking through these kind of issues in the future. Any advice is appreciated. You'll see that, in part, my woes came from violating the cardinal rule of only optimizing that code which is most expensive; nonetheless, this specific instance is an involved enough example that I thought it worth pursuing... ============== During the writing of an interface, a function was added to a templated class, that has-a stl vector, to sum SomeValue of its contained elements: const unsigned allElementsValue() const { unsigned result = 0; std::vector<T>::const_iterator thisElement(sequence_.begin()); const std::vector<T>::const_iterator endElement (sequence_.end()); while (thisElement != endElement) { result += thisElement->getSomeValue(); } } At the time this interface was being written, it was a departure from an prior approach and so it was important that performance was not significantly affected. During this effort, we used KCachegrind and found out that this call was (relatively) more expensive than hoped. Since std::accumulate was supposed to be a quicker way to walk through elements, that approach was tried and the following function resulted: const unsigned allElementsValue() const { unsigned result = 0; return std::accumulate ( boost::make_transform_iterator (sequence_.begin(), boost::mem_fn(&T::getSomeValue) ), boost::make_transform_iterator (sequence_.end(), boost::mem_fn(&T::getSomeValue) ), 0 ); } We now note the use of make_transform_iterator and the use of a 0-ary member function of the constituent element objects. This code is semantically equivalent and yet yielded an relatively significant performance improvement. The performance increase can be taken in part to considering that STL and boost use templates and so some of what why otherwise have to be done at run-time can now be done at compile-time. So we naively took the moral of the story to be that std::accumulate is Good and walking through elements manually with a loop is Bad. The following code was later examined. Note that this particular code happens to be executed many, many times in our run. So any performance change to this code will have a major effect to the overall performance of the program. Certainly a ripe and ready candidate for applying this new conclusion. The code was changed from this... ----------- // Note that a and b (referred to in calcSomeValue below) are // references to other objects passed into the function that // has this code float result = 0.0; // SomeObjectPtrCont is a typedef for a stl vector that contains // boost::shared_ptrs managing pointers to SomeObject. // SomeObjectPtrs_ is an instance of SomeObjectPtrCont SomeObjectPtrCont::const_iterator thisIter(SomeObjectPtrs_.begin()); const SomeObjectPtrCont::const_iterator endIter (SomeObjectPtrs_.end()); while (thisIter != endIter) { result += (*thisIter)->calcSomeValue(a, b); ++thisIter; } ----------- ...to this: ----------- // Note that a and b (referred to in calcSomeValue below) are // references to other objects passed into the function that // has this code float result = 0.0; // Use a typedef so that we can handle overloading of calcSomeValue typedef float (SomeObject::* calcFunct)(const T&, const OtherObjB&) const; // Use stl accumulate to do same thing as the while loop result = std::accumulate ( boost::make_transform_iterator ( SomeObjectPtrs_.begin(), boost::bind(static_cast<calcFunct>(&SomeObject::calcSomeValue), _1, a, b) ), boost::make_transform_iterator ( SomeObjectPtrs_.end(), boost::bind(static_cast<evalFunct>(&SomeObject::calcSomeValue), _1, a, b) ), float(0.0) ); ----------- Note that this is a significantly more sophisticated use of std::accumulate with boost::make_transform_iterator and boost::bind. Indeed, now bind must take an argument, marked by the _1, to link the function being called, evaluate, with each element in the collection being walked through. The evaluate() function itself is binary and not a member of the constituent elements. Nonetheless, it is semantically equivalent to the more conventional while loop form. Remembering our earlier simplistic conclusion that std::accumulate is Good and that while-loops are Bad, this change was made, checked in, and pride swelled within the author (silly me) for so cleverly using boost, et al. The expectation at the time was that since templates would be involved more, then much of the logic would be resolved at compile-time rather than run-time giving us a performance increase just like with the simpler accumulation approach (basically since one form of accumulation is good, than all are better). We discovered that the revised code now ran 4 times SLOWER. KCachegrind showed the problem was the above code. So what the *&^% gives? Rather than analyze the situation, it's always better to tinker :), so the next attempt involved an approach that std::accumulate also allows: ----------- // Note that a and b (referred to in calcSomeValue below) are // references to other objects passed into the function that // has this code float result = 0.0; // Use a typedef so that we can handle overloading of calcSomeValue typedef float (SomeObject::* calcFunct)(const T&, const OtherObjB&) const; // Alternate accumulation approach result = std::accumulate ( SomeObjectPtrs_.begin(), SomeObjectPtrs_.end(), float(0.0), boost::bind (std::plus<float>(), _1, boost::bind(static_cast<calcFunct>(&SomeObject:calcSomeValue), _2, a, b) ) ); ----------- This sped up the code but now it was measured to be 3 times slower than the original form, though now not 4 times as slow. Hardly a ringing endorsement for the use of std::accumulate. Our best conclusion so far is that involving boost::bind in this kind of operation causes accumulate to go through additional function redirection at run-time to access the final evaluate() function desired. This more than offsets any potential gain that might have been realized by the std::accumulate because now its use of templated compilation is thwarted by all of this run-time redirection. Note that because of the arguments involved, the compiled code under boost::bind must now move variables onto the stack so that when the underlying accumulate calls this implicit functor, those values are part of its state. All of this is now done at run-time where as before, without having to move such variables, it was really just a change of a function pointer's value. So, the new current thinking is that std::accumulate is Better than simple while-loops that walk through elements which is still Bad. However, boost::bind under std::accumulate is Worse. At this point, the best advice is that one should use std::accumulate whenever simple accumulations are needed. However, once one has to start involving boost::bind on 1+-ary functions or anything else that requires new run-time function redirection, then retreating back to while-loop is a better performance solution. Thank you all for reading this far... Kind regards, Richard Newman Crowley Davis Research richard(a)nospam.cdres.com (take out the nospam. to email me directly)

4 8

1_32_0 final test python issue
by Russ Gibson 16 Nov '04

16 Nov '04

The latest 1_32_0 (downloaded today - 2004-11-15 at around 13:30 PST/-0800) failed to build the python libs because of "python22.lib" references in a link. I have python 2.3 installed, and have the python environment variables set like this: PYTHON_ROOT=C:\python23 PYTHIN_VERSION=2.3 PYTHON_LIB_PATH=C:\Python23\libs My WinXP system is brand newly set up (from major crash), so there aren't any strange things going on (i.e. no other python's in path, etc.). I have cygwin installed, but none of the cygwin stuff is in my path (or any other environment variables for that matter), so I'm confident that isn't a problem. Besides, it also has python 2.3, not 2.2. I actually used vsvars32.bat to get the build environment for boost. Everything else (that wasn't dependant on boost python) build fine. Anybody know anything about this? (Be sure to reply-all if you reply to this, unless you don't mind long delays for a response). --> Russ

2 1

Ideas for logging/tracing
by Alexander Nasonov 15 Nov '04

15 Nov '04

I have a couple of ideas about making function traces nicer: 1. Use of PP_SEQ interface to "parse" function name and arguments int X::foo(char* buf, size_t len) { BOOST_TRACE_MEM_FUN( (foo)(buf, len) ); // ... } Function name can be extracted with BOOST_PP_SEQ_ELEM(0, fn), the arguments with BOOST_PP_SEQ_POP_FRONT(fn). BOOST_TRACE_MEM_FUN macro could expand to: tracer tracer_line_N(this, "foo", "(buf, len)", resolve_args (buf, len)); 2. In addition to text format, produce XML output. This opens up a possibility for XSLT convertion to UML sequence and collaboration diagrams (XMI). -- Alexander Nasonov

4 15

[iterator] Why no assignment operator for filter_iterator?
by David M. Jones 15 Nov '04

15 Nov '04

Is there a reason why filter_iterator has no assignment operator? I have a place in my code where I want to perform an assignment of filter_iterators. Can anyone suggest a work-around? Thanks in advance, David Jones

2 2

1.32 Draft Tarball: MPL docs completely missing?
by Stefan Slapeta 15 Nov '04

15 Nov '04

Currently, mpl/doc/index.html shows this information: The Boost MPL library documentation is currently undergoing a major overhaul for the 1.32 release. Please come back in a few days. :-( Stefan

2 1

[graph] bellman_ford_shortest_paths interface
by Vladimir Prus 15 Nov '04

15 Nov '04

Hi, after trying to use the bellman_ford_shortest_paths I think it's a little bit strange. First of all, user is required to initialise distance map before calling the algorithm. The distance to the source vertex must be set to zero and distances to other vertices to infinity. Why can't the algorithm accept a source vertex as parameter and do initialisation itself? Dijsktra surely does not require such initialization. Another problem is that number of vertices is passed as parameter. I realize this is more flexible (for example I can compute the maximum length of all paths with less than N edges), but it's also confusing and dangerous. I've just passed a wrong variable to that parameter and spend quite some time debugging. Is it possible to provide a version of the algorithm which (1) takes just graph, without vertex number parameter (2) takes start vertex, and initialises distance map itself - Volodya

2 6

Still OK to merge changes into 1.32.0?
by Beman Dawes 15 Nov '04

15 Nov '04

I've just fixed a minor Windows only filesystem::path bug in the CVS head. Is it OK to merge the fix into 1.32.0, or is 1.32.0 closed? --Beman

2 3

[1.32 release] RC_1_32_0 branch is closed for any modifications
by Aleksey Gurtovoy 15 Nov '04

15 Nov '04

Please see the subject. If you think that something just *has* to be committed to the branch, please post a query to the list before doing so, however trivial the change is (this includes fixes to the documentation and likes). Thanks, -- Aleksey Gurtovoy MetaCommunications Engineering

1 0

[BGL] Determining whether a path exists from vertex U to vertex V
by David M. Jones 15 Nov '04

15 Nov '04

I have looked at the BGL User Guide/Reference manual book but I can't seem to find the answer to this seemingly basic question. I have a directed BGL graph. Given two vertices U and V, I want to know whether there is a path from U to V. I don't care what path it is; I just want to know whether one exists or not. It looks like I might be able to use the BFS or DFS to do this, but that seems like attacking a mosquito with a tank. A slightly more complicated problem that I want to solve is: given vertices U and V, I want to know whether there is a path from U to V such that all edges along the path have a certain property. Again, I don't care to know what the path is or its length; only whether or not such a path exists. Thanks in advance, David Jones

3 3