- Boost - lists.boost.org

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

Re: GUI Library Proposal for a Proposal
by George van den Driessche 15 Nov '04

15 Nov '04

> Message: 11 > Date: Fri, 12 Nov 2004 22:18:53 +0200 > From: John Torjo <john.lists(a)torjo.com> > Subject: Re: [boost] Re: GUI Library Proposal for a Proposal > To: boost(a)lists.boost.org > Message-ID: <41951AAD.20208(a)torjo.com> > Content-Type: text/plain; charset=us-ascii; format=flowed > > >> >> You have made a good point. I still feel uncomfortable about parsing >> header >> files to determine type information. If header files were used, since >> run-time reflection does not exist, one would have to inject the >> correct >> code into source files based on design-time decisions. But it does >> seem as > > I think reflection in general is very different from reflection for a > GUI. > > When you have a GUI control, you want to apply reflection for a few of > its properties. You won't have #ifdefs (or at least I would consider it > bad design). Case in point: its interface should be extremely simple > and > easy to parse. > > You shouldn't need complex information like reflection for virtual > functions, overloading etc. > > Even reflected property types should be of trivial types: > 1. build in types > 2. std::string > 3. types that can simply be read from /written to strings. > > For case 3., you might also have a validation function which will be > used in design-mode to validate user input. > > At least that's what I want. I *think* what you envisage is based around collecting data from the user via dialogs. So in your view of things, there would be a C++ object that holds the collected data, a set of validation routines, and a reflection map that binds these to the UI. But you don't do anything to the program state until the user clicks "OK" in your dialog, at which point you suck the data out of your simple C++ object and act on it. In contrast, other people (myself included) are considering binding properties and member functions to the UI for similar purposes to why you would expose them to script: to allow the user to drive them. So, for a simple example, let's suppose you have some object that corresponds to a file: class file_backed_t { public: std::string get_filename(); /// This actually renames the file on disk. void set_filename( std::string const& ); }; Now, when you bind the filename property to the UI, you'll automatically do the rename as soon as the user changes the text in the edit box. (Probably that isn't the desired behaviour in this case, but it serves as a demonstration.) This usage pattern corresponds better to modeless dialogs where you don't have an "OK" button. Of course if you are using a generalised reflection architecture like I mentioned yesterday, then you can do both approaches: > One of the things that I noticed about serialisation code is that > there's > generally a symmetry between the reading and writing routines. So > rather > than write "this is how I load an X, and this is how I save one" I'd > want to > write "these are the things in X that need to be saved" and let some > templates figure out what the corresponding routines are. And then it > was > this desire to serialise things automatically by specifying properties > that > led me on to think about a common architecture for language binding and > serialisation. Maybe in the end you'd get declarations like: > > /// Properties for serialisation > boost::properties< my_t, "my_t", boost::serialisation > > .def( "my_int", &my_t::my_int, &my_t::set_my_int ) > // After serialisation format version 4,a > // my_float no longer needed to be serialised > .def( "my_float", &my_t::my_float, &my_t::set_my_float, > boost::serialisation::in_format_version_range<>( 0, 4 ) ) > ; > > /// Properties for scripting > boost::properties< my_t, "my_t", boost::langbinding > > // Use serialisation properties to implement pickling. > .def_pickle( default_pickle_suite< my_t >() ) > .def( "my_int", &my_t::my_int, &my_t::set_my_int, > boost::langbinding::return_internal_reference<>() ) > // We don't want to bind my_float, for whatever reason. > ; boost::properties< file_backed_t, "file_backed_t", boost::gui > // This is a heavyweight property for a modeless dialog .def( "filename", &file_backed_t::get_filename, &file_backed_t::set_filename ) ; // dialog_data_t is just a struct to store data for a modal dialog till // the user clicks "OK", which is when we process it. struct dialog_data_t { std::string filename; // Says whether to back up the specified file before // processing it. bool make_backup; }; // Helper function for dialog_data_t reflection. bool is_good_filename( std::string const& ); boost::properties< dialog_data_t, "dialog_data_t", boost::gui > .def( "filename", &dialog_data_t::filename, boost::gui::validator( &is_good_filename ) ) // No validation required for this simple bool. .def( "make_backup", &dialog_data_t::make_backup ) ; George

2 1