October 2011 - Boost - lists.boost.org

Re: [boost] boost threads: pthread mutex priority inheritance + patches
by Jason Newton 16 Jan '12

16 Jan '12

Ack, no discussion on this since I posted it back in July. In my opensuse packages, I apply the following patch to insure priority inheritence on mutexs. I had to go inside the mutex ctor to do the work. -Jason On Wed, Jul 27, 2011 at 5:40 PM, Jason Newton <nevion(a)gmail.com> wrote: > On Wed, Jul 27, 2011 at 4:48 PM, Jason Newton <nevion(a)gmail.com> wrote: > >> For the moment, the few lines that compose the mutex class are easily >> copied so that I can do my own business inside the constructor but I expect >> others will run into this problem down the line and this solution is a bit >> unsavory. Any better advice? >> > > Actually a private copy of mutex didn't work so well overall as pthread > conditions are hard coded to > void boost::condition_variable::wait(boost::unique_lock<boost::mutex>&) > > -Jason >

2 1

Is there any interest in command line interpreter class templates?
by alexey.tsoy 29 Dec '11

29 Dec '11

Hello everybody, The file command_line.zip in the containers directory in Boost’s vault contain command line interpreter library. There you can find simple tutorial with examples and draft documentation. The library supports variable amount of option parameters as well as automatic type casting. Note that their types may be diferent. The library doesn't require special linking because it contains headers only. You only need to type in a few lines of code to start using it. Regards Alexey -- View this message in context: http://boost.2283326.n4.nabble.com/Is-there-any-interest-in-command-line-in… Sent from the Boost - Dev mailing list archive at Nabble.com.

4 6

[1.48.0] Beta 1 release candidates available
by Beman Dawes 20 Dec '11

20 Dec '11

Release candidate files for 1.48.0 beta 1 are available at http://boost.cowic.de/rc/ As always, the release managers would appreciate it if you download the candidate of your choice and give building it a try. Please report both success and failure, and anything else that is noteworthy. This helps ensure the candidates build OK before we push them out to SourceForge. Thanks, --The release managers

21 44

Proposed Boost.Algorithms Review Ends
by Dave Abrahams 28 Nov '11

28 Nov '11

The review of Marshall Clow's proposed Boost.Algorithms submission officially ended yesterday, but if you get your review in before the end of the weekend, as review manager I'll probably consider it. So far we've had five votes, which is reasonable for something of this scale. Thanks everybody for your time and interest. I'll be posting the review results next week. Regards, Dave -- Dave Abrahams BoostPro Computing http://www.boostpro.com

2 3

[functional] [variant] Hash patch for variant
by Antony Polukhin 22 Nov '11

22 Nov '11

Header and tests in attachments. Passes tests on GCC-4.4 and VC10. OK to commit to trunk and include header file from boost/functional/hash/extensions.hpp ? Best regards, Antony Polukhin

2 3

[parameter] type requirement compiler error
by lcaminiti 08 Nov '11

08 Nov '11

