April 2009 - Boost - lists.boost.org

[GSOC] Regarding the project Boost.DeVector
by Satyam Shekhar 04 Apr '09

04 Apr '09

Hi, I am interested in doing the Boost.DeVector project for GSOC 2009. I had certain queries regarding this project: 1. Does the standard specify any sort of implementation for deque, or does it only specify the requirements and interface? I ask this because if we assume a dynamic array implementation which grows on both the sides, implementing 'reserve', and specifying the size of the chunk should be a trivial task. 2. What are the examples of the low-level operations for which this container is over-encapsulated? Regards Satyam

6 14

[gsoc] Application period ends today / review period begins.
by troy d. straszheim 04 Apr '09

04 Apr '09

Student application period ends today at 19:00 UTC, 12 Noon PDT. Then we have until the 15th to review and rank all (over 50 as of now) student proposals and match them with mentors. -t

4 7

[serialization] serializing std::bitset
by Kenny Riddile 04 Apr '09

04 Apr '09

I need to serialize a std::bitset. I found an implementation by Brian Ravnsgaard Riis from 2006 in the vault that doesn't work with xml archives out of the box since it fails to use nvp wrappers internally. Should I just add the nvp wrappers or is there anything more current for serializing std::bitsets?

3 5

Release schedule
by Vladimir Prus 03 Apr '09

03 Apr '09

Hi, the calendar at http://www.boost.org/development/index.html has: 1.39.0 Closed for major code changes for today and: 1.39.0 Closed except by permission for next Friday, Apr 10th. I have a few questions: 1. Is this schedule still up-to-date? I did not notice any reminder emails. 2. I assume this refers to all commits to release branch? 3. What is 'major code change'. Will wholesale merge of Boost.Build count as one (though I'm not away of any disturbing changes on trunk). 4. Would it be possible to move both deadlines over the weekend to Apr 6 and Apr 13 respectively? I'm sure many developers have more spare time on weekend, so it will make it easier to complete changes. I, in particular, have some changes in pipeline to make building Boost less confusing for newcomers, and certainly will appreciate having that weekend of Apr 11-12. Thanks, Volodya

4 4

[statechart] Bug when switching inner-states?
by George van Venrooij 03 Apr '09

03 Apr '09

