- Boost - lists.boost.org

[atomic] review results
by Tim Blechmann 07 Nov '11

07 Nov '11

hi all, unfortunately only few reviews of boost.atomic arrived in time, however i count 3 YES and no NO, so i am happy to say: Helge Bahmann's boost.atomic library is ACCEPTED. since the library is an implementation of a c++11 feature for c++03, design, API and semantics are mostly fixed. many comments are going into details of the implementation, so i won't sum them all up ... iac, helge already said he wants to address the raised issues, the main points are summarized below. full implementation of the c++11 interface: the library currently only implements a subset of the c++11 library. it lacks the functional interface for integral atomic types and the ATOMIC_VAR_INIT / ATOMIC_FLAG_INIT macro. quickly consulting the latest draft that i currently have at hand the following two functions are missing as well: template <class T> T kill_dependency(T y); void atomic_signal_fence(memory_order); i encourage helge to provide a full implementation of the interface. documentation: the documentation is currently lacking a good API reference. i would therefore encourage helge to provide a doxygen-generated reference section. there were some concerns that it assumes that readers will have to be familiar with concurrency. maybe it is a good idea to point to some literature/tutorials about concurrent programming and/or to c++11 atomics. the section of real-world examples could probably include a link to shavit/herlihy's book `the art of multiprocessor programming'. it would also be helpful to have a detailed specification, if a platform/compiler combination supports a specific type natively (with run-time dispatching or specific compiler flags) ... maybe in form of a table. shared memory support/multi-module support: in multi-module applications and when using shared memory, the blocking emulation of atomics can cause troubles. for multi-module applications this can be resolved by placing the spinlock pool inside a shared library. shared- memory support could be realized by associating a (spin)lock with each blocking atomic<> instead of using a pool of spinlocks. boost should definitely provide atomics which support shared memory, either by default or by an additional implementation which is placed in the boost::interprocess namespace. i would like to thank helge for implementing boost.atomic and submitting it to boost and everyone who participated in the review. cheers, tim review manager

4 4

[smart_ptr] Please merge 5327
by Steve M. Robbins 07 Nov '11

07 Nov '11

Peter Dimov, When you have a moment, could you merge the patch in ticket https://svn.boost.org/trac/boost/ticket/5327 It should be safe enough; Debian has been using this since August 2009. Thanks, -Steve

2 1

[parameter] named template parameters
by Lorenzo Caminiti 07 Nov '11

07 Nov '11