Hello all, The following parameter type requirement: (required (graph, *) ) (optional (root_vertex, (typename boost::graph_traits<graph_type>::vertex_descriptor), *boost::vertices(graph).first) ) Generates a GCC error: dfs.05.cpp:40: error: ‘graph_type’ was not declared in this scope Detailed code and error below. In fact, if I look at the code after pp, I can see that graph_type is define only after the type requirement is checked... why? What am I doing wrong? Thanks a lot! --Lorenzo #include <boost/graph/adjacency_list.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/range/irange.hpp> #include <boost/pending/indirect_cmp.hpp> #include <boost/parameter.hpp> #include <iostream> namespace graphs { BOOST_PARAMETER_NAME(graph) BOOST_PARAMETER_NAME(visitor) BOOST_PARAMETER_NAME(root_vertex) BOOST_PARAMETER_NAME(index_map) BOOST_PARAMETER_NAME(color_map) template< typename Size, typename IndexMap > boost::iterator_property_map<boost::default_color_type*, IndexMap, boost::default_color_type, boost::default_color_type&> default_color_map ( Size const& num_vertices, IndexMap const& index_map ) { std::vector<boost::default_color_type> colors(num_vertices); return &colors[0]; } BOOST_PARAMETER_FUNCTION( (void), depth_first_search, tag, (required (graph, *)) (optional (visitor, *, boost::dfs_visitor<>()) (root_vertex, (typename boost::graph_traits<graph_type>::vertex_descriptor), *boost::vertices(graph).first) (index_map, *, boost::get(boost::vertex_index, graph)) (in_out(color_map), *, default_color_map(boost::num_vertices(graph), index_map)) ) ) { std::cout << "here\n"; boost::depth_first_search(graph, boost::visitor(visitor). color_map(color_map).root_vertex(root_vertex). vertex_index_map(index_map)); } } // namespace graphs template< typename TimeMap > class dfs_time_visitor : public boost::default_dfs_visitor { typedef typename boost::property_traits< TimeMap >::value_type T; public: dfs_time_visitor(TimeMap dmap, TimeMap fmap, T& t) : dmap_(dmap), fmap_(fmap), time_(t) {} template< typename V, typename G > void discover_vertex ( V u, G const& g ) const { put(dmap_, u, time_++); } template< typename V, typename G > void finish_vertex ( V u, G const& g ) const { put(fmap_, u, time_++); } TimeMap dmap_; TimeMap fmap_; T& time_; }; using namespace boost; int main ( ) { typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> G; typedef boost::graph_traits<G>::vertices_size_type size_type; enum {u, v, w, x, y, z, N}; char names[] = {'u', 'v', 'w', 'x', 'y', 'z'}; typedef std::pair<int, int> E; E edges[] = {E(u, v), E(u, x), E(x, v), E(y, x), E(v, y), E(w, y), E(w, z), E(z, z)}; G g(edges, edges + sizeof(edges) / sizeof(E), N); std::vector<size_type> dtime(boost::num_vertices(g)); std::vector<size_type> ftime(boost::num_vertices(g)); size_type t = 0; dfs_time_visitor<size_type*> vis(&dtime[0], &ftime[0], t); graphs::depth_first_search(g, vis); std::vector<size_type> dorder(N); boost::integer_range<size_type> r(0, N); std::copy(r.begin(), r.end(), dorder.begin()); std::sort(dorder.begin(), dorder.end(), boost::indirect_cmp<size_type*, std::less<size_type> >(&dtime[0])); std::cout << "order of discovery: "; for(int i = 0; i < N; ++i) std::cout << names[dorder[i]] << " "; std::cout << std::endl; std::vector<size_type> forder(N); std::copy(r.begin(), r.end(), forder.begin()); std::sort(forder.begin(), forder.end(), boost::indirect_cmp<size_type*, std::less<size_type> >(&ftime[0])); std::cout << "order of finish: "; for(int i = 0; i < N; ++i) std::cout << names[forder[i]] << " "; std::cout << std::endl; return 0; } $ g++ -Wall -I../../../../../boost-trunk.cygwin dfs.05.cpp dfs.05.cpp:40: error: ‘graph_type’ was not declared in this scope dfs.05.cpp:40: error: template argument 1 is invalid dfs.05.cpp:40: error: expected `::' before ‘,’ token dfs.05.cpp:40: error: expected identifier before ‘,’ token dfs.05.cpp:40: error: template argument 3 is invalid dfs.05.cpp:40: error: expected `::' before ‘{’ token dfs.05.cpp:40: error: expected class-name before ‘{’ token ../../../../../boost-trunk.cygwin/boost/parameter/preprocessor.hpp: In instantiation of ‘boost::parameter::aux::argument_pack<graphs::boost_param_params_40depth_first_search<int>, const boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, const dfs_time_visitor<main::size_type*>, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>’: dfs.05.cpp:88: instantiated from here ../../../../../boost-trunk.cygwin/boost/parameter/preprocessor.hpp:157: error: no type named ‘parameter_spec0’ in ‘struct graphs::boost_param_params_40depth_first_search<int>’ ../../../../../boost-trunk.cygwin/boost/parameter/preprocessor.hpp:158: error: no type named ‘parameter_spec0’ in ‘struct graphs::boost_param_params_40depth_first_search<int>’ ../../../../../boost-trunk.cygwin/boost/parameter/preprocessor.hpp: In instantiation of ‘boost::parameter::aux::argument_pack<graphs::boost_param_params_40depth_first_search<int>, const boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>’: dfs.05.cpp:88: instantiated from here ../../../../../boost-trunk.cygwin/boost/parameter/preprocessor.hpp:157: error: no type named ‘parameter_spec0’ in ‘struct graphs::boost_param_params_40depth_first_search<int>’ ../../../../../boost-trunk.cygwin/boost/parameter/preprocessor.hpp:158: error: no type named ‘parameter_spec0’ in ‘struct graphs::boost_param_params_40depth_first_search<int>’ dfs.05.cpp: In function ‘int main()’: dfs.05.cpp:88: error: no matching function for call to ‘depth_first_search(main()::G&, dfs_time_visitor<size_type*>&)’ -- View this message in context: http://boost.2283326.n4.nabble.com/boost-parameter-type-requirement-compile… Sent from the Boost - Dev mailing list archive at Nabble.com.

