February 2010 - Boost - lists.boost.org

Re: [boost] [contract] Released Contract Programming Library on SourceForge
by Andrzej Krzemienski 21 Mar '10

21 Mar '10

> I have released on SourceForge a library that implements Contract > Programming (a.k.a. Design by Contract(TM) ) for C++. I am considering > to submit this library to Boost (as Boost.Contract). > Comments? Hi, Just another thought for a tiny extension that came to my mind. I tried to use the block invariant as a regular assert: int main() { CONTRACT_ASSERT_BLOCK_INVARIANT( fee fee fee ); } This code compiles and works fine. This is because "disabling block invariants" means that the entire macro invocation will disappear, inclusive of the nonsense I wrote inside. We are used to it because this is how C-style asserts work, but one of the advantage of asserts over comments, as it is often advertised, is that the predicates are checked for syntactic and (to some extent) semantic correctness. But this is not the case if we disable the assertion macros. I believe, it would be useful if "disabling block invariants" meant no run-time overhead, but still checking syntactic correctness. It would be possible if the macro CONTRACT_ASSERT_BLOCK_INVARIANT( expression ); were replaced with something like: ... sizeof( expression ) ... then, the expression is not evaluated, but required to be correct. If the value of sizeof is not used it should be eliminated by the compiler. Obviously, the same would be applicable for all the other types of checks, Regards, &rzej

2 2

[unordered] unordered_set::erase() complexity bug?
by Stefan Strasser 18 Mar '10

18 Mar '10