Hi, I have attached a test program that gives some curious results, indicating the statemachine does not reach its proper state when performing state changes in orthogonal regions. The machine attached contains a main state that handles an "update" event. That main state contains 2 inner states, one of which also handles the "update" event. If that inner state transits to another state and back again, the "update" event no longer arrives at it, which in my opinion is a bug. If I modify the state machine so it does not have 2 but only 1 inner state, then the behavior matches my expectations. Could someone please verify if this is bug or tell me if my usage scenerio is incorrect. Regards, George van Venrooij Organic Vectory http://www.organicvectory.com #include <boost/statechart/state_machine.hpp> #include <boost/statechart/event.hpp> #include <boost/statechart/simple_state.hpp> #include <boost/statechart/custom_reaction.hpp> #include <iostream> namespace bs = boost::statechart; using namespace std; // The main event, should be handles by a sub-state and the main state struct update_event; // An event triggering the sub-state to switch struct toggle_event; // A dummy event struct other_event; // Sub-states in 2 orthogonal regions struct state_1A; struct state_1B; struct state_2A; struct state_2B; // Main state struct parent_state; // State machine consisting of the main state struct machine : bs::state_machine<machine, parent_state> { }; typedef boost::mpl::list < state_1A , state_2A > inner_states_t; // The main state has 2 orthogonal sub-states struct parent_state : bs::simple_state<parent_state, machine, inner_states_t> { typedef boost::mpl::list < bs::custom_reaction <update_event> > reactions; bs::result react(const update_event&) { cout << __FUNCTION__ << endl; return discard_event(); } }; struct update_event : bs::event<update_event> { }; struct other_event : bs::event<other_event> { }; struct toggle_event : bs::event<toggle_event> { }; struct state_1A : bs::simple_state<state_1A, parent_state::orthogonal<0>> { typedef boost::mpl::list < bs::custom_reaction <toggle_event> , bs::custom_reaction <update_event> > reactions; state_1A() { cout << __FUNCTION__ << endl; } bs::result react(const toggle_event&) { cout << __FUNCTION__ << endl; return transit<state_1B>(); } bs::result react(const update_event&) { cout << __FUNCTION__ << endl; return forward_event(); } }; struct state_1B : bs::simple_state<state_1B, parent_state::orthogonal<0>> { typedef boost::mpl::list < bs::custom_reaction <toggle_event> > reactions; state_1B() { cout << __FUNCTION__ << endl; } bs::result react(const toggle_event&) { cout << __FUNCTION__ << endl; return transit<state_1A>(); } }; struct state_2A : bs::simple_state<state_2A, parent_state::orthogonal<1>> { typedef boost::mpl::list < bs::custom_reaction <other_event> > reactions; state_2A() { cout << __FUNCTION__ << endl; } bs::result react(const other_event&) { cout << __FUNCTION__ << endl; return discard_event(); } }; struct state_2B : bs::simple_state<state_2B, parent_state::orthogonal<1>> { typedef boost::mpl::list < bs::custom_reaction <other_event> > reactions; state_2B() { cout << __FUNCTION__ << endl; } bs::result react(const other_event&) { cout << __FUNCTION__ << endl; return discard_event(); } }; int main(int argc, char* argv[]) { machine m; cout << "0. Initiating state machine:" << endl; m.initiate(); cout << endl << "1. Processing 'other_event':" << endl; m.process_event(other_event ()); cout << endl << "2. Processing 'update_event':" << endl; m.process_event(update_event()); cout << endl << "3. Processing 'toggle_event':" << endl; m.process_event(toggle_event()); cout << endl << "4. Processing 'update_event':" << endl; m.process_event(update_event()); cout << endl << "5. Processing 'toggle_event':" << endl; m.process_event(toggle_event()); cout << endl << "6. Processing 'update_event':" << endl; m.process_event(update_event()); return 0; } ////////////////////////////////////////////////////////////////////////// // Program output after building with VC 9 and Boost 1.37.0 // // Note the different event handling in step 6. as compared to step 2. // although the machine should be back in the same state. ////////////////////////////////////////////////////////////////////////// /* 0. Initiating state machine: state_1A::state_1A state_2A::state_2A 1. Processing 'other_event': state_2A::react 2. Processing 'update_event': state_1A::react parent_state::react 3. Processing 'toggle_event': state_1A::react state_1B::state_1B 4. Processing 'update_event': parent_state::react 5. Processing 'toggle_event': state_1B::react state_1A::state_1A 6. Processing 'update_event': parent_state::react */

2 1

Mutex vs Semaphore
by Jean-Sebastien Stoezel 03 Apr '09

03 Apr '09

Hi, I need to synchronize 2 threads, that is once one is done doing something, it should activate another thread that had been waiting in a pending state. I see the thread library offers mutexes and nothing else. I guess mutexes would do, but I do not believe I should use mutexes for my application. Mutexes are supposed to provide mutual exclusion when critical data is accessed. Semaphores should be used for what I want to do. However, I only see semaphores available in the interprocess library. I only need inter-thread synchronization, and going the long way with the interprocess library seems a bit overkill. It may be an ideology issue here. I would appreciate your comments on what to use in this case. Thanks, Jean

4 5

[gsoc] Min Cost Flow in Boost Graph library
by shilp gupta 03 Apr '09

03 Apr '09

Hey, I am interested in contributing to the Boost Graph library with algorithms. Some of my suggestions are, - minimum cost flow - weighted bupartite matching - maximum flow (based on blocking flows) I had a few questions to ask, Is there any significant progress already in development or implementation of minimum cost flow algorithms in Boost? To the best of my knowledge, Boost does not have a structure for bipartite graphs. Would it be appreciated if I work on one? I know that these can be represented using standard graph structures without much loss, but the simplicity (and scope) of bipartite graph's can be used to reduce constants in the run times of algorithms on them - maximum flow using blocking flows infact runs in O(sqrt(V)E) time for calculating the maximum cardinality matching in the bipartite case. Thanks! Regards Shilp Gupta

2 1

