- Boost - lists.boost.org

[Fusion] port to c++0x
by Christopher Schmidt 04 Oct '09

04 Oct '09

I participated in Google's 'Summer of Code' for Boost this year. My project was to port Boost.Fusion to c++0x. The program is over now and I would like to give you a short report on my work and put my code up for comments. In a nutshell, there is rvalue support, native variadic templates are used if possible and the public classes and (meta-) functions are guarded by a set of static asserts that detect most invalid (template) arguments. I also added certain new functionality to provide an easier, faster and more intuitive programming interface. My implementation is pretty much backwards compatible and all test cases pass on gcc 3.4/4.4 and vc 9. Here is a short overview of the most striking changes besides the implementation of raw c++0x support. I removed the deque container and the extension-classes. The deque container is undocumented and, in my opinion, does not go well with the other container due to its intrinsic extension mechanism. There also should not be a performance gain compared to a regular fusion::joint_view in combination with two fusion::vector. The extension classes are pretty much Boost.Proto specific. At the moment they seem to be out of place, especially as they are undocumented, unmaintained and not even part of the regular file structure. I would like to see them either fully documented (with the underlying concept of segmented sequences) or in the detail namespace of Boost.Proto. I added support for associative iterators. An associative forward sequence shall provide an iterator type which implements the extension backend of the intrinsic (meta-)functions fusion::result_of::value_of_data, fusion::deref_data and fusion::result_of::key_of. This has the advantage that all view classes, even fusion::iterator_range, are able to adapt the underlying sequence's associative-ness. fusion::transform_view, as a special case, got an additional template parameter. This parameter specifies whether the view should model either the forward concept only or the associative and the forward concept. This design breaks consistency with Boost.MPL. Unfortunately these changes are crucial and I would rather risk this break with Boost.MPL than missing that important feature. Using the old implementation, there is no way to avoid explicitly converting from a view back to an associative sequence to preserve the associative-ness. This leads to a nasty runtime overhead due to evaluation of every element of the view and copy-/move-constructing it. Besides, other changes include: -If the compiler supports rvalue references, all fusion container have a template constructor (taking either const lvalue or 'templated' rvalue references). -If the compiler supports variadic templates, fusion::cons, fusion::pair and fusion::single_view have a variadic template constructor (taking either const lvalue or 'templated' rvalue references) that allows emplace construction. -The view classes adapt the full category of their underlying sequences. As mentioned above, the associative-ness is preserved, but also, if possible, the random-access or bidirectional trait. -The result_of::-metafunctions accept r- and lvalue references arguments. If an argument is not reference-qualified, it will be considered to be an lvalue reference. All existing extension implementations must be changed to adapt this new behaviour. -The algorithm functions now also take (and correctly forward) non-const reference arguments. -Fusion iterators (with reference compatible sequence types and a very same index) and views (with reference compatible sequence types) have a working operator= that correctly reassigns the underlying sequence references. -Fusion now also adapts MPL iterators. If, and only if, the <boost/fusion/adapted/mpl.hpp>-header is included, mpl sequences and iterators are recognized as fusion sequences and iterators. -There are new headers to adapt std::(tr1::)array or std::(tr1::)tuple. The overall compile-time performance of my code is satisfying. Compiling a compilation unit that includes all possible fusion headers takes on gcc 4.4 slightly more time than the official fusion implementation. If native variadic templates are present, the compilation is a lot faster (usually up to 3 to 6 times), regardless of the value of FUSION_MAX_xxx_SIZE. The compile-time performance of actual fusion code is mixed. The intrinsic container and iterator (meta-)functions compile a little bit slower compared to the official fusion implementation. This is due to explicit removal of the references on the arguments of all result_of::metafunctions and some additional abstraction layer. If the compiler support rvalue references, there has to be a rather ugly and slow type evaluation/transformation to avoid issues with rvalue references on non-array, non-class types (see /support/internal/ref.hpp and 8.5.3p5 of the current c++0x draft for more details). On the other hand, I added several optimizations (such as result preevaluation), and, if variadic templates are present, the actual instantiation of fusion containers is a lot faster. All in all, the compile-time performance is a little bit worse if c++0x features are not present. If c++0x features are present, the code should compile a little bit faster in most cases. For example, the lambda example of the Boost.Proto documentation, which internally heavily relies on Boost.Fusion, takes on my machine 2.6 seconds to compile with the 'old' fusion on gcc 4.4, 3 seconds with my port without -std=c++0x, and 2.1 seconds with c++0x features being present. The overall performance might be even better once Boost.MPL adapts native variadic templates and the compiler supports template aliases. There have been tons of other changes, mostly bugfixes, optimizations (in terms of compile time of course) and removals of redundancy. Whenever I had the choice, I tried to prefer clean, redundancy-free instead of heavily optimized code. The overall performance loss is not noticeable though, and most compile-time optimizations that go beyond the as-little-template-instantiations-as-possible paradigm are pretty much compiler dependent anyway. There is still some work to do. I did not add c++0x-specific test cases and there are several parts of the documentation which need to be updated. By the way, are there any official guidelines for documenting c++03/c++0x-specific differences? For now, I would like to hold off on implementing these changes until Boost.TypeTraits adapts c++0x. Right now I implemented missing or incorrectly behaving trait functions in the fusion::detail-namespace. I would rather like to use the official ones, at least in the documentation and in the test cases. Besides that, I think my implementation is trunk-ready. If there are no objections, I would like to finish the outstanding work as soon as possible, and then merge my code with the trunk. Of course I will provide long-term support for the project. In fact, I would love to become an official fusion maintainer. You can find the code in the boost sandbox (/sandbox/SOC/2009/fusion). If you test the code with a compiler that has decltype support, please use the HEAD of the trunk rather than the official 1.40 distribution package to compile your code. Best regards Christopher