6 14

[smart_ptr] scoped_array / shared_array (size_t) constructor
by Olaf van der Spek 07 Nov '11

07 Nov '11

Hi, Currently, one has to manually allocate the array and pass the ptr to the constructor of scoped_array / shared_array. boost::scoped_array<unsigned char> A(new unsigned char[100]); boost::shared_array<unsigned char> B(new unsigned char[100]); This requires one to repeat the type and shared_array requires two allocations (one extra for the control block). std::vector has a constructor from size_t and one can write: std::vector<unsigned char> V(100); This avoids the type duplication and it'd allow shared_array to do only a single allocation. A few choices have to be made: 1. Should "new T[sz]" or "new T[sz]()" be used? 2. What should happen when size = 0? Should it call new T[0] or should it just use NULL? https://svn.boost.org/trac/boost/ticket/4637 -- Olaf

10 46

Interest in bounded (Top-Bounded) Range adaptor.
by Fernando Pelliccioni 06 Nov '11

06 Nov '11

Is there interest in adding a Top-Bounded adaptor into Boost.Range ? Example: using namespace boost::adaptors; using namespace boost::assign; std::vector<int> input; input += 1,2,3,4,5,6,7,8,9; boost::copy( input | bounded(0), std::ostream_iterator<int>(std::cout, ",")); // prints nothing boost::copy( input | bounded(1), std::ostream_iterator<int>(std::cout, ",")); // prints 1, boost::copy( input | bounded(2), std::ostream_iterator<int>(std::cout, ",")); // prints 1,2, boost::copy( input | bounded(8), std::ostream_iterator<int>(std::cout, ",")); // prints 1,2,3,4,5,7,8, The above example is similar in behavior to ... boost::copy_n( input, 0, std::ostream_iterator<int>(std::cout, ",")); boost::copy_n( input, 1, std::ostream_iterator<int>(std::cout, ",")); boost::copy_n( input, 2, std::ostream_iterator<int>(std::cout, ",")); boost::copy_n( input, 8, std::ostream_iterator<int>(std::cout, ",")); The difference is that *copy_n* algorithm doesn't check for begin(range) != end(range) In the following line, an error occurs at runtime... boost::copy_n( input, 9, std::ostream_iterator<int>(std::cout, ",")); Unlike the following that runs ok... boost::copy( input | bounded(9), std::ostream_iterator<int>(std::cout, ",")); // prints 1,2,3,4,5,7,8,9, This behavior could be equated using *sliced(0, X)*, but sliced requires *RandomAccessRange*, unlike bounded that requires *SinglePassRange*. *bounded* code is based on *indexed* adaptor code, I think it is more efficient than *sliced* ( that uses *make_iterator_range* --> std::advance ). I don't know if this behavior can be achieved using other adapters, if so, please let me know. Is there interest in this for Boost? Regards, Fernando.