BOOST::SIMD - handling double : precision vs speed
by Joel Falcou 03 Apr '09

03 Apr '09

SIMD algorithms for double precision seem to be rather hard to do right. It's difficult to get the right precision with respect to the scalar reference as scalar algorithm take advantages of the internal 80 bits floating points register, thus leading comparison between our implementation and the reference to yields things like 3000 ulp (ie 10^-13 RMS instead of 10^16). Fixing this is difficult and even if it's possible for some algorithms, the average speed-up then drop to less than 10% - ie as fast as an unrolled scalar call over the SIMD vector elements. What should we enforce : precision or speed ? Or is the 10^-13 RMS enough ? Of course, this is mostly a problem on current SIMD extension in which vector of double only have 2 elements. It may be different with upcoming AVX and Larabee featuring larger vectors. Discussions welcome. -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35

7 6

A Boost.NumericAdaptor library to support big numbers
by Bruno Lalande 02 Apr '09

02 Apr '09

Hello, Barend quickly talked about this in the discussion about robustness, big numbers and GMP. We have discussed about the idea and I'd like to present it here to see if there's an interest. The idea started from the need to rely on big numbers in geometry computations that are sensitive to floating point errors. The most important points were: - big numbers are needed for those computations - it's difficult to develop a Boost Big Numbers library as efficient as the existing ones - having a Boost geometry library that *necessarily* depends on an existing big numbers library would impose to the user the way in which big numbers must be handled, and would imply a dependency that apparently disturbs some people Thus we had the idea of using an adaptor, that is a wrapper that would have the same semantics as a number, with an underlying implementation chosen at compile-time, by selecting a policy. There would be a IEEE policy that doesn't use any big number at all, and other policies that would be implemented upon the most widely used big numbers libraries. In the end it appears that this adaptor could become a library on its own since it can be useful in other libraries than just geometry. It could thus take the form of a Boost.NumericAdaptor library, aimed to any library developer who needs to optionally enable the use of big numbers for the most robustness-sensible operations of his library. He would just have to take a policy as a template parameter, and propagate this policy to a Numeric Adaptor used internally. The first user of this library would obviously be the GGL we're developing. Libraries like the fixed-size matrix being currently discussed as a GSoC project could offer take advantage of this kind of library, since ideally it has to support big numbers. The sample in attachment shows the numeric_adaptor, a IEEE policy, a GMP policy and a sample showing the use of the library. The implementation has to evolve of course, but the main points are here. Would there be an interest in adding such a library into Boost? Bruno Lalande Barend Gehrels

7 10

Back to Boost.SIMD - Some performances ...
by Joel Falcou 02 Apr '09

02 Apr '09