6 17

Review Request: Boost.Itl; The Interval Template Library
by Joachim Faulhaber 03 Oct '09

03 Oct '09

Dear developers, the Interval Template Library is now in a state where I think it does conform the requirements and guidelines for boost libraries fairly well. To decide, whether it's design, implementation and overall usefulness is sufficient to be accepted in the boost libraries collection is now up to you. In the last round of refactoring I concentrated on efficiency and optimization issues. The implementation of the itl's interval containers is still based on std::set and std::map, but algorithms are now exploiting hinted insert and are manipulating intervals and values in place instead of copying in many instances. This way, it has been possible to improve performance significantly. Along the way of implementing optimizations I have documented the complexity guarantees for all important functions of the library's interface. Please note that the original ITL as presented in May 2008 has been split into 3 parts and only the *first* part is submitted for review: itl : Core library, interval containers, SUBMITTED FOR REVIEW Additional parts are: itl_xt : Extensions like histories and generalized crosstables validate: The law based test automaton (LaBatea). A validation tool using laws aka axioms. *itl* is a complete library containing all required ingredients particularly a separate test suite (NOT using LaBatea) and the quickbook documentation. The code is successfully compiled and tested with gcc-3.4.4, 4.1.0, 4.3.2 and msvc-8.0, 9.0. I have uploaded the review version as itl_3_1_0.zip to the vault in section containers. http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_3_… Another file itl_plus_3_1_0.zip contains all three parts (itl, itl_xt and validate). http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_pl… Reviewers interested in the law based testing part may have to refer to this file to examine those tests. The law base testing examples compile and run with gcc-4.3.2, msvc-8.0 and 9.0. LaBatea does not compile with gcc-4.1.0 or older. The quickbook generated documentation is included in the zip files and is also available online at http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html Sources are also available form the sandbox: https://svn.boost.org/svn/boost/sandbox/itl/ To close my request for review, let me take the opportunity to do some advertisement ;-) focusing on some of the itl's highlights. * The Itl emerged out of real world software development extracting generic functionality from numerous use cases of the date time problem domain. (http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/ex…) But the need for the same data structures occurs in other fields as well. E.g. Zachary Turner uses a compressed_bitmap similar to an itl::interval_set to manage very large file system allocation bitmaps and gives more use cases here (http://lists.boost.org/Archives/boost/2009/06/152817.php) * Aggregation on overlap not only provides a useful feature to compute aggregation results on interval_maps like statistics, it also leads to a generalized addition operation on maps that exhibits interesting semantical properties. E.g. (http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/semant…) * The itl's design is based on sets of laws (aka axioms) that are described in the documentation. (http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/semant…) These law sets not only are giving a formal specification of the library. Using the law based testing tool (LaBatea) (https://svn.boost.org/svn/boost/sandbox/itl/boost/validate) allows to validate the library code for every specified law. * For the itl, 18 laws have been validated on the 7 container templates with varying instantiation types for template parameters, running a total of 719 different law instances (each of them for large numbers of randomly generated test data). (https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/) This gives everyone a method to check semantical properties of the library in a way that is more powerful than traditional unit tests. To get the 'complete picture' of the library's interface you may want to refer to the synoptic function table first (http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/in…) before looking at more specific topics. Hoping to have quickened your appetite to take a closer look at this library before and during the review process. best regards Joachim Faulhaber

6 28

[task]
by Baxter Jeremy 03 Oct '09

03 Oct '09

I have been looking at the boost task library from the vault and comparing it with the threadpools library http://threadpool.sourceforge.net and have a few comments. Firstly I should say that I'm interested in tasks / thread pools for a situation rather different from the one for which they are designed. Namely the case in which threads (tasks) are being used to monitor some internal or external activities and so may block for significant periods of time waiting for the result of a complex planning algorithm or for some condition being met. I'm therefore worried about blocking all the available threads. I think what I need is to be able to dynamically add new threads to the thread pool, or just not use a pool at all and create and destroy a thread for every subtask. However during my review I came across a helper function which I though might allow re-use of the same thread but I'm concerned could actually lead to deadlock: reschedule_until <file:///D:\Boost\boost.task-0.3.0\doc\html\boost_task\utilities.html> In the function boost::this_task::reschedule_until( Pred const&) allows to synchronize the task with other asynchronous events without blocking the worker-threads (bool Pred::operator()() must not block). The current task will be rescheduled until the passed predicate becomes true. Looking at the code I don't think this is an accurate description and gives the potential to introduce deadlocks in tasks which otherwise would operate normally. >From the code what reschedule_until does is repeatedly call the process_ function to look for new tasks, testing once each task has finished to see if the predicate has been met. This is not quite as described since the task is not 're-scheduled' it is actually blocked until whatever task the scheduler next selects is complete. This introduces problems if multiple tasks on the queue use reschedule_until. If there are three tasks T1 T2 and T3 on the queue doing the following: T1 { ... Reschedule_until(A) B.setTrue() ... } T2 { ... Reschedule_until(B) ... } T3 { ... A.setTrue() } What we would like to happen, and what will happen if they are run in different threads (or a different order on the one thread) is that T1 does some work, waits for T3 then terminates. T2 does some work, waits for T1, then does some more work. T3 independently does its work and finishes by signalling that T1 can continue. Unfortunately if they are scheduled in the order T1 T2 T3 then T1 runs, reschedules and T2 gets to run until it reschedules and T3 gets to run. When T3 finishes T1 is in a position when it can run, however it will not get the chance to because in order for condition A to be checked T2 has to have finished, and it can't do that until B is set true. Therefore although progression should be possible as the condition T1 is waiting for has been met it will never notice and T1 and T2 will never complete. I'm not sure that there is a general solution to this problem without using more threads so that any potentially runnable task will get a chance. A second comment. Comparing the task and thread pool libraries they use different waiting mechanisms. Thread pool uses a wait-notify construct on the queue to block worker threads if the queue is empty. Task uses active polling, trying to get items from the queue and then sleeping for a short period if nothing can be found on the queue. I wondered why the difference is there. Wait - notify would look like it should perform better in the case where there are fewer tasks than threads is polling better in the case where there are many more tasks than threads and so threads will never sit idle polling for long? Jeremy Jeremy Baxter Lead Researcher, UAVs & Autonomy Tel: 01684 894801 email: jwbaxter(a)QinetiQ.com www.QinetiQ.com QinetiQ - Delivering customer focused solutions Please consider the environment before printing this email. The information contained in this E-Mail and any subsequent correspondence is private and is intended solely for the intended recipient(s). The information in this communication may be confidential and/or legally privileged. Nothing in this e-mail is intended to conclude a contract on behalf of QinetiQ or make QinetiQ subject to any other legally binding commitments, unless the e-mail contains an express statement to the contrary or incorporates a formal Purchase Order. For those other than the recipient any disclosure, copying, distribution, or any action taken or omitted to be taken in reliance on such information is prohibited and may be unlawful. Emails and other electronic communication with QinetiQ may be monitored and recorded for business purposes including security, audit and archival purposes. Any response to this email indicates consent to this. Telephone calls to QinetiQ may be monitored or recorded for quality control, security and other business purposes. QinetiQ Limited Registered in England & Wales: Company Number:3796233 Registered office: 85 Buckingham Gate, London SW1E 6PD, United Kingdom Trading address: Cody Technology Park, Cody Building, Ively Road, Farnborough, Hampshire, GU14 0LX, United Kingdom http://www.qinetiq.com/home/notices/legal.html

3 5

[utility] Fix for const issue of value_initialized merged to release
by Niels Dekker - address until 2010-10-10 03 Oct '09

03 Oct '09

FYI, I have just merged the fix of ticket #2548, regarding value_initialized, to the release branch. The fix has been on the trunk for quite a few months, and Fernando Cacciola has told me he thinks that it's okay to merge it. The fix disables implicit conversion from const value_initialized<T> to non-const T&. More information: Ticket #2548, Let's fix the logical constness of value_initialized!" https://svn.boost.org/trac/boost/ticket/2548 [boost] [utility] A fix for the const issue of value_initialized http://lists.boost.org/Archives/boost/2009/02/148489.php Changeset 56547: Merged value_init from the trunk, including fix of #2548, regarding "const value_initialized" https://svn.boost.org/trac/boost/changeset/56547 Kind regards, Niels -- Niels Dekker http://www.xs4all.nl/~nd/dekkerware Scientific programmer at LKEB, Leiden University Medical Center

1 0

[Serialization] Question about "Back versionning"
by Vincent Thomas 02 Oct '09

02 Oct '09

Hi, During some testing of boost::serialization features, I tried to do this : Let's say we have a class X, the current version for this class is 5 (BOOST_CLASS_VERSION(X, 5)). Serialize in class X is split into save/load.What I'd like to do now, is save an object of type X at version 3 to make the object loadable by an older version of my software. that is get ""<X class_id="0" tracking_level="0" version="3">" in my resulting file instead of "<X class_id="0" tracking_level="0" version="5">". I've gone through the documentation of boost::serialization and I found only one thing. A TODO speaking about "Back versionning". It's not clear for me if this part speaks about the archive (like xml_oarchive, xml_iarchive, ...) or the object I can serialize, in other words does it concern this line "<boost_serialization signature="serialization::archive" version="5">" or a line like this one "<test class_id="0" tracking_level="0" version="2">" in a resulting file ? Maybe it concerns both but that I don't know. So apparently If I understand the documentation correctly I can't do what I describe above at the moment. Does anyone know if it's going to be implemented soon, or if I can be of any help ? Vincent

1 0

Hello and a quick question.
by S. Brad Daughdrill 02 Oct '09

02 Oct '09

Hello to all, I first want to say hello to all the members. I recently ran across your project, and I am really interested in working with you all. My question is are there an example that use forms? The example I found all seem to be console applications and while they are helpful, I really want my students to start programming with forms (initially at least). They will be using Visual C++ 2008 Express. Thank you for everything ahead of time. Brad *----- S. Brad Daughdrill The University of Alabama B.S. Management Information Systems M.S. Operations/Project Management M.B.A. Financial Risk M.A. Economics (Candidate) 146 Lenora Drive Tuscaloosa, AL 35401 (o) 205.348.7591, Bidgood Hall - 351E (c) 251.510.3089 (e) S.Brad.Daughdrill(a)Gmail.com*

3 2

threads: how to remotely kill a thread?
by David M. Cotter 02 Oct '09

02 Oct '09

say i'm on the main thread, and i've got a thread::id of some other preemptive thread. i do not have the actual boost::thread object any more. and i want to unceremoniously kill that thread. like right now. how do i kill it? i don't see a way to recover the actual boost::thread from the thread::id. but even if i could, and then call thread.interrupt(), that's more of a polite request which is free to be ignored, rather than a you_must_die_now() thing.

3 2

[BGL] Why source() needs a graph argument?
by Cosimo Calabrese 02 Oct '09

02 Oct '09

Hi to all, the question is in subject. I don't understand it. Either source() and target() functions only return the m_source member and the m_target of edge_base. They don't use the graph argument, that is not even used. I need to know it because I'm implementing an union_graph adaptor, that provides the join's view of 2 graph. When I call the source() function on a union_graph, I provide an edge_descriptor; but whereas the source() function of an adjacency_list needs a graph argument, I need to know which graph belongs the edge, which is an 2 * O|E| operation on 2 graphs. Thanks, Cosimo Calabrese

2 1

"parent_from_member" proposal
by Domagoj Saric 02 Oct '09

02 Oct '09

Sometimes your design contains the typical model<->view / data/logic<->gui separation of classes/objects but at the same time it is static enough that it does not require the also typical dynamic way of connecting the two worlds through pointers and/or signals/events and/or function pointers/callbacks and/or ... In other words: - the two corresponding objects ('model/logic' and 'view/gui') always exist in the same memory space/process - the 'model' always exists when the 'view' exists - one does not mind compile time coupling/compile time hit that will occur if the 'model' and the 'view' classes know which methods they must call on 'the other' object as opposed to knowing which slots to expose/signals to connect to. In such a scenario the typical 'dynamic connection/coupling' approach unnecessarily incurrs overhead both in terms of verbosity and efficiency...it is 'easier' if the 'model' holds the 'view' object by value (or a wrapper class holds them both or whatever other solution as long as their offset in memory is constant)...then the the 'model' knows its 'view' instance implicitly from its this pointer (only a positive offset is required) but the 'view' instance does not know its 'model' instance implicitly (using 'conventional' methods) although it is infact also only a matter of offset calculation from its this pointer (only a negative one in this situation)... Now, if we take into account that the 'model' class knows the name of its 'view' member it can 'create' a pointer-to-member to it thus enabling us to create a sort of an extended and templated version of the standard C offset macro (from stddef.h). Using this 'template offset' functor (called ParentFromMember here, provided by the 'model' class) the 'view' class/instance can now also get to its 'model' instance implicitly from its this pointer (without knowing exactly how or where it exists in relation to the 'model' instance). template <class T> struct DummyStorage { typedef typename std::tr1::aligned_storage < sizeof( T ), std::tr1::alignment_of<T>::value >::type type; }; template < class Parent, class Member, Member Parent::* pMember > class ParentFromMember { public: typedef typename std::tr1::remove_const<Parent>::type Parent; typedef typename std::tr1::remove_const<Member>::type Member; public: Parent & operator()( Member & member ) const { DummyStorage<Parent>::type const parentStorage; Parent const * const pDummyParent( reinterpret_cast<Parent const *>( &parentStorage ) ); ptrdiff_t const offset ( reinterpret_cast<char const *>( &( pDummyParent->*pMember ) ) - reinterpret_cast<char const *>( pDummyParent ) ); return *reinterpret_cast<Parent *>( reinterpret_cast<char *>( &member ) - offset ); } Parent const & operator()( Member const & member ) const { return operator()( const_cast<Member &>( member ) ); } }; ...the DummyStorage part is just 'added-paranoia'...the whole operator() function could (probably ?) be simplified to work just like the offset macro in MSVC's stddef.h (in fact, with MSVC, both approaches produce the same code)...: Parent & operator()( Member & member ) const { ptrdiff_t const offset( reinterpret_cast<ptrdiff_t>( &( reinterpret_cast<Parent const *>( 0 )->*pMember ) ) ); return *reinterpret_cast<Parent *>( reinterpret_cast<char *>( &member ) - offset ); } .... so if you have class View { void someViewFunc(); }; class Model { private: View v; public: typdef ParentFromMember<Model, View, &Model::v> ViewModel; void someModelFunc(); } void View::someViewFunc() { Model & myModel( Model::ViewModel()( *this ) ); myModel.someModelFunc(); } ... If this has any chance of not being against the standard and/or "by-the-book" conventions it could probably be augmented with additional debugging/paranoia checks (for example that classes that would use this would be required to derive from some utility class and/or hold the "Member" object in some templated wrapper that would add GUID-like headers in front of objects in memory to assert that the conversions were called on valid objects and things like that)... The whole approach could also be extended with utility classes like FusionContainerFromMember, ParentFromOptionalMember, MemberFromMember and such... One 'big' problem is that this breaks MSVC (tested with 9.0 SP1 and 10b1) with a compiler error (at the typedef line) when the Parent class (in this case the Model class) is a template class (it compiles fine with the online Comeau compiler). A workaround (for MSVC) that might come to mind is to place the typedef outside the body of the template Parent class (it can also be in a another class) but this no solution as template typedefs do not work and an out-of-body template would require public access to the member/encapsulation breakage...so far the only acceptable solution I could find for MSVC is to use a wrapper metafunction that returns the required ParentFromMember<> specialization... -- "That men do not learn very much from the lessons of history is the most important of all the lessons of history." Aldous Huxley

1 0

[serialization]Double rounding bug?
by Mariusz Kwiczala 02 Oct '09

02 Oct '09

Hello, I found that for some small double value, serialization change last few digits.(it look like some rounding bug) Below is one example (I have more :) usually it is a number 0.00... or 0.00 with 19-20 digits after dot): -0.0070850229047457131 - double value -0.007085022904745714 - double value after save/read from xml file On my computer I have always assert in function DoubleTest(). Boost: version 1.39/boost_serialization-vc90-mt-gd-1_39.dll Compiler: VS2008 Could you verify below code on your computer (call DoubleTest())? Is it bug? Sample code: #pragma warning( push ) #pragma warning( disable : 4512 ) #include <boost/archive/xml_iarchive.hpp> #pragma warning( pop ) #include <boost/archive/xml_oarchive.hpp> #include <boost/serialization/vector.hpp> #include <boost/bind.hpp> #include <fstream> #include <boost/archive/xml_oarchive.hpp> #include <boost/archive/text_iarchive.hpp> #include <boost/archive/text_oarchive.hpp> #include <boost/serialization/vector.hpp> void LoadDoubleValue(DoubleValue& doubleValue, const char* fileName) { std::ifstream ifs(fileName); assert(ifs.good()); boost::archive:: xml_iarchive ia(ifs); ia >> BOOST_SERIALIZATION_NVP(doubleValue); } void SaveDoubleValue(DoubleValue& doubleValue, const char* fileName) { std::ofstream ofs(fileName); assert(ofs.good()); boost::archive::xml_oarchive oa(ofs); oa << BOOST_SERIALIZATION_NVP(doubleValue); } void DoubleTest() { DoubleValue doubleValue1; doubleValue1.m_value = -0.0070850229047457131; SaveDoubleValue(doubleValue1, "DoubleValue.xml"); DoubleValue doubleValue2; LoadDoubleValue(doubleValue2, "DoubleValue.xml"); //but from file is read -0.007085022904745714 assert(doubleValue1.m_value==doubleValue2.m_value); } Best regards, Mariusz

3 2