Hello all (and especially Boost.Parameter's authors), The Boost.Parameter docs suggest to implement parameter-enabled class templates using a series of typedes for the argument pack and the actual argument types. I think it is best to define extra template parameters with default values to old the argument pack Args and named template parameters ClassType, etc as shown below. This allows to use the named template parameters within the class declaration for example in a base class (boost::python::class_<ClassType, ...>) instead that just in the class definition. Do you see any problem in using extra template parameter to define the argument pack and named template parameters? #include <boost/parameter.hpp>#include <boost/python/class.hpp>#include <boost/type_traits/is_class.hpp>#include <boost/type_traits/is_base_and_derived.hpp>#include <boost/mpl/is_sequence.hpp>#include <boost/mpl/placeholders.hpp>#include <boost/mpl/not.hpp>#include <boost/mpl/and.hpp>#include <boost/noncopyable.hpp>#include <boost/shared_ptr.hpp> namespace py { namespace detail { struct bases_tag {}; } template< class B0 = void, class B1 = void, class B2 = void >struct bases : detail::bases_tag {}; BOOST_PARAMETER_TEMPLATE_KEYWORD(ClassType) BOOST_PARAMETER_TEMPLATE_KEYWORD(BaseList)BOOST_PARAMETER_TEMPLATE_KEYWORD(HeldType)BOOST_PARAMETER_TEMPLATE_KEYWORD(Copyable) template< typename Arg123X0 , typename Arg123X1 = boost::parameter::void_ , typename Arg123X2 = boost::parameter::void_ , typename Arg123X3 = boost::parameter::void_ , typename Args123 = typename boost::parameter::parameters< // IF(IS_EMPTY(DEFAULT(p)), required, optional) boost::parameter::required< tag::ClassType , boost::is_class<boost::mpl::_> > , boost::parameter::optional< // IF(IS_DEDUCED(p), deduced<tag::NAME(p)>, tag::NAME(p)) boost::parameter::deduced<tag::BaseList> // COMMA_IF(COMPL(IS_EMPTY(REQUIRES(p)))) REQUIRES(p) , boost::is_base_and_derived<detail::bases_tag, boost::mpl::_> > , boost::parameter::optional< boost::parameter::deduced<tag::HeldType> , boost::mpl::not_< boost::mpl::or_< boost::is_base_and_derived<detail::bases_tag, boost::mpl::_> , boost::is_same<boost::noncopyable, boost::mpl::_> > > > , boost::parameter::optional< boost::parameter::deduced<tag::Copyable> , boost::is_same<boost::noncopyable, boost::mpl::_> > >::bind<Arg123X0, Arg123X1, Arg123X2, Arg123X3>::type , typename ClassType = typename boost::parameter::value_type< Args123, tag::ClassType >::type , typename BaseList = typename boost::parameter::value_type< // ... COMMA_IF(COMPL(IS_EMPTY(DEFAULT(p)))) DEFAULT(p) >::type Args123, tag::BaseList, bases<> >::type , typename HeldType = typename boost::parameter::value_type< Args123, tag::HeldType, ClassType >::type , typename Copyable = typename boost::parameter::value_type< Args123, tag::Copyable, void >::type>struct class_ : boost::python::class_<ClassType, BaseList, HeldType, Copyable>{ typedef ClassType class_type; typedef BaseList base_list; typedef HeldType held_type; typedef Copyable copyable;}; } // namespace py struct b { virtual ~b() = 0; }; struct d : b { ~d() {} }; // Named parameters.typedef py::class_< py::ClassType<b>, py::Copyable<boost::noncopyable> > x1;typedef py::class_< d, py::HeldType< boost::shared_ptr<d> >, py::BaseList< py::bases<b> > > x2;// Deduced parameters.typedef py::class_< b, boost::noncopyable > y1;typedef py::class_< d, boost::shared_ptr<d>, py::bases<b> > y2; A couple more things: 1) I thing that BOOST_PARAMETER_TEMPLATE_KEYWORD(ClassType) macro should define a symbol _ClassType to be used for the named parameter so to be consistent with the BOOST_PARAMETER_NAME(x) which defined _x to be used for the named function parameter. However, ClassType is defined without the leading _. What is the reason for this asymmetry? 2) I'd expect a macro that allows to specify tag and passing argument name for template parameters BOOST_PARAMETER_TEMPLATE_KEYWORD((PassClassType, mytag) ClassType) as for BOOST_PARAMETER_NAME((pass_x, mytag) x) does for function parameters. Why is such a usage of BOOST_PARAMETER_TEMPLATE_KEYWORD not supported? Thanks a lot. --Lorenzo

4 10

[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

[python] Please apply and merge 2208
by Steve M. Robbins 07 Nov '11

07 Nov '11

Hi, The patch has been used in Debian since August 2008 so it should be safe to apply. Thanks, -Steve

1 0

[units] spatial coordinates, vectors, x, y, z, something like that
by Janek Kozicki 06 Nov '11

06 Nov '11

Hi, I want to use boost::units to calculate diffraction & interference patterns and wave propagation in 3D. I need some way to represent points in spatial 3D space with 'length' dimension. What do you guys use for that? I need them to work with 'frequency' & 'speed' dimensions also. Don't tell me that I need to write my own 'vector' class ? best regards -- Janek Kozicki http://janek.kozicki.pl/ |

2 2

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

[parameter] aux_/void.hpp: potential undefined behavior
by Krzysztof Czainski 05 Nov '11

05 Nov '11

Hello, Here's boost/aux_/void.hpp contents, without include quards and license note, where I marked a line with a comment to refer to it below. [code] namespace boost { namespace parameter { // A placemarker for "no argument passed." // MAINTAINER NOTE: Do not make this into a metafunction struct void_ {}; namespace aux { inline void_& void_reference() { static void_ instance; // (1) return instance; } } // namespace aux }} // namespace boost::parameter [/code] My question is: is it allowed to use an instance of an uninitialized empty struct? The struct void_ is empty. On line (1) a static uninitialized instance of struct void_ is defined, and it is then returned. Does the standard allow this? I can't imagine any real problems with this, but I'm curious if this has defined behavior according to the standard. A natural and simple solution to my concern is of course to change the line (1) to: static void_ instance = {}; I'd be happy to create a ticket with a patch, if my concern is valid. Regards, Kris

3 5

[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