I'm still working on a potential Boost.SIMD proposal despite the apparent lack of interest by the list. Last discussion spawned the fact that actual performances figures may be interesting. So here's some (see end of mail). This table show for a subset of non-trivial functions the cycles needed to compute one value in scalar, using SSE2, some precision concerns and the actual speed-up. Most of them are super-linear because either : 1/ libc algorithm is badly implemented, or 2/ non-SIMD architectural difference between SSE2 FPU and scalar FPU leads to additional speed-up Most transcendental functions used a SIMD evrsion of the old yet useful Cephes C library based around various polynomial estimations. Results on Altivec processor are roughly the same except for transcendental where the use of a proper FMA instead of sequence of mul-add increases performances.For trivial function like +,-,*,/, I was happily surprised that indeed gcc is able to generate SIMD code. Alas, gcc auto-SIMD speed-up never exceed 2.54 while our code can go up to 3.5. Concerning the problem of interface and support of odd-ball vector size in a platform independant fashion, we use the remark of Matthias and provide a vec<T,C> class in which the vector cardinal can be speficified (and is equal to the native cardinal of said type by default). Things like vec<double,5> are handled as boost::array and provide same interface and set of functions. for any given functions, it cna be applied either to any vec<T,C> types or any native SIMD type (__m128 in SSEx or vector xxx in Altivec). Syntaxic sugar like v = v+4 is provided and perform consatnt splatting before SIMD evaluation. This still has to be boostified and made independant of the whole project it depends on. Once done, a preliminary version will be uploaded into the Vault. Current target architecture are : - SSE2, SSSE3,SSE3 - AltiVec for PPC and Cell processor (a patched version of boost is needed) Comments and questions welcomed. || -------------- || --------------- || scalar || -------------- vector ---------------- || ---- || || || || cycles ||cycles | ulp | rms | peak || s-up || || --------------------------------------------------------------------------------------------- || || abs_ || float || 2.0 || 0.8 | 0 | 0.00e+00 | 0.00e+00 || 2.4 || || acosh_ || float || 148.2 || 30.2 | 1 | 9.15e-09 | 1.19e-07 || 4.9 || || acos_ || float || 261.8 || 14.7 | 3 | 7.01e-08 | 2.38e-07 || 17.8 || || arg_ || float || 5.0 || 1.2 | 0 | 0.00e+00 | 0.00e+00 || 4.2 || || asinh_ || float || 152.8 || 32.4 | 1 | 1.22e-08 | 1.19e-07 || 4.7 || || asin_ || float || 256.5 || 11.6 | 2 | 5.32e-08 | 2.28e-07 || 22.1 || || atanh_ || float || 123.9 || 20.4 | 2 | 2.27e-08 | 4.55e-07 || 6.1 || || atan_ || float || 160.7 || 12.7 | 1 | 3.55e-08 | 6.74e-08 || 12.7 || || bitofsign_ || float || 5.1 || 0.8 | 0 | 0.00e+00 | 0.00e+00 || 6.1 || || boolean_ || float || 5.4 || 1.0 | 0 | 0.00e+00 | 0.00e+00 || 5.4 || || cbrt_ || float || 152.5 || 39.7 | 1 | 2.76e-08 | 7.77e-08 || 3.8 || || ceil_ || float || 16.6 || 2.8 | 0 | 0.00e+00 | 0.00e+00 || 5.9 || || cosh_ || float || 211.5 || 19.1 | 2 | 4.00e-08 | 1.83e-07 || 11.1 || || cos_ || float || 112.2 || 14.6 | 1 | 2.98e-08 | 1.11e-07 || 7.7 || || cospi_ || float || 103.6 || 12.1 | 1 | 3.43e-08 | 1.19e-07 || 8.6 || || cot_ || float || 142.8 || 17.8 | 3 | 5.54e-08 | 2.38e-07 || 8.0 || || cotpi_ || float || 142.1 || 17.1 | 6 | 9.62e-08 | 4.08e-07 || 8.3 || || exp10_ || float || 169.3 || 32.1 | 1 | 2.88e-08 | 1.19e-07 || 5.3 || || exp_ || float || 171.3 || 19.3 | 1 | 2.60e-08 | 1.19e-07 || 8.9 || || expm1_ || float || 294.1 || 42.6 | 3 | 2.89e-08 | 1.94e-07 || 6.9 || || floor_ || float || 16.9 || 2.7 | 0 | 0.00e+00 | 0.00e+00 || 6.4 || || gd_ || float || 602.4 || 35.8 | 3 | 3.93e-08 | 2.46e-07 || 16.8 || || indeg_ || float || 2.2 || 0.8 | 0 | 2.59e-08 | 5.94e-08 || 2.7 || || inrad_ || float || 2.2 || 0.8 | 0 | 2.53e-08 | 5.94e-08 || 2.6 || || iseqz_ || float || 5.5 || 0.9 | 0 | 0.00e+00 | 0.00e+00 || 6.3 || || iseven_ || float || 45.0 || 2.3 | 0 | 0.00e+00 | 0.00e+00 || 19.9 || || isfin_ || float || 5.9 || 0.9 | 0 | 0.00e+00 | 0.00e+00 || 6.6 || || isflint_ || float || 38.3 || 1.8 | 0 | 0.00e+00 | 0.00e+00 || 21.4 || || isgez_ || float || 6.0 || 0.8 | 0 | 0.00e+00 | 0.00e+00 || 7.4 || || isgtz_ || float || 6.0 || 0.9 | 0 | 0.00e+00 | 0.00e+00 || 6.5 || || isinf_ || float || 6.0 || 0.9 | 0 | 0.00e+00 | 0.00e+00 || 6.5 || || islez_ || float || 5.0 || 0.9 | 0 | 0.00e+00 | 0.00e+00 || 5.8 || || isltz_ || float || 5.0 || 0.9 | 0 | 0.00e+00 | 0.00e+00 || 5.8 || || isnan_ || float || 3.0 || 0.8 | 0 | 0.00e+00 | 0.00e+00 || 3.6 || || isnegative_ || float || 5.6 || 1.1 | 0 | 0.00e+00 | 0.00e+00 || 5.0 || || isnez_ || float || 5.4 || 0.9 | 0 | 0.00e+00 | 0.00e+00 || 6.2 || || isnotfinite_ || float || 3.0 || 0.8 | 0 | 0.00e+00 | 0.00e+00 || 3.6 || || isodd_ || float || 47.8 || 2.5 | 0 | 0.00e+00 | 0.00e+00 || 18.8 || || ispositive_ || float || 5.6 || 1.3 | 0 | 0.00e+00 | 0.00e+00 || 4.2 || || log10abs_ || float || 107.5 || 17.3 | 2 | 6.59e-08 | 2.12e-07 || 6.2 || || log10_ || float || 105.4 || 16.9 | 2 | 6.58e-08 | 2.12e-07 || 6.2 || || log1p_ || float || 149.7 || 18.8 | 1 | 9.16e-09 | 1.19e-07 || 8.0 || || log2abs_ || float || 107.5 || 17.2 | 1 | 1.89e-08 | 1.19e-07 || 6.3 || || log2_ || float || 105.5 || 17.1 | 4 | 1.90e-08 | 2.51e-07 || 6.2 || || logabs_ || float || 107.5 || 23.6 | 1 | 4.36e-08 | 1.19e-07 || 4.6 || || log_ || float || 108.3 || 15.4 | 1 | 9.12e-09 | 1.19e-07 || 7.0 || || mantissa_ || float || 22.1 || 5.0 | 0 | 0.00e+00 | 0.00e+00 || 4.4 || || oneminus_ || float || 3.3 || 0.8 | 0 | 5.16e-10 | 5.96e-08 || 4.0 || || oneplus_ || float || 3.4 || 0.8 | 0 | 2.87e-10 | 5.74e-08 || 4.1 || || rec_ || float || 37.4 || 4.3 | 0 | 2.48e-08 | 5.92e-08 || 8.8 || || round_ || float || 43.7 || 5.5 | 0 | 0.00e+00 | 0.00e+00 || 8.0 || || rsqrt_ || float || 105.4 || 11.3 | 1 | 3.62e-08 | 8.81e-08 || 9.3 || || signedbool_ || float || 9.3 || 0.9 | 0 | nan | 0.00e+00 || 10.6 || || sign_ || float || 12.1 || 2.5 | 0 | 0.00e+00 | 0.00e+00 || 4.9 || || signnz_ || float || 12.1 || 1.4 | 0 | 0.00e+00 | 0.00e+00 || 8.5 || || sinh_ || float || 267.2 || 19.1 | 3 | 2.38e-07 | 3.84e-07 || 14.0 || || sin_ || float || 110.5 || 17.0 | 1 | 2.98e-08 | 1.12e-07 || 6.5 || || sinpi_ || float || 115.8 || 14.4 | 1 | 2.98e-08 | 1.10e-07 || 8.0 || || sqr_ || float || 2.0 || 0.7 | 0 | 2.53e-08 | 5.94e-08 || 2.9 || || sqrt_ || float || 68.3 || 7.1 | 0 | 2.62e-08 | 5.96e-08 || 9.6 || || sqrtabs_ || float || 68.3 || 7.0 | 0 | 2.61e-08 | 5.96e-08 || 9.7 || || tanh_ || float || 206.4 || 20.8 | 197 | 1.63e-07 | 1.77e-05 || 9.9 || || tan_ || float || 153.0 || 17.8 | 2 | 4.18e-08 | 1.45e-07 || 8.6 || || tanpi_ || float || 156.2 || 18.0 | 2 | 4.16e-08 | 1.48e-07 || 8.7 || || --------------------------------------------------------------------------------------------- || -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35

9 23