May 2013 - Boost - lists.preview.boost.org

[MPL] Bug with default lambda expressions?
by Louis Dionne 23 May '13

23 May '13

Hi, Some higher order algorithms in the MPL have a default for the lambda expression they accept. A good example is `boost::mpl::equal`: template <typename S1, typename S2, typename Pred = is_same<_, _> > struct equal; This works fine most of the time, but I was recently bitten by the following: template <typename VectorOfVectors, typename Vector> struct find_vector : find_if< VectorOfVectors, equal<Vector, _1> > { }; typedef find_vector< vector< vector<int, int>, vector<char, char> >, vector<char, char> >::type ThisWillBreak; What happens here is that the `equal<Vector, _1>` expression inside `find_vector` really is `equal<Vector, _1, is_same<_1, _2> >` because of the default value for the predicate to `equal`. When the lambda is evaluated, the placholders inside the inner `is_same<_1, _2>` expression are replaced too, which yields unexpected results. Using template <typename S1, typename S2, typename Pred = typename lambda<is_same<_, _> >::type> struct equal; or equivalently template <typename S1, typename S2, typename Pred = quote2<is_same> > struct equal; fixes the issue. Also note that all of the unit tests of the MPL still pass with these changes. Is the current behavior intended, or should I submit a patch? Regards, Louis Dionne

5 7

[test]: heap tests broken in release
by Tim Blechmann 23 May '13

23 May '13

hi all, for some reasons, the tests of boost heap are broken in release. it crashes somewhere in boost.test code. trunk works well ... > 0 __gnu_cxx::new_allocator<unsigned long>::construct PC=0x0057084e, FP=0x7fffdee7d5e0 [/usr/include/c++/4.7/ext/new_allocator.h#120] 1 __gnu_cxx::__alloc_traits<std::allocator<unsigned long> >::construct<unsigned long> PC=0x0056fa2e, FP=0x7fffdee7d610 [/usr/include/c++/4.7/ext/alloc_traits.h#203] 2 std::vector<unsigned long,std::allocator<unsigned long> >::_M_insert_aux PC=0x0056fb77, FP=0x7fffdee7d680 [/usr/include/c++/4.7/bits/vector.tcc#354] 3 std::vector<unsigned long,std::allocator<unsigned long> >::push_back PC=0x0056ee4f, FP=0x7fffdee7d6a0 [/usr/include/c++/4.7/bits/stl_vector.h#893] 4 boost::unit_test::test_suite::add PC=0x0056d823, FP=0x7fffdee7d6d0 [/media/hd3btr/sources/boost-release/boost/test/impl/unit_test_suite.ipp#139] 5 boost::unit_test::ut_detail::test_init_caller::operator () PC=0x00577721, FP=0x7fffdee7d710 [/media/hd3btr/sources/boost-release/boost/test/impl/framework.ipp#96] 6 boost::unit_test::ut_detail::invoker<int>::invoke<boost::unit_test::ut_detail::test_init_caller> PC=0x0057c657, FP=0x7fffdee7d730 [/media/hd3btr/sources/boost-release/boost/test/utils/callback.hpp#42] 7 boost::unit_test::ut_detail::callback0_impl_t<int,boost::unit_test::ut_detail::test_init_caller>::invoke PC=0x0057c526, FP=0x7fffdee7d760 [/media/hd3btr/sources/boost-release/boost/test/utils/callback.hpp#89] 8 boost::unit_test::callback0<int>::operator () PC=0x00586d31, FP=0x7fffdee7d780 [/media/hd3btr/sources/boost-release/boost/test/utils/callback.hpp#118] 9 boost::detail::do_invoke<boost::scoped_ptr<boost::detail::translate_exception_base>,boost::unit_test::callback0<int> > PC=0x00586bb5, FP=0x7fffdee7d7a0 [/media/hd3btr/sources/boost-release/boost/test/impl/execution_monitor.ipp#281] 10 boost::execution_monitor::catch_signals PC=0x00585ecf, FP=0x7fffdee7e290 [/media/hd3btr/sources/boost-release/boost/test/impl/execution_monitor.ipp#885] 11 boost::execution_monitor::execute PC=0x00585f8b, FP=0x7fffdee7e370 [/media/hd3btr/sources/boost-release/boost/test/impl/execution_monitor.ipp#1211] 12 boost::unit_test::framework::init PC=0x7f7a20adb04a, FP=0x7fffdee7e400 [/media/hd3btr/sources/boost-release/boost/test/impl/framework.ipp#268] 13 boost::unit_test::unit_test_main PC=0x7f7a20af0c17, FP=0x7fffdee7e4b0 [/media/hd3btr/sources/boost-release/boost/test/impl/unit_test_main.ipp#177] 14 main PC=0x004d6439, FP=0x7fffdee7e4d0 [/media/hd3btr/sources/boost-release/boost/test/unit_test.hpp#59] 15 __libc_start_main PC=0x7f7a1fecfea3, FP=0x7fffdee7e590 [/usr/lib/debug/lib/x86_64-linux-gnu/libc-2.17.so] 16 _start PC=0x004d6344, FP=0x7fffdee7e598 [/media/hd3btr/sources/boost-release/bin.v2/libs/heap/test/fibonacci_heap_test.test/gcc-4.7/debug/threading-multi/fibonacci_heap_test] -- any idea? thanks, tim

3 3

[type_erasure][release] okay to add to release?
by Steven Watanabe 22 May '13

22 May '13

AMDG The trunk tests are clean except for xlc. In Christ, Steven Watanabe

4 5

[1.54.0] Deadline for major changes approaching
by Daniel James 22 May '13

22 May '13

Hello everyone, This is just a quick reminder that the release branch is closed for major changes on Monday. thanks, Daniel

3 6

[heap] van Emde Boas tree proposal
by Jeremy Murphy 22 May '13

22 May '13

Hi everyone, I propose to add the van Emde Boas tree (vEBt) to Boost, primarily as a container adaptor to satisfy the Boost.Heap concept and interface. Rationale The vEBt is an extremely efficient data structure for satisfying the operations of a priority queue. Where u = |U| and U is the universe of numbers that can be stored in the container, the vEBt performs top() in O(1) and push(), pop(), erase() in O(lg lg u). U is, however, limited by type and range: positive integer values from 0 to 2^w (where w is the word size)*. The naive implementation uses an abysmal Θ(u) space but this can be improved to Θ(n) with hashing. Design If people support the idea of the vEBt in principle then I would be really interested in their thoughts on ... should u be a run-time or compile-time constant? Should the vEBt be available as a data structure for purposes other than a priority queue? Implementation I recently finished the basic implementation of the algorithm, so anyone interested in seeing a teething new-born is welcome to take a look.** Gritty questions and constructive criticism about class structure, etc are always welcome. The code won't meet all the programming guidelines yet, but don't worry, I have them in mind. Cheers. Jeremy * There is a good lecture on it from MIT here: https://www.youtube.com/watch?v=AjFtTQevtq0 ** https://code.google.com/p/veb-heap/

1 0

Returned mail: Data format error
by sean.farrow＠seanfarrow.co.uk 22 May '13

22 May '13

The original message was received at Wed, 22 May 2013 15:02:28 +0800 from seanfarrow.co.uk [86.198.252.36] ----- The following addresses had permanent fatal errors ----- <boost(a)lists.boost.org> ----- Transcript of session follows ----- while talking to lists.boost.org.: >>> MAIL From:sean.farrow@seanfarrow.co.uk <<< 501 sean.farrow(a)seanfarrow.co.uk... Refused

1 0

Git Modularization Ready for Review
by Dave Abrahams 22 May '13

22 May '13

Hi All, After substantial work, including massive changes by me and Daniel Pfeifer to KDE's svn->Git conversion tool, we have captured every Boost SVN commit in a Git repository. You can view the results at http://github.com/boostorg http://bitbucket.org/boostorg or you can pull from these repositories and view them in your local browser. The conversion process is automated by http://jenkins.boost.org/job/Boost2Git/ using the tool at http://github.com/ryppl/Boost2Git The rules that describe how commits are distributed are in https://github.com/ryppl/Boost2Git/blob/master/repositories.txt To understand how to edit that file, please read https://github.com/ryppl/Boost2Git/wiki/Editing-repositories.txt Daniel and I are ready to accept your feedback on the results of modularization, and especially your pull requests containing edits to the ruleset. I will the steering committee to establish a formal review period, though. -- Dave Abrahams

16 41

[graph] A few additions to propose to BGL
by Mikael Persson 21 May '13

21 May '13

Hi all, I have developed a number of small additions to the BGL, nothing major, just things that were useful to me and more practical as an extension to BGL instead of as a separate library, and if you're interested, I'm willing to contribute them back. These are non-intrusive additions, no modifications of existing BGL code is required (although some can be discussed, see below). The proposed additions are: 1) Additional property-maps to fill the void between bundled properties and boost::property_map<> mechanisms. Incl. descriptor-to-bundle maps, bundle-to-property maps, composite maps (i.e., chaining property maps), etc. https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 2) A few more property-tags that are common for graph algorithms. https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 3) A few more graph-concepts: a) Tree concept: Facilities for tree inspection. b) MutableTree concept: Facilities for tree construction / destruction. c) MutablePropertyTree concept: Same as MutableTree concept but with properties (like MutablePropertyGraph concept). d) NonCompactGraph concept: For graphs / trees that may contain invalid vertices or edges (i.e., "holes"). https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 4) Boost Graph Library Tree adaptors. This is for using the boost::adjacency_list to store a tree (and comply to tree concepts). https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 5) Pooled Adjacency-list. This is a wrapper around the boost::adjacency_list class which uses a method similar to Boost.Pool to store vertices in a contiguous storage (boost::vecS) while keeping vertex descriptors and iterators valid after removals. https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… Here are the some subjective issues to discuss: w.r.t.-3c) In my MutablePropertyTree concept, I have included removal functions that extract the properties of the elements to be removed. This can usually be implemented easily and provides symmetry w.r.t. to element-adding functions (if you can provide properties when creating elements, you should be able to retrieve them when removing elements). Without this, you can either copy the properties before removing the elements (needless copy and destruct), or you can std::move them out before removing the elements (leaving zombie elements in the graph in the meanwhile). The preferred option is to have the removal function move the properties into a destination (e.g. back-inserter). I would argue that the existing MutablePropertyGraph concept should include overloads for recording properties during removals, this shouldn't break any existing user-side code and be easily added to existing graph data structures. w.r.t.-3d) I have two issues with the NonCompactGraph concept: 1) Invalid elements mostly (or only) show up from iterators. So, one practical option is to have the iterators skip invalid elements. This effectively makes a "non-compact" graph look "compact". This would make this concept useless. However, iterators that must skip over invalid elements cannot provide random-access. There are ways to get the best of both worlds, such as introducing some "always-valid" iterators, which might or might not be identical to the base iterators (zero-overhead) depending on whether the graph is compact or not (a tag or meta-function might be needed to identify this). 2) A common operation with non-compact containers is to "re-pack" it. Generally, the advantage of leaving holes in a container is to avoid invalidating iterators. But, at certain points, one can decide to compact the container again. In the non-compact implementations that I have, I have included such functions, but never really needed them in practice (when removals <= insertions). I wonder if such functions should be included in the NonCompactGraph concept. This is mainly what I propose to contribute back to the BGL (or any part of it). I have, however, lots of other code that is peripheral or closely tied to the BGL. Some is a bit more experimental at this stage, while other things are too peripheral or too specific. You are welcome to browse my library to see if anything else grabs your attention. See below for a short list of a few specific items that might be of interest. Cheers, (and pardon the lengthy email) Mikael. P.S.: Other interesting items that I have developed that might be worth proposing: 6) Linked-tree. A classic linked-tree data structure. It has similar signature as boost::adjacency_list and models the relevant BGL graph concepts and the proposed tree concepts: https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 7) Contiguous layout trees. These are fixed-arity (D-ary) trees that use a breadth-first layout (similar to heaps) in contiguous memory. They model the relevant BGL concepts and the proposed tree concepts. a) D-ary BF-tree uses one contiguous storage with vertices laid out in breadth-first order. It works great, it's my work-horse tree-implementation and the memory-locality it provides has been a major performance factor in my code. https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… b) D-ary COB-tree (Cache-Oblivious B-tree) uses a tree of moderately-sized contiguous blocks with breadth-first layout within them. This thing is nice in theory, but in practice it has been difficult to guarantee correctness and to deliver good performance (it only out-performs the BF-tree when the size of the tree is in the gigabytes range). https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 8) I wrote an AD* algorithm, which I modeled after the BGL's existing A* search implementation. It's rather old code that I haven't done much with for a while, but I'm willing to resurrect it if there is interest for it. The fact that it is a dynamic / anytime / on-line graph algorithm makes it a bit odd compared to the other existing algorithms in BGL (all static / batch / off-line algorithms, AFAIK). https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 9) I wrote a multi-graph template to overlay an adjacency-list (i.e., general "graph") and a tree (i.e., complying to the proposed tree concepts). The point here is to have one set of vertices and two sets of edges, one forming a general graph and one forming a tree. The motivation is to: keep the graph and tree strongly synchronized by sharing the same storage; and, benefit from cache-friendly tree layouts (e.g., BF-tree) when using the general graph. My reservations with this are that the code is (1) not be quite polished yet, (2) a bit too advanced / specific for the general nature of the BGL, and (3) a bit convoluted to use (user-side code is messy). https://github.com/mikael-s-persson/ReaK/blob/master/src/ReaK/ctrl/graph_al… 10) If you find anything else you like, we can discuss it. I mostly write path-planning code and lots of numerical stuff. I have a nice sampling-based motion-planning framework in place that builds upon the BGL, and extended (and more mathematically sound) "Topology" concepts, as well as space-partitioning trees and stuff like that: https://github.com/mikael-s-persson/ReaK/tree/master/src/ReaK/ctrl/graph_alg https://github.com/mikael-s-persson/ReaK/tree/master/src/ReaK/ctrl/path_pla… https://github.com/mikael-s-persson/ReaK/tree/master/src/ReaK/ctrl/topologi… -- Sven Mikael Persson

2 2

Re: [boost] [ASIO] Having a hard time after upgrading my boost
by Marat Abrarov 20 May '13

20 May '13

> My code is heavily multi-threaded. This problem doesn't show up in > single threaded environment at all. My OS is SUSE 11 and g++-4.3.3 as the > compiler. I may have to post some code eventually but on the top off your > head - do you have any pointers for me? Note that free functions like asio::async_read/aync_read_untill (async_write/async_write_until, etc) are composed operations so "... The program must ensure that the stream performs no other read operations (such as async_read, async_read_until, the stream's async_read_some function, or any other composed operations that perform reads) until this operation completes" (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/reference/async_re ad_until.html). Also note that most of Asio classes (sockets, timers, etc.) are not thread safe. So in multi-threaded program you have to use some kind of synchronization if there is no implicit strand (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/overview/core/stra nds.html). The simplest kind of synchronization is asio::io_service::strand. If you use something else (for example, mutex) then notice intermediate handlers created by composed operations (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/overview/core/stra nds.html, asio_handler_invoke) and use your synchronization in a right way (for mutex see https://github.com/boostcon/2011_presentations/raw/master/mon/thinking_async hronously.pdf, struct mutex_wrapper at page 95-97). There is a feature named "Handler Tracking" (http://www.boost.org/doc/libs/1_53_0/doc/html/boost_asio/overview/core/hand ler_tracking.html) that can help you to investigated the order of handler invocation. Regards, Marat Abrarov.

2 1

[ASIO] Having a hard time after upgrading my boost libraries
by Arpan Sen 20 May '13

20 May '13

Folks, I recently moved to boost 1.52, been using a pretty old version of boost earlier. Quite a number of pieces of my code have stopped working since then, but the one that's really a pain is the ASIO piece. I have a lot of code that makes use of ASIO's async read/write and other calls and there seems to be a problem reading data from socket with async_read_until - sometimes I get empty string, there's valid data at other times. My code is heavily multi-threaded. This problem doesn't show up in single threaded environment at all. My OS is SUSE 11 and g++-4.3.3 as the compiler. I may have to post some code eventually but on the top off your head - do you have any pointers for me? Thanks for your time. Arpan

3 2