I think there is something very wrong with boost's implementation of unordered_set/map. 1 unordered_set<int> s; 2 for(int c=0;c<nr;++c) s.insert(c); 3 for(int c=nr-1;c>=0;--c) s.erase(s.find(c)); results: nr: time 20000: 0m0.244s 40000: 0m0.940s 60000: 0m5.584s 80000: 0m4.232s 100000: 0m34.814s 120000: 0m33.486s the function that's causing this is erase(), which is specified to be O(1) average, O(n) worst. I can't think of a reason why it should be O(n) in this case (perfect hash, erase doesn't rehash). but even if it was, the results should be at worst quadratic. load_factor() is below 1, bucket_count(x) is 1. if line 3 is changed to: 3 for(int c=0;c<nr;++c) s.erase(s.find(c)); 20000: 0m0.008s 40000: 0m0.016s 60000: 0m0.028s 80000: 0m0.032s 100000: 0m0.040s 120000: 0m0.044s as you would expect. even if I do the very same thing as above using Boost.Intrusive (using a load factor of 1), I get expected results: struct element : intrusive::unordered_set_base_hook<>{ ... for(int c=0;c<nr;++c) s.insert(*new element(c)); for(int c=nr-1;c>=0;--c) s.erase(s.find(element(c))); 20000 0m0.008s 40000 0m0.016s 60000 0m0.024s 80000 0m0.024s 100000 0m0.032s 120000 0m0.040s but surprisingly enough, the TR1 implementation shipped with libstdc++ also has a problem like that: 20000: 0m0.368s 40000: 0m1.448s 60000: 0m1.668s 80000: 0m7.160s 100000: 0m7.808s 120000: 0m13.349s am I missing something or is there really the same bug in 2 major implementations of unordered_set? it effectively caused a deadlock in some of my code. I'm using 1.38. no bug report in Trac.

20 48

Status of (boost) lockfree?
by Emil Dotchevski 13 Mar '10

13 Mar '10

I decided to give the lockfree library that's currently in the review queue a try. On MSVC 9.0, I'm getting this error: boost\lockfree\detail\cas.hpp(129) : error C2440: 'reinterpret_cast' : cannot convert from 'const boost::uint64_t' to 'LONGLONG' The compiler then continues to say: Conversion is a valid standard conversion, which can be performed implicitly or by use of static_cast, C-style cast or function-style cast Am I missing a configuration macro, or is this a valid compile error? Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode

4 5

[inspect] More changes to Inspection Report
by Beman Dawes 10 Mar '10

10 Mar '10

More changes to the Inspection Report: * Line numbers are now shown when a problem is associated with a specific line in a file. * Apple macros clashes now show the specific name causing the problem. * Spacing is optimized so that problems without line numbers don't take up so much report space. See the results at http://boost.cowic.de/rc/inspect-trunk.html Thanks to everyone who commented yesterday! --Beman

6 6

enable_shared_from_this2
by Berserker 10 Mar '10

10 Mar '10

After experiencing some troubles with boost::python and enable_shared_from_this (as already reported in the past by someone to Peter Dimov), I started looking at the new (not documented) class enable_shared_from_this2. I made two changes in init_weak_once and now it seems to support shared_from_this in constructors and shared pointers "reinitialization". The original code (from boost 1.40): void init_weak_once() const { if( weak_this_._empty() ) { shared_this_.reset(static_cast< T* >( 0 ), detail::esft2_deleter_wrapper()); weak_this_ = shared_this_; } } The "patched" code: void init_weak_once() const { // Reinitialization support if( weak_this_.expired() ) { // shared_from_this in costructors support shared_this_.reset(static_cast <T*>(const_cast<enable_shared_from_this2>(this)), detail::esft2_deleter_wrapper()); weak_this_ = shared_this_; } } I know that the static_cast/const_cast is "problematic" on VC6 (and maybe other compilers) but it could be solved using an offset from enable_shared_from_this2 * to T *. I've attached a testcase that shows the problems with the current enable_shared_from_this2 implementation (with the proposed patch it works). Any feedback about this? struct null_deleter { template <typename T> inline void operator()(T *p) const { } }; class EnableThisPtrTester : public boost::enable_shared_from_this2<EnableThisPtrTester> { public: EnableThisPtrTester() { } EnableThisPtrTester(shared_ptr<EnableThisPtrTester> &ptr) { ptr = shared_from_this(); BOOST_CHECK(ptr); } }; BOOST_AUTO_TEST_CASE(test_enable_this_ptr) { { shared_ptr<EnableThisPtrTester> ptr1; shared_ptr<EnableThisPtrTester> ptr2(new EnableThisPtrTester(ptr1)); BOOST_CHECK(ptr1 == ptr2); BOOST_CHECK(ptr1.use_count() == ptr2.use_count()); BOOST_CHECK(ptr1->shared_from_this() == ptr1); BOOST_CHECK(ptr1->shared_from_this().use_count() == ptr1.use_count()); shared_ptr<EnableThisPtrTester> ptr3 = ptr2->shared_from_this(); BOOST_CHECK(ptr2 == ptr3); BOOST_CHECK(ptr2.use_count() == ptr3.use_count()); BOOST_CHECK(ptr1->shared_from_this().use_count() == ptr1.use_count()); } { shared_ptr<EnableThisPtrTester> ptr1; EnableThisPtrTester tester(ptr1); shared_ptr<EnableThisPtrTester> ptr2 = tester.shared_from_this(); BOOST_CHECK(ptr1 == ptr2); BOOST_CHECK(ptr1.use_count() == ptr2.use_count()); ptr1.reset(); ptr2.reset(); } { EnableThisPtrTester tester; { shared_ptr<EnableThisPtrTester> ptr1 = tester.shared_from_this(); shared_ptr<EnableThisPtrTester> ptr2 = tester.shared_from_this(); BOOST_CHECK(ptr1 == ptr2); BOOST_CHECK(ptr1.use_count() == ptr2.use_count()); shared_ptr<EnableThisPtrTester> ptr3(&tester, null_deleter()); BOOST_CHECK(ptr1 == ptr3); BOOST_CHECK(ptr1.use_count() == ptr3.use_count()); shared_ptr<EnableThisPtrTester> ptr4 = tester.shared_from_this(); BOOST_CHECK(ptr4 == ptr1); BOOST_CHECK(ptr4 == ptr3); BOOST_CHECK(ptr1.use_count() == ptr4.use_count()); BOOST_CHECK(ptr3.use_count() == ptr4.use_count()); } BOOST_CHECK(tester.shared_from_this()); } }

7 22

is review system in place is extremely slow? (was Re: [rfc] rcpp)
by vicente.botet 08 Mar '10

08 Mar '10

Hi, ----- Original Message ----- From: "Mathias Gaunard" <mathias.gaunard(a)ens-lyon.org> To: <boost(a)lists.boost.org> Sent: Tuesday, February 23, 2010 12:47 PM Subject: Re: [boost] [rfc] rcpp > > Ivan Sorokin wrote: >> 3 When will Boost.Move become a part of boost? > > When it gets reviewed. > It could be said, however, that the review system in place is extremely > slow and that it's going to take years (literally). Why do you think the review system in place is extremely slow? Currently there are a lot of libraries to review, but no review managers. That means that the user community don't want to spend a little bit of their time to manage a review. In addition, the last review didn't had too much of reviewers (I'm also concerned by this point) I'm the review manager of Boost.Task but the library is not ready for review, because now Boost.Task depends on Boost.Move, Boost.Fiber and Boost.Atomic (which is not yet on the review queue). Maybe the review withards could add this on the schedule page. What do you propose to improve it? Best, _____________________ Vicente Juan Botet Escribá

32 87

[Tokenmap] A (perfect) hash container library chcked-in to sandbox (RFC)
by Slawomir Lisznianski 08 Mar '10

08 Mar '10

http://svn.boost.org/svn/boost/sandbox/tokenmap/libs/tokenmap/doc/html/inde… A tokenmap is a data structure that uniquely maps pseudo-random generated keys with elements of the collection. Boost.Tokenmap is a (perfect) hash container library for C++. An important distinction between tokenmap and other dictionary-like containers, such as std::map or Boost.Unordered, is that tokenmap generates keys internally (referred to as "tokens") rather than relying on user to provide them. Specifically, when a new element is inserted into the tokenmap, an apparently random key is returned back to the caller which uniquely maps to the stored element. The returned key can later be used in a very efficient lookup. Although the code and documentation are far from complete, the implementation in the repo is functional and hopefully serves as a basis for further work. Slawomir

9 27

[Itl] Review
by Phil Endecott 08 Mar '10

08 Mar '10

My review of the proposed Interval Template Library follows. This is based only on studying the documentation, and previous discussion of the library on the Boost mailing list (e.g. http://lists.boost.org/Archives/boost/2009/03/149396.php ). Joachim has clearly put a lot of work into what is a substantial and well-documented library. Unfortunately, it seems to me that it is built on a weak foundation. One of the most well-known problems involving intervals is to determine which of a given set of intervals contains a particular point. How to store a set of intervals in such a way as to make this problem efficient has been extensively studied. If an "interval tree" (See e.g. Wikipedia: http://en.wikipedia.org/wiki/Interval_tree) is used, then the problem can be answered in logarithmic time and linear space. (More precisely: if there are N intervals in the container and M overlap the point of interest, finding them should take O(M + log N) time and the data structure should take O(N) space.) I was hoping to find that this library was an implementation of an interval tree. But it is not: it is built on top of normal standard-library containers. The implementation used can find the intervals that overlap a point in O(M + log N) time, but to do so it needs worst-case O(N^2) space and I think it needs O(N^2 log N) time to build that structure. Presumably this complexity is not an issue in Joachim's application. Unfortunately, library code will be used in many different applications including those where optimal complexity is required. For example, consider trying to store the lifespans of people in a genealogy program: recording a few thousand people living over a few hundred years would approach the worse-case space complexity and need megabytes of storage. Perhaps other reviewers will feel that there are sufficient applications where this library is suitable to justify its inclusion in Boost. My feeling is that since the interval tree data structure is so well known and its performance is so much better, we should not accept this library. Ideally it would be possible for Joachim to replace ITL's current standard containers with an interval tree implementation. Could an interval tree be implemented with an interval sufficiently similar to a std::set/map to make that possible, without losing the complexity benefits? Once again, I believe that apart from this weak foundation this looks like an excellent submission that is comprehensive and well-documented. Regards, Phil.

3 9

[Review] ITL review starts today, February 18th
by Hartmut Kaiser 08 Mar '10

08 Mar '10

Hi all, The formal review of the Interval Template Library (ITL) starts today, February 18th, 2010 and will end February 27th, 2010. ITL is being developed by Joachim Faulhaber. ------------------------------------------------ About the library: The Interval Template Library (ITL) is a library of interval containers that facilitates computations on collections of intervals and associated values. Use cases of such computations typically occur in the date and time problem domain, when collections of time intervals with associated data are analyzed, combined and aggregated. But the scope of applications for interval containers is more general and not limited to date and time problems. Interval containers allow to access and manipulate collections of intervals on an abstract level as sets and maps (of elements), but also to exploit segmental information that is given by the interval borders. Interval containers are fairly generic. They can be instantiated with discrete domain (or key) types like integral numeric types or boost::date or time types. But they also work with continuous domain types like double, rational or string. Using the latter allows to represent infinite sets and maps. The interface of the interval containers strives to be very intuitive and in line with the stl and other boost libraries. * The set theoretic operations union, difference, intersection and symmetric difference are available as operators for all interval containers and for many useful overloads between them. * There is iterator support on the level of segments and interval containers can be combined with stl containers of intervals via stl algorithms. * For discrete domain types, element iterators are available which makes interval sets and maps models of SortedAssociative Containers so they can be used with many stl algorithms. All interval containers are addable and subtractable. The addability and subtractability concept of the ITL leads to a general mechanism of aggregation on interval_maps which is called 'aggregate on overlap'. Exploiting 'aggregate on overlap' allows to compute many useful aggregation results in a simple and abstract manner. The ITL's Set and Map concepts are defined by a signature and collections of laws or axioms. Those semantical constraints have been validated using automatic law based tests. This gives the library both a well founded formal specification and an unusual thorough test base. The ITL emerged out of real world use cases and is successfully used at Cortex Software GmbH since a couple of years in the production code of various applications. On the boost developer's list it has been proposed in four previews and a review request since May 2008 and has been refactored and refined according to boost standards and suggestions from the list. The ITL is available from the boost vault: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_3_2 _0.zip&directory=Containers Documentation is online available at: http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html The current sources are in the sandbox: https://svn.boost.org/svn/boost/sandbox/itl/ ------------------------------------------------ Everybody on this list is invited to participate in this formal review. I hope to see your review of this library, including your vote, and I welcome your participation in the discussions on the Boost mailing list. Please always state in your review, whether you think the library should be accepted as a Boost library. Additionally, please consider giving feedback on the following general topics: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain? Regards Hartmut Review Manager --------------- Meet me at BoostCon www.boostcon.com

9 29

[transact] Handling with user exceptions
by vicente.botet 07 Mar '10

07 Mar '10

Hi, I would like to initiate a discussion on how to manage with user exceptions. Here follows some thougth I'm implementing in Boost.STM. There are two main ways to manage with user exceptions: * exceptions commit transactions - corresponds to the current C++ behavior * exceptions abort on exit - corresponds to rollback The behavior associated to the curent language-like macros is to throw the catched exception. In this case, the exception shouldn't contain references to transaction specific objects. I was wondering if we cannot add a second family of macros that before a user exception leaves the transaction block the transaction is commited. BOOST_TRANSACT_A_ family will abort the transaction on user exception BOOST_TRANSACT_C_ family will commit the transaction on user exception This will allows to explore which both approaches, and see which approach is more usable, or if there is an approach that is better adapted to some particuler contexts. * Exceptions Commit Transactions - How to get this? While trying to commit on destruction we have catched any exception to release the commit_on_destruction variable. commit_on_destruction __comm( __txn ) ; t ry { i f ( false ) ; else / / to for ce a sentence / / t r a n s a c t i o n sentence } catch ( . . . ) { __comm. release ( ) ; throw ; } To make exception commit transactions by default, we should not release the committer. However, we need to avoid exception throw by commit when the transaction has been set as forced to abort or during unwinding exception. commit_on_destruction __comm( __txn ) ; t ry { <sentence > } catch ( . . . ) { i f ( __txn_.forced_to_abort ( ) ) __comm.release ( ) ; else __comm.commit ( ) ; throw ; } We need how to override the default behavior. If we have Exceptions Commit Transactions - we can abort the transaction in two ways: * Explicit try-block to Abort Transactions * Explicitly abort before throw - Explicit try-block to Abort Transactions The user may want the exception abort the transaction while leaving the transaction block. The user must explicitly state that this is the desired behavior by adding a try-catch block as shown below: BOOST_STM_C_TRANSACTION t ry { / / t r a n s a c t i o n block } catch (Ex&) { BOOST_STM_ABORT( ) ; throw ; } BOOST_STM_C_END_TRANSACTION; - Explicitly abort before throw The user may want the transaction to be aborted before throwing an exception. The user may explicitly state that this is the desired either by setting the current transaction as forced to abort, BOOST_STM_ABORT( ) ; throw except ( ) ; or by throwing the exception using the macro : / / . . . BOOST_STM_ABORT_AND_THROW( except ( ) ) ; / / . . . If we have Exceptions Abort on Exit we can commit the transaction as follows: - Explicit try-block to Commit Transactions The user must explicitly state that this is the desired behavior by adding a try-catch block as shown below: BOOST_STM_TRANSACTION t ry { / / t r a n s a c t i o n block } catch (Ex &ex ) { BOOST_STM_COMMIT( ) ; throw ; } BOOST_STM_END_TRANSACTION; boost::exception_ptr error; BOOST_STM_TRANSACTION t ry { / / t r a n s a c t i o n block } catch (Ex &) { error=boost::current_exception(); } BOOST_STM_END_TRANSACTION; if( error) boost::rethrow_exception(error); } Please let me know what do you think? Do you find this useful? Should we provide two families of macros? Best regards, _____________________ Vicente Juan Botet Escribá

2 6