5 12

[lockfree] review
by Gordon Woodhull 05 Nov '11

05 Nov '11

Hi Tim, Hopefully I'll have at least a partial review. I only know enough about the subject to be a little dangerous. (One course in concurrent data structures, one successfully implemented lockfree hash table - except for the memory reclamation. Unspecified barriers and ABA problems. :p ) Considering the difficulty of the subject, you seem to have carefully chosen a small set of algorithms where at least there is consensus that the sources you are using have solved the problem correctly. I apologize if this has already been covered, but I don't see anything in the documentation about which platforms and compilers this has been tested on. These algorithms are extremely susceptible to compiler and processor optimizations. Anyway, I thought I would try to run the tests, and maybe try changing the testing methodology a little, but I got a few compiler errors, below. Defining uint fixed most of these, but bench_1.cpp also appears to be out of date? Of course I also have my lack of understanding of boost build library linking to contend with. Hope to try again later. Cheers, Gordon ~/lib/boost_lockfree/libs/lockfree/test ~/src/boost-trunk grodo-mcwoohu:test gordon$ bjam ...found 141 targets... ...updating 21 targets... darwin.compile.c++ ../../../bin.v2/libs/lockfree/test/bench_1.test/darwin-4.5.3/debug/threading-multi/bench_1.o g++: unrecognized option '-no-cpp-precomp' bench_1.cpp: In function 'void test_fifo_pop()': bench_1.cpp:67:23: error: no matching function for call to 'boost::lockfree::fifo<long int>::dequeue(long int*)' ../../../boost/lockfree/fifo.hpp:214:10: note: candidate is: bool boost::lockfree::detail::fifo<T, freelist_t, Alloc>::dequeue(T&) [with T = long int, freelist_t = boost::lockfree::caching_freelist_t, Alloc = std::allocator<long int>] bench_1.cpp: In function 'void test_fifo_pop_unsafe()': bench_1.cpp:77:30: error: no matching function for call to 'boost::lockfree::fifo<long int>::dequeue_unsafe(long int*)' ../../../boost/lockfree/fifo.hpp:255:10: note: candidate is: bool boost::lockfree::detail::fifo<T, freelist_t, Alloc>::dequeue_unsafe(T&) [with T = long int, freelist_t = boost::lockfree::caching_freelist_t, Alloc = std::allocator<long int>] bench_1.cpp: In function 'void test_stack_pop()': bench_1.cpp:87:19: error: no matching function for call to 'boost::lockfree::stack<long int>::pop(long int*)' ../../../boost/lockfree/stack.hpp:179:10: note: candidate is: bool boost::lockfree::stack<T, freelist_t, Alloc>::pop(T&) [with T = long int, freelist_t = boost::lockfree::caching_freelist_t, Alloc = std::allocator<long int>] bench_1.cpp: In function 'void test_stack_pop_unsafe()': bench_1.cpp:97:26: error: no matching function for call to 'boost::lockfree::stack<long int>::pop_unsafe(long int*)' ../../../boost/lockfree/stack.hpp:207:10: note: candidate is: bool boost::lockfree::stack<T, freelist_t, Alloc>::pop_unsafe(T&) [with T = long int, freelist_t = boost::lockfree::caching_freelist_t, Alloc = std::allocator<long int>] "g++" -ftemplate-depth-128 -O0 -fno-inline -Wall -g -dynamic -no-cpp-precomp -gdwarf-2 -fexceptions -fPIC -I"../../.." -c -o "../../../bin.v2/libs/lockfree/test/bench_1.test/darwin-4.5.3/debug/threading-multi/bench_1.o" "bench_1.cpp" ...failed darwin.compile.c++ ../../../bin.v2/libs/lockfree/test/bench_1.test/darwin-4.5.3/debug/threading-multi/bench_1.o... ...skipped <p../../../bin.v2/libs/lockfree/test/bench_1.test/darwin-4.5.3/debug/threading-multi>bench_1 for lack of <p../../../bin.v2/libs/lockfree/test/bench_1.test/darwin-4.5.3/debug/threading-multi>bench_1.o... ...skipped <p../../../bin.v2/libs/lockfree/test/bench_1.test/darwin-4.5.3/debug/threading-multi>bench_1.run for lack of <p../../../bin.v2/libs/lockfree/test/bench_1.test/darwin-4.5.3/debug/threading-multi>bench_1... darwin.compile.c++ ../../../bin.v2/libs/lockfree/test/fifo_test.test/darwin-4.5.3/debug/threading-multi/fifo_test.o g++: unrecognized option '-no-cpp-precomp' fifo_test.cpp:103:18: error: 'uint' does not name a type fifo_test.cpp: In member function 'void fifo_tester<freelist_t>::add()': fifo_test.cpp:116:14: error: 'uint' was not declared in this scope fifo_test.cpp:116:19: error: expected ';' before 'i' fifo_test.cpp:116:26: error: 'i' was not declared in this scope fifo_test.cpp:116:31: error: 'nodes_per_thread' was not declared in this scope fifo_test.cpp: In member function 'void fifo_tester<freelist_t>::run()': fifo_test.cpp:187:1: error: 'nodes_per_thread' was not declared in this scope "g++" -ftemplate-depth-128 -O0 -fno-inline -Wall -g -dynamic -no-cpp-precomp -gdwarf-2 -fexceptions -fPIC -I"../../.." -c -o "../../../bin.v2/libs/lockfree/test/fifo_test.test/darwin-4.5.3/debug/threading-multi/fifo_test.o" "fifo_test.cpp" ...failed darwin.compile.c++ ../../../bin.v2/libs/lockfree/test/fifo_test.test/darwin-4.5.3/debug/threading-multi/fifo_test.o... ...skipped <p../../../bin.v2/libs/lockfree/test/fifo_test.test/darwin-4.5.3/debug/threading-multi>fifo_test for lack of <p../../../bin.v2/libs/lockfree/test/fifo_test.test/darwin-4.5.3/debug/threading-multi>fifo_test.o... ...skipped <p../../../bin.v2/libs/lockfree/test/fifo_test.test/darwin-4.5.3/debug/threading-multi>fifo_test.run for lack of <p../../../bin.v2/libs/lockfree/test/fifo_test.test/darwin-4.5.3/debug/threading-multi>fifo_test... darwin.link ../../../bin.v2/libs/lockfree/test/freelist_test.test/darwin-4.5.3/debug/threading-multi/freelist_test ld: library not found for -lboost_thread collect2: ld returned 1 exit status "g++" -o "../../../bin.v2/libs/lockfree/test/freelist_test.test/darwin-4.5.3/debug/threading-multi/freelist_test" "../../../bin.v2/libs/lockfree/test/freelist_test.test/darwin-4.5.3/debug/threading-multi/freelist_test.o" -lboost_thread -lboost_unit_test_framework -g ...failed darwin.link ../../../bin.v2/libs/lockfree/test/freelist_test.test/darwin-4.5.3/debug/threading-multi/freelist_test... ...skipped <p../../../bin.v2/libs/lockfree/test/freelist_test.test/darwin-4.5.3/debug/threading-multi>freelist_test.run for lack of <p../../../bin.v2/libs/lockfree/test/freelist_test.test/darwin-4.5.3/debug/threading-multi>freelist_test... darwin.compile.c++ ../../../bin.v2/libs/lockfree/test/ringbuffer_test.test/darwin-4.5.3/debug/threading-multi/ringbuffer_test.o g++: unrecognized option '-no-cpp-precomp' ringbuffer_test.cpp:209:14: error: 'uint' does not name a type ringbuffer_test.cpp: In member function 'void ringbuffer_tester::add()': ringbuffer_test.cpp:225:14: error: 'uint' was not declared in this scope ringbuffer_test.cpp:225:19: error: expected ';' before 'i' ringbuffer_test.cpp:225:26: error: 'i' was not declared in this scope ringbuffer_test.cpp:225:31: error: 'nodes_per_thread' was not declared in this scope ringbuffer_test.cpp: In member function 'void ringbuffer_tester::run()': ringbuffer_test.cpp:284:1: error: 'nodes_per_thread' was not declared in this scope ringbuffer_test.cpp: In member function 'void ringbuffer_tester_buffering::add()': ringbuffer_test.cpp:315:14: error: 'uint' was not declared in this scope ringbuffer_test.cpp:315:19: error: expected ';' before 'i' ringbuffer_test.cpp:315:26: error: 'i' was not declared in this scope ringbuffer_test.cpp:315:31: error: 'nodes_per_thread' was not declared in this scope ringbuffer_test.cpp: In member function 'void ringbuffer_tester_buffering::run()': ringbuffer_test.cpp:386:1: error: 'nodes_per_thread' was not declared in this scope

8 63

Re: [boost] [lockfree] review
by Boehm, Hans 05 Nov '11

05 Nov '11

[Dave Abrahams pointed me at this thread.] Alexander Terekhov <terekhov <at> web.de> writes: > > Dave Abrahams wrote: > > > > on Thu Aug 25 2011, Alexander Terekhov <terekhov-AT-web.de> wrote: > > > > > Ilya Sokolov wrote: > > >> > > >> > > >> AFAIK, in the example above another thread can't observe reordering > > >> without introducing UB. > > > > > > I meant "observed" as in "check the sequence of writes in the generated > > > code". > > > > Do we care about what the generated code looks like? IIUC what counts > > is the sequence of memory states that another another thread can see. > > > > > But int can be simply changed to relaxed atomic<int> so that another > > > thread can observe reordering without UB. > > > > Sure. > > I meant that for the example upthread, with an int instead of relaxed > atomic<int>, another thread's code triggering UB does not prevent us > from observing reordered writes in the writing thread's code (in > generated code), by looking at it. > > Changing int to relaxed atomic<int> simply removes UB but does not > change the relevant code in the writing thread. > > regards, > alexander. > I agree with Alexander and most of the recent postings. If I write mx.lock(); x = 1; mx.unlock(); my.lock(); y = 1; my.unlock(); There is nothing to prevent the stores to x and y from becoming visible out of order at the hardware level. Enforcing ordering here would add needless and substantial cost. But a data-race-free program cannot observe such reordering. (One reference for that is Sarita Adve's and my PLDI 08 paper. Unofficial TR version at http://www.hpl.hp.com/techreports/2008/HPL-2008- 56.html. I believe Mark Batty et al have a much more complete and formal proof.) If we change x and y to be atomic variables, and the stores to be memory_order_relaxed, then an observer can tell the difference. I.e. if x and y are initially zero, and another thread does r1 = y; r2 = x; (or the acquire versions), it can see r1 = 1 and r2 = 0, since there are no synchronizes-with relationships between threads, and thus nothing to enforce ordering. If you use memory_order_relaxed, or even the acquire/release forms, things do get MUCH more complicated. The equivalent rules for other languages are an interesting story. I believe Posix implentors assume the above rules. I have a PPoPP 2007 paper that explains why that's not exactly what Posix actually states. OpenMP 3.0 has stricter rules which are also not consistently obeyed, and are somewhat fixed in OpenMP 3.1. (See my MSPC 11 paper for some details.) Java has arguably the same rules as C++ in this respect. In my mind, the main way in which sequential consistency differs from the cheaper acquire/release semantics that Alexander wants is that a) Dekker's algorithm (which by itself isn't that practically interesting), plus a number of real lock-free algorithms (which do matter) don't work. b) In my mind, acquire/release is a far more difficult model to explain to non- experts than the model for C++ with only sequentially consistent atomics. You can no longer reason about interleaving thread actions, either for purposes of determining the existence of a data-race, nor when defining what data-race- free programs mean. This was extensively discussed in C++ meetings starting in about 2005. The current solution with default-sequentially-consistent atomics, but explicit support for weaker ordering, was the resulting committee compromise. Hans

6 19