- Boost - lists.preview.boost.org

[documentation/doxygen] Incomplete header files names generated when the path contains twice boost
by Vicente Botet 16 Jun '11

16 Jun '11

Hi, While generating the Boost.Conversion documentation using quickbook and doxygen I have observed that the files named as doxygen boost : [ glob ../../../boost/conversion/boost/*.hpp ] Are expanded in the doc removing the path /boost/conversion. See http://svn.boost.org/svn/boost/sandbox/conversion/libs/conversion_ext/doc/h… Could something be done in order to correct this, or should I move the files to a directory that don't contains boost twice in the path? Any other workarounds? Any idea for a better name than boost? Best, Vicente http://svn.boost.org/svn/boost/sandbox/conversion/libs/conversion_ext/index… -- View this message in context: http://boost.2283326.n4.nabble.com/documentation-doxygen-Incomplete-header-… Sent from the Boost - Dev mailing list archive at Nabble.com.

3 3

[shared_ptr] Design question about make_shared
by Loïc Joly 16 Jun '11

16 Jun '11

Hello everybody, I recently wondered about the choice to make make_shared a free function, and not a static member function: struct A{...}; struct B:A {...}; shared_ptr<A> ptr = make_shared(arg1,arg2); vs shared_ptr<A> ptr = shared_ptr::make(arg1, arg2); I was wondering if this is just a stylistic choice, or if there are some differences? Thank you for any information. -- Loïc

8 17

[quickbook/doxygen] copydoc from internal header
by Tim Blechmann 16 Jun '11

16 Jun '11

hi all, preparing the docs of boost.heap, i came across one issue with the generation of the class reference: i have an internal header file, that should not be exposed to the class reference, but that needs to be parsed by doxygen (it contains a base class, which should be copied to its derived classes). however if i simply add it to the list of files to be parsed by bjam, it will be included into the reference (see [1]). is there any clean way to parse the file with doxygen but avoid it to be listed in the class reference? thanks, tim [1] http://tim.klingt.org/boost_heap/heap/reference.html

2 2

[gsoc] boost.simd news from the front.
by Mathieu - 16 Jun '11

16 Jun '11

Hi everyone, Last week, we (Joel Falcou my mentor, Mathias Gaunard, and me) had a meeting to decide the courses of action for the future boost.simd library. For those who aren't aware of it, it's a subset of an existing library, namely nt2, which provide an abstraction for simd instructions in C++. Here is what have been decided so far : boost.simd will be composed of several modules mimicking what's done in nt2 (or in phoenix). That is there will be the main operators in a module (add / minus etc) and the extra modules that we provide like bitwise (bitwise_andnot etc) or arithmetic. Second, what will be included? We decided to keep only functions which might have a corresponding intrinsic to exploit. Finally boost.build will come into play later in the process. Final note, despite what I said in a previous mail a few weeks ago, the initial development will happen in the nt2 (available at https://github.com/MetaScale/nt2 : main repository (in a branch) for ease of use (to ease merge process mainly) and in the boost.simd repository. Cheers, Mathieu Masson.

10 44

Fwd: [MSM] exit_ps stuks in case of outer state machine uses Row with event to event base class
by Richard Szabo 15 Jun '11

15 Jun '11

Thanks Christophe I will try it out but we use the queue anyhow because we send signals to our self some cases. It was just a copy paste mistake for the example to disable queues. the real problem is the constructor if I define this : event4 (const event3& evt_) : baseEvent() { } than it works (after enabling the queue). So I don't get it why it is compiles ..... and now I have to figure out what has changed in our real code which hides the copy constructor ..... Thanks for your support PS : We update to latest MSM time to time and even using new features of it like Enqueueing events for later processing Thanks Richard On 15 June 2011 06:42, Christophe Henry <christophe.j.henry(a)googlemail.com> wrote: >> 3. This one is my fault and might be a problem for you as you seek >> performance. I think we discussed this but I forgot it in the doc. Pseudo >> exits require the message queue and you deactivated it with: >> typedef int no_message_queue; > > Thinking again about it, as you have the newest MSM version (time for a bit > of advertisement for the new version ;-) ), there is now a way around the > queue. > The exit point needs the queue because it will process an event4 during > processing of event3, so that MSM has time to update its current state > before processing event4. But this is only because MSM does this after the > transition (the UML standard "forgot" to specify this point). > The newest version allows you to override this and decide that this updating > job will be done for example before the transition is taken (after the guard > chooses the transition of course), or after the exit action, etc. > To do this, add into every state machine: > > typedef msm::active_state_switch_before_transition > active_state_switch_policy; > > Now you don't need the queue. Doc is there: > http://svn.boost.org/svn/boost/trunk/libs/msm/doc/HTML/ch03s05.html#backend… > > Regards, > Christophe > _______________________________________________ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost >

2 1

[math] Empirical distribution function
by Denis Arnaud 15 Jun '11

15 Jun '11

Hello, would there be an interest in adding the Empirical distribution function ( http://en.wikipedia.org/wiki/Empirical_distribution_function) to Boost.Math? The good statistical software projects implement it. For instance, in R, we have the ECDF ( http://stat.ethz.ch/R-manual/R-patched/library/stats/html/ecdf.html) and Python has something like that as well ( http://statsmodels.sourceforge.net/generated/scikits.statsmodels.tools.ECDF… ). Best Denis

5 6

Re: [boost] [math] Empirical distribution function
by Denis Arnaud 15 Jun '11

15 Jun '11

(please disregard my previous message: the subject was not the correct one) Date: Wed, 15 Jun 2011 06:19:49 -0400, From: er <er.ci.2020(a)gmail.com> > I developed one as a Boost.Accumulator here: > https://svn.boost.org/svn/boost/sandbox/statistics/non_parametric/boost/sta… > > While it's been a while I haven't touched these directories, I'd be > happy to do some maintenance & a proper doc/test suite. > It is the ECDF assuming independent sampling (I think identically need > not even be assumed) and derived quantities (such as Kolmogorov Smirnov > statistic) : > F(x) = count of samples below x > The fact that it's an accummulator is just a convenience : the > distribution is updated each time a sample is passed to the acc. > I'm doing maintenance work right not, whether or not this matches the > need of Denis. It shouldn't take too much time (days). That seems to fit my (pretty simple) need. I'm still trying to test it. Indeed, I would find it more logical to have an empirical distribution "function" <http://en.wikipedia.org/wiki/Empirical_distribution_function>part of the set of already existing Boost.Math statistical distributions<http://www.boost.org/doc/libs/1_46_1/libs/math/doc/sf_and_dist/html/math_to…>. But an accumulator is just fine for now. By the way, does it mean that if we have a set of 1 million of distinct real numbers, the corresponding accumulator will store a pretty big number of counters? Denis

2 1

[fusion] Qualification of 'at' and 'deref' in fusion (Ticket #4755)
by Gabriel Redner 15 Jun '11

15 Jun '11

I have just been bitten by a simple issue in fusion. The 'at' and 'deref' functions are used unqualified, which causes conflicts when mpl::at and mpl::deref are also visible. This issue has been reported as Ticket #4755 [1], and a patch was attached eight months ago. Is there anyone I can prod to get this fix committed? I have also updated the ticket with some relevant information. Thanks, -Gabe [1] https://svn.boost.org/trac/boost/ticket/4755

3 4

[intrusive] unordered_set insert/find question
by Tim Blechmann 15 Jun '11

15 Jun '11

hi all, i am a bit confused about the behavior of boost::intrusive::unordered_set. i can insert() an object, but i am unable to find() it: my basic workflow is: // insert: map_type * elem = new map_type(); std::pair<iterator, bool> inserted = slot_resolver_map.insert(*elem); bool success = inserted.second; assert(success); // object has been inserted correctly // verify: iterator this_iterator = inserted.first; iterator found = slot_resolver_map.find(*elem); iterator end = slot_resolver_map.end(); assert(this_iterator == found); // fails assert(found != end); // fails so basically if i insert an element, i cannot find it anymore ... i have a reduced test case, which shows this behavior at [1] ... is this my fault (not using the unordered_set correctly) or is it a bug in boost.intrusive? thanks, tim

3 4

MS VC10 std::numeric_limits<float>::max_digits10 is wrong for float
by Paul A. Bristow 15 Jun '11

15 Jun '11

Inexplicably, MS for VS 10 have chosen std::numeric_limits<float>::max_digits10 == 8 for VS 10 rather than 9, when the formula max_digits10 = 2 + std::numeric_limits<FPT>::digits * 3010/10000; and values have been known for 30 years. std::numeric_limits<T>:: max_digits10; is 'new for C++0X'. Briefly, max_digits10 is the number of decimal digits that you need to output to make sure that a one least significant bit (ULP) change produces a different decimal digit string. Any more digits are just noise with no useful information. Using max_digits10 rather than the formula above may be more efficient, and is certainly very much clearer. "Executive Summary" ================ Don't use max_digits10 for float or floating-point template types for MS VS - yet! You can safely (and very usefully) use cout.precision(std::numeric_limits<double>::max_digits10); when you want to be sure that all significant decimal digits are output. GCC provides the correct values of 9 for float (and 17 for double). The Fuller Story =========== This might affect anyone planning to use VS10 and this new (and very useful numeric_limits value) with built-in *type float, or a floating-point template type*, potentially, for example, with Boost Lexical_cast, Serialization. Round tripping would be 1 bit wrong in perhaps 1/3 of cases! If max_digits10 was used, Boost.Test might detect values that are different, but are reported to be the same, for example. As far as I know, none of these utilities yet try to use max_digits10. Mercifully, this fault only affects type T = float (not the most popular double or long double), and only in new code that uses the 'new for C++0X' numeric_limits<T>:: max_digits10. Other types like double and long double (and possibly user defined types that specialize numeric_limits) are, I believe, correct. So you can safely (and very usefully) use cout.precision(std::numeric_limits<double>::max_digits10); when you want to be sure that all significant decimal digits are output. (If you want this to be 'Boost portable' you will have to use the inscrutably named BOOST_NO_NUMERIC_LIMITS_LOWEST as a proxy for "C++0x numeric_limits before using new-for-C++0X max_digits10. Unless we add yet another macro for max_digits10? Groan.). The workaround is to continue to use the well-tried and test Kahan formula max_digits10 = 2 + std::numeric_limits<FPT>::digits * 3010/10000; Reported and confirmed as https://connect.microsoft.com/VisualStudio/feedback/details/668921/std-nume… ts10-value-of-8-is-wrong-and-should-be-9 (It might help if, you could confirm you can 'reproduce' this too). I trust this mistake will be corrected pronto - but I'm not holding my breath :-( I will post again if it is resolved. Paul --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow(a)hetp.u-net.com

5 13

[MSM] exit_ps stuks in case of outer state machine uses Row with event to event base class
by Richard Szabo 15 Jun '11

15 Jun '11

Hi Christophe and All after splitting our complicated several level deep contained state machines to small run-time instances. I have to use feature Event Hierarchy (http://svn.boost.org/svn/boost/trunk/libs/msm/doc/HTML/ch03s02.html#d0e1176) which is really cool. But this feature in combination with pseudo exits state, breaks the pseudo exit state functionality and the pseudo exit state is entered but never left. I have made a small example where the problem is reproduced see attachment. (the file name is misleading was just lazy to rename it something more appropriate) Here is the output of the execution : entering: Idle MS1_ leaving: Idle Action: MS1::onEvent1 entering: RunningStateMachine MS1_ entering: RunningStateMachine::PseudoEntry1 leaving: RunningStateMachine::PseudoEntry1 entering: Inner1 RunningStateMachine_ entering: InnerState11 leaving: InnerState11 leaving: Inner1 entering: RunningStateMachine::PseudoEntry1 I have tried it in our host test environment only so VC9 compiler and with boost trunk from Friday last week. Cheers Richard.

2 2

[review][assign] Formal review of Assign v2 begins 15th June
by John Bytheway 14 Jun '11

14 Jun '11

The formal review of the Assign v2 library upgrade by Erwann Rogard starts tomorrow, June 15th and is scheduled to continue until June 24th. About Assign v2 =============== Assign v2 is an upgrade of Boost.Assign (1.0) that redefines its functionality, with optional C++0x support and new features. It is a compact interface for executing the repetitive tasks of assigning or inserting container elements. Please see the change log (linked below) for more detail on the motivation for this library and pointers for navigating the documentation. Where to get it =============== The documentation is online at: <http://svn.boost.org/svn/boost/sandbox/assign_v2/libs/assign/v2/doc/html/in…> With the change log at: <http://svn.boost.org/svn/boost/sandbox/assign_v2/libs/assign/v2/doc/html/bo…> The Assign v2 source can be found in the Boost sandbox at: <http://svn.boost.org/svn/boost/sandbox/assign_v2/> or downloaded from: <http://www.boostpro.com/vault/index.php?action=downloadfile&filename=assign…> Review guidelines ================= Reviews should be submitted to the developer list (boost(a)lists.boost.org) with '[assign]' in the subject. Or if you don't wish to for some reason, you can send them privately to me. If so, please let me know whether or not you'd like your review to be forwarded to the list. All reviews are appreciated, even if you don't have time for an in-depth study. The Assign v2 library consists of several largely independent components: Reference containers and chaining, container modification and generation, and conversion of ranges to containers. If you wish, feel free to review and even vote on these separately. For your review you may wish to consider the following questions: - 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? And finally, every review should answer this question: - Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. More detail on the review process is available at: http://www.boost.org/community/reviews.html John Bytheway Review Manager

1 0

[documentation/doxygen] Trouble with partial template specializations in documentation
by Vicente Botet 14 Jun '11

14 Jun '11

Hi, I'm having some trouble with partial template specializations documentation while generating the Boost.Conversion documentation. The documentation for the specialization is not generated sometimes. I have added the file type_erasure/any.hpp that specialize the any template class and it works as expected with my Jamfile. I don't know why the specializations in conversion/assign_to.hpp are not all generated. The specialization on conversion/boost and conversion/std don't appear neither. Could someone help me? Thanks in advance, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/documentation-doxygen-Trouble-with-parti… Sent from the Boost - Dev mailing list archive at Nabble.com.

1 0

Holding char arrays in boost variants, what is the correct way?
by Michael Goldshteyn 14 Jun '11

14 Jun '11

What is the correct way of getting several character arrays into a variant: // This doesn't work typedef boost::variant<int,char[256],char[8192]> MyType; // This does, but seems like a lot of work template <int len> struct MyChar { char val_[len]; }; typedef boost::variant<int,MyChar<256>,MyChar<8192> > MyType; What is the best way to do this? Thanks, Michael Goldshteyn

4 7

[container_bptree] updates and performance measurements
by Vadim Stadnik 14 Jun '11

14 Jun '11

Hi all, The code and documentation of the submitted library container_bptree have been updated. The new version can be downloaded using this link: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=contai… 1. For those who do not know this library I’d suggest before opening the documentation to spend some time to the answer the following warm-up question: Is it possible to sum up any N consecutive numbers in less than N-1 operations? 2. The library and tests compile and run correctly on two C++ compilers: MSVC++ 9/10 (tested with Visual Studio 2008/2010, including Express editions), and GCC 4.5.2 (tested with MinGW). 3. Lists of template parameters of class templates have been modified to simplify the generation of classes of STL variants of containers. 4. Performance measurements have been added to the documentation. They show that submitted B+ trees are highly competitive with Red Black trees in basic operations. 5. I would like to thank Beman Dawes for suggestion to adapt and apply map tests from his project [BTree]. Class templates of the namespace container_bptree can be used to generate three types of map containers with bidirectional and random access iterators. All of them pass successfully the adapted tests on Windows systems. At this stage it would be particularly valuable in addition to my own tests to run independent tests for associative containers with random access iterators. This is why I am wondering if there are Boost libraries, which include classes of such associative containers and test code. 6. Since I am a newcomer to Boost community I do not know how the current level of quality of the library container_bptree meets Boost standards. Anyone who tried the code and read the documentation is welcome to make comments and suggestions. I am quite happy to implement another list of improvements before the formal request for interest to this library. Regards, Vadim Stadnik

1 0

fusion concepts
by Robert Ramey 14 Jun '11

14 Jun '11

I'm trying to implement concept checking for at least parts of the boost::fusion library. My motivations are several: a) I'm interested in making another library/program based on fusion and I believe that having implemented concepts will make this job easier. b) I'm interested in the concept checking concept and this is way to pracitice. Attached is the current state of my efforts. I have a few problems with this. I think most of these are specific to fusion but maybe not. a) line 29 of test_misc.cpp invokes concept checking on a fusion vector. lines 28 & 29 of fusion/concepts.hpp are intended to verify that result_of::next have been defined for the for the forward iterator associated with the fusion vector. The BOOST_CONCEPT_ASSERT fails with element 6 from the sequence. I conclude that the recurrsive invocation of concept checking on the result of next is crapping out at the end of the sequence. This makes sense in a practical way - BUT it would voilate the requirements on the return type from result_of::end<vector>. Sooooo i) am I right about this? ii) if so how should it be addressed? fixing the concept implementation (how?) would "hide" the violation. Seems to be that the documentation on forward sequence/iterator should be tweaked and my concept checking code should be fixed up to match. Any thoughts on this? b) lines 34-38 illustrate a different problem. I can't figure out what distance(i,j) is supposed to return. I would think that result_of::distance(i, j) should be a signed integer of some sort. So I'm not understanding why this assertion traps. I not sure if it's a side effect of the problem cited in a) above. c) In another file not included here (test_concepts.hpp). I've attempted to implement archtypes for these types. I managed to do it, but I'm not all that confident that i did it right. After doing this, I came to understand the fusion extension mechanism. I could re-implement the archtypes with this and I'm confident that it would be "correct" BUT I'm wonder if this just wouldn't be a circular conclusion. That is would doing this really be testing the concepts or would generating archetypes in this way just guarentee that things were in some sense internally consistent but not necessarily reflection the concepts as stated in the documentation. Any comments/help would be appreciated. Robert Ramey begin 666 concepts.hpp M(VEF;F1E9B!?0T].0T505%-?#0HC9&5F:6YE(%]#3TY#15!44U\-"@T*+R\@ M35,@8V]M<&%T:6)L92!C;VUP:6QE<G,@<W5P<&]R=" C<')A9VUA(&]N8V4- M"B-I9B!D969I;F5D*%]-4T-?5D52*2 F)B H7TU30U]615(@/CT@,3 R,"D- M"B,@<')A9VUA(&]N8V4-"B-E;F1I9@T*#0H-"B-I;F-L=61E(#QB;V]S="]C M;VYC97!T+V%S<V5R="YH<' ^#0HC:6YC;'5D92 \8F]O<W0O8V]N8V5P=%]C M:&5C:RYH<' ^#0HC:6YC;'5D92 \8F]O<W0O9G5S:6]N+VET97)A=&]R+FAP M<#X-"B-I;F-L=61E(#QB;V]S="]F=7-I;VXO<V5Q=65N8V4N:'!P/@T*#0IN M86UE<W!A8V4@8F]O<W0@>PT*;F%M97-P86-E(&9U<VEO;B![#0H-"G1E;7!L M871E(#QT>7!E;F%M92!)/@T*<W1R=6-T($9O<G=A<F1)=&5R871O4-O;G-T<G5C=&EB;&4\23X-"GL-"G!U8FQI8SH-"B @("!"3T]35%]# M3TY#15!47U5304=%*$9O<G=A<F1)=&5R871O<BD-"B @("![#0H@(" @(" @ M('1Y<&5D968(a)22!*.PT*(" @(" @(" O+R!V97)I9GD@=&AE('1H92!F;VQL M;W=I;F<@97AI<W0-"B @(" @(" @='EP961E9B!T>7!E;F%M92!B;V]S=#HZ M9G5S:6]N.CIR97-U;'1?;V8Z.FYE>'0\23XZ.G1Y<&4@=#$[#0H@(" @(" @ M($)/3U-47T-/3D-%4%1?05-315)4*"@@1F]R=V%R9$ET97)A=&]R/'0Q/B I M*3L-"B @(" @(" @='EP961E9B!T>7!E;F%M92!B;V]S=#HZ9G5S:6]N.CIR M97-U;'1?;V8Z.F5Q=6%L7W1O/$DL($H^.CIT>7!E('0R.PT*(" @(" @("!T M>7!E9&5F('1Y<&5N86UE(&)O;W-T.CIF=7-I;VXZ.G)E<W5L=%]O9CHZ861V M86YC95]C/$DL,#XZ.G1Y<&4@=#,[#0H@(" @(" @('1Y<&5D968@='EP96YA M;64@8F]O<W0Z.F9U<VEO;CHZ<F5S=6QT7V]F.CIA9'9A;F-E/$D(a)+$T^.CIT M>7!E('0T.PT*(" @(" @("!T>7!E9&5F('1Y<&5N86UE(&)O;W-T.CIF=7-I M;VXZ.G)E<W5L=%]O9CHZ9&ES=&%N8V4\22 L2CXZ.G1Y<&4@=#4[#0H@(" @ M(" @('1Y<&5D968@='EP96YA;64@8F]O<W0Z.F9U<VEO;CHZ<F5S=6QT7V]F M.CID97)E9CQ)/CHZ='EP92!T-CL-"B @(" @(" @='EP961E9B!T>7!E;F%M M92!B;V]S=#HZ9G5S:6]N.CIR97-U;'1?;V8Z.G9A;'5E7V]F/$D^.CIT>7!E M('0W.PT*+R\@(" @(" @('0U('@@/2!D:7-T86YC92AI+"!J*3L@#0HO+R @ M(" @(" @0D]/4U1?0T].0T505%]!4U-%4E0H* T*+R\@(" @(" @(" @("!B M;V]S=#HZ4VEG;F5D26YT96=E<CQT>7!E;F%M92!B;V]S=#HZ9G5S:6]N.CIR M97-U;'1?;V8Z.F1I<W1A;F-E/$D(a)+$H^.CIT>7!E/@T*+R\@(" @(" @("DI M.PT*(" @(" @("!S86UE7W1Y<&4H:2 ]/2!J+"!B*3L-"B @(" @(" @<V%M M95]T>7!E*&D@(3T@:BP@8BD[#0H@(" @(" @('-A;65?='EP92AD97)E9BAI M*2P(a)=BD[.PT*(" @(" @("!S86UE7W1Y<&4H*FDL('8I.PT*(" @('T-"B @ M(" -"G!R:79A=&4Z#0H@(" @22!I+"!J.PT*(" @(&)O;VP@8CL-"B @("!T M>7!E;F%M92!B;V]S=#HZ9G5S:6]N.CIR97-U;'1?;V8Z.G9A;'5E7V]F/$D^ M.CIT>7!E('8[#0H@(" @='EP961E9B!B;V]S=#HZ;7!L.CII;G1?/# ^.CIT M>7!E($T[#0H-"B @(" O+R!4>7!E(&1E9'5C=&EO;B!W:6QL(&9A:6P@=6YL M97-S('1H92!A<F=U;65N=',@:&%V92!T:&4@<V%M92!T>7!E+@T*(" @('1E M;7!L871E(#QT>7!E;F%M92!4/@T*(" @('9O:60@<V%M95]T>7!E*%0@8V]N M<W0F+"!4(&-O;G-T)BD[#0I].PT*#0IT96UP;&%T92 \='EP96YA;64@4SX- M"G-T<G5C="!&;W)W87)D4V5Q=65N8V4@>PT*<'5B;&EC.@T*(" @($)/3U-4 M7T-/3D-%4%1?55-!1T4H1F]R=V%R9%-E<75E;F-E*0T*(" @('L-"B @(" @ M(" @+R\@=F5R:69Y('1H92!T:&4@9F]L;&]W:6YG(&5X:7-T#0H@(" @(" @ M('1Y<&5D968@='EP96YA;64@<F5S=6QT7V]F.CIB96=I;CQ3/CHZ='EP92!T M,3L-"B @(" @(" @0D]/4U1?0T].0T505%]!4U-%4E0H*"!&;W)W87)D271E M<F%T;W(\=#$^("DI.PT*(" @(" @("!T,2!X,2 ](&)E9VEN*',I.PT*(" @ M(" @("!T>7!E9&5F('1Y<&5N86UE(')E<W5L=%]O9CHZ96YD/%,^.CIT>7!E M('0R.PT*+R\@(" @(" @($)/3U-47T-/3D-%4%1?05-315)4*"@@1F]R=V%R M9$ET97)A=&]R/'0R/B I*3L-"B @(" @(" @=#(@>#(@/2!E;F0H<RD[#0H@ M(" @(" @('1Y<&5D968@='EP96YA;64@<F5S=6QT7V]F.CIS:7IE/%,^.CIT M>7!E('0S.PT*(" @(" @("!T,R!X,R ]('-I>F4H<RD[#0H@(" @(" @('1Y M<&5D968@='EP96YA;64@<F5S=6QT7V]F.CIE;7!T>3Q3/CHZ='EP92!T-#L- M"B @(" @(" @=#0@>#0@/2!E;7!T>2AS*3L-"B @(" @(" @='EP961E9B!T M>7!E;F%M92!R97-U;'1?;V8Z.F9R;VYT/%,^.CIT>7!E('0U.PT*(" @(" @ M("!T-2!X-2 ](&9R;VYT*',I.PT*(" @('T-"@T*<')I=F%T93H-"B @("!3 M(',[#0H-"B @(" O+R!4>7!E(&1E9'5C=&EO;B!W:6QL(&9A:6P@=6YL97-S M('1H92!A<F=U;65N=',@:&%V92!T:&4@<V%M92!T>7!E+@T*(" @('1E;7!L M871E(#QT>7!E;F%M92!4/@T*(" @('9O:60@<V%M95]T>7!E*%0@8V]N<W0F M+"!4(&-O;G-T)BD[#0I].PT*#0I]("\O(&9U<VEO;@T*?2 O+R!B;V]S= T* M#0HC:6YC;'5D92 \8F]O<W0O9G5S:6]N+VET97)A=&]R+VME>5]O9BYH<' ^ M#0HC:6YC;'5D92 \8F]O<W0O9G5S:6]N+VET97)A=&]R+W9A;'5E7V]F7V1A M=&$N:'!P/@T*(VEN8VQU9&4@/&)O;W-T+V9U<VEO;B]I=&5R871O<B]D97)E M9E]D871A+FAP<#X-"@T*;F%M97-P86-E(&)O;W-T('L-"FYA;65S<&%C92!F M=7-I;VX@>PT*#0IT96UP;&%T92 \='EP96YA;64@23X-"G-T<G5C="!!<W-O M8VEA=&EV94ET97)A=&]R(#H-"B @("!&;W)W87)D271E<F%T;W(\23X-"GL- M"G!U8FQI8SH-"B @("!"3T]35%]#3TY#15!47U5304=%*$%S<V]C:6%T:79E M271E<F%T;W(I#0H@(" @>PT*(" @(" @(" O+R!V97)I9GD@=&AE('1H92!F M;VQL;W=I;F<@97AI<W0-"B @(" @(" @='EP961E9B!T>7!E;F%M92!B;V]S M=#HZ9G5S:6]N.CIR97-U;'1?;V8Z.FME>5]O9CQ)/CHZ='EP92!T,3L-"B @ M(" @(" @='EP961E9B!T>7!E;F%M92!B;V]S=#HZ9G5S:6]N.CIR97-U;'1? M;V8Z.G9A;'5E7V]F7V1A=&$\23XZ.G1Y<&4@=#([#0H@(" @(" @('1Y<&5D M968@='EP96YA;64@8F]O<W0Z.F9U<VEO;CHZ<F5S=6QT7V]F.CID97)E9E]D M871A/$D^.CIT>7!E('0S.PT*(" @(" @("!S86UE7W1Y<&4H9&5R969?9&%T M82AI*2P@8F]O<W0Z.F9U<VEO;CHZ<F5S=6QT7V]F.CID97)E9E]D871A/$D^ M.CIT>7!E*3L-"B @("!]#0H@(" @#0H@<')I=F%T93H-"B @("!)(&D[#0H@ M(" @+R\@5'EP92!D961U8W1I;VX@=VEL;"!F86EL('5N;&5S<R!T:&4@87)G M=6UE;G1S(&AA=F4@=&AE('-A;64@='EP92X-"B @("!T96UP;&%T92 \='EP M96YA;64@5#X-"B @("!V;VED('-A;65?='EP92A4(&-O;G-T)BP@5"!C;VYS M="8I.PT*?3L-"@T*?2 O+R!F=7-I;VX-"GT@+R\@8F]O<W0-"@T*+RH-"D)I M9&ER96-T:6]N86P@271E<F%T;W(-"E)A;F1O;2!!8V-E<W,@271E<F%T;W(- M"D%S<V]C:6%T:79E($ET97)A=&]R#0H-"D9O<G=A<F0@4V5Q=65N8V4-"D)I M9&ER96-T:6]N86P@4V5Q=65N8V4-"E)A;F1O;2!!8V-E<W,@4V5Q=65N8V4- M"D%S<V]C:6%T:79E(%-E<75E;F-E#0H-"D-A;&QA8FQE($]B:F5C= T*4F5G M=6QA<B!#86QL86)L92!/8FIE8W0-"D1E9F5R<F5D($-A;&QA8FQE($]B:F5C M= T*4&]L>6UO<G!H:6,@1G5N8W1I;VX@3V)J96-T#0HJ+PT*#0HC96YD:68@ /+R\@7T-/3D-%4%137PT* ` end begin 666 test_misc.cpp M(VEN8VQU9&4@/'-T<FEN9SX-"B-I;F-L=61E(#QI;W-T<F5A;3X-"@T*(VEN M8VQU9&4@/&)O;W-T+V9U<VEO;B]C;VYT86EN97(O=F5C=&]R+FAP<#X-"B-I M;F-L=61E(#QB;V]S="]F=7-I;VXO=FEE=R]F:6QT97)?=FEE=RYH<' ^#0HC M:6YC;'5D92 \8F]O<W0O9G5S:6]N+W-E<75E;F-E+VEO+FAP<#X-"B-I;F-L M=61E(#QB;V]S="]M<&PO;F]T+FAP<#X-"B-I;F-L=61E(#QB;V]S="]T>7!E M7W1R86ET<R]I<U]C;&%S<RYH<' ^#0H-"G5S:6YG(&)O;W-T.CIM<&PZ.E\[ M#0IU<VEN9R!B;V]S=#HZ;7!L.CIN;W1?.PT*=7-I;F<@8F]O<W0Z.FES7V-L M87-S.PT*=7-I;F<@;F%M97-P86-E(&)O;W-T.CIF=7-I;VX[#0H-"G1Y<&5D M968@=F5C=&]R/'-T9#HZ<W1R:6YG+"!C:&%R+"!L;VYG+"!B;V]L+"!D;W5B M;&4^('9E8W1O<E]T>7!E.PT*='EP961E9B!R97-U;'1?;V8Z.F)E9VEN/'9E M8W1O<E]T>7!E/CHZ='EP92!V96-T;W)?='EP95]I=&5R871O<CL@#0IT>7!E M9&5F(&9I;'1E<E]V:65W/'9E8W1O<E]T>7!E(&-O;G-T+"!N;W1?/&ES7V-L M87-S/%\^(#X@/B!V:65W7W1Y<&4[#0H-"FEN="!M86EN*&EN="!A<F=C+"!C M:&%R("H@87)G=EM=*7L-"B @("!V96-T;W)?='EP92!V*")A+7-T<FEN9R(L M("= )RP@.3@W-C4T+"!T<G5E+" V+C8I.PT*(" @('9I97=?='EP92!V:65W M*'8I.PT*(" @('-T9#HZ8V]U=" \/"!V:65W(#P\('-T9#HZ96YD;#L-"GT- M"@T*#0HC:6YC;'5D92 B9G5S:6]N+V-O;F-E<'1S+FAP<"(-"B-I;F-L=61E M(")S8VAE;6$N:'!P(@T*#0I"3T]35%]#3TY#15!47T%34T525"@H(&)O;W-T M.CIF=7-I;VXZ.D9O<G=A<F1397%U96YC93QV96-T;W)?='EP93X@*2D[#0I" M3T]35%]#3TY#15!47T%34T525"@H(&)O;W-T.CIF=7-I;VXZ.D9O<G=A<F13 897%U96YC93QV:65W7W1Y<&4^("DI.PT* ` end

5 11

Re: [boost] [gsoc] boost.simd news from the front.
by Ivan Le Lann 14 Jun '11

14 Jun '11

----- "David A. Greene" <greened(a)obbligato.org> a écrit : > Mathias Gaunard <mathias.gaunard(a)ens-lyon.org> writes: > > > Making data parallelism simpler is the goal of NT2. And we do that > by > > removing loops and pointers entirely. > > First off, I want to apologize for sparking some emotions. That was > not > my intent. I am deeply sorry for not expressing myself well. > > NT2 sounds very interesting! Does it generate the loops given calls > into generic code? > > Let me try to clarify my thinking about boost.simd a bit. > > - There is a place for boost.simd. It's important that I emphasize > this > upfront. > > - Here is how I see a typical programmer using it, given a loop nest: > > - Programmer tries to run the compiler on it, examines code > - Code sometimes (maybe most of the time) executes poorly > - If not, done > > - Programmer restructures loop nest to expose parallelism > - Try compiler directives first, if available (tell compiler > which > loops to interchange, where to cache block, blocking factors, > which loops to collapse, etc.) > - Otherwise, hand-restructure (ouch!) > > - Programmer tries compiler again on restructured loop nest > - Code may execute poorly > - If not, done > > - Programmer adds directives to tell the compiler which loops > to vectorize, which to leave scalar, etc. > - Code may still execute poorly > - If not, done > > - Programmer uses boost.simd to write vector code at a higher level > than provided compiler intrinsics > > Does that seem like a reasonable use case? > I hope I won't disappoint you, but in my case I'd put boost.simd a few ranks up. Because, from what I've seen in slides, it's a quite easy and really clean way to do things. I've always been taught to dive into dirty things as a last resort, so I'd use boost.simd first, and eventually, if performance is still not met, try hand-written hints. Regards, Ivan

1 0

[foreach][assign] Does foreach work with assign::list_of?
by MaximYanchenko 14 Jun '11

14 Jun '11

This simple example doesn't compile with GCC 4.4 + Boost 1.46.1: #include <boost/assign/list_of.hpp> #include <boost/foreach.hpp> #include <iostream> int main() { BOOST_FOREACH( int i, boost::assign::list_of(3)(1)(4)(1)(5) ) std::cout < >' and 'boost::assign_detail::generic_list<int>' I believe both Foreach and Assign library are to ease sequence creation/iteration on the fly, so they should work together smoothly. Thanks, Maxim

4 4

Re: [boost] Is there any interest in a base class which prevents construction during the static initialization phase?
by Ben Robinson 14 Jun '11

14 Jun '11

> > On Jun 12, 2011, at 4:51 PM, Ben Robinson wrote: > > > Because the order of static initialization is undefined, numerous > > difficult > > to detect problems can arise when multiple objects are initialized > > during > > the static initialization phase. This base class would guarantee > > that a > > class will never be unintentionally constructed during static > > initialization. This is the same philosophy behind how > > boost::noncopyable > > guarantees that a class will never be unintentionally copied. > > > > int main() > > { > > nonstaticinitializable::enable_initialization(); // Indicates that > > static initialization is complete. > > Foo foo; // This instance initializes successfully after static > > initialization. > > return 0; > > } // main > > > > What does Boost think about submission::nonstaticinitializable (I > > chose the > > name to mirror noncopyable)? > > The requirement to modify main() is sufficiently burdensome that I > probably wouldn't use this technique, though I admit the failure mode > is an assertion failure that's easy to fix. But also consider that > the unit defining main() might be written in C. > > Josh > Josh, The requirement is that a single call to a static function is made as the first line of executable C++ code, in order to define the boundary between static initialization, and run-time. Usually this is in main(), but it can be elsewhere. Only a single function call is required, even if every single class in the executable load module inherits from it. I also didn't point out that there is zero performance hit in a release build, as asserts become a noop and the empty base class constructor is inlined out. Also, no vtable is introduced, and a total of only one bool of memory is consumed for the entire program, independent of how many classes use it. I believe the time saved by avoiding debugging static initialization order problems greatly outweighs the cost of adding a single function call to the program. The philosophy is the same as for boost::noncopyable, express your intent to the compiler/program, so you don't accidentally use a class in an unintended way. It is preferable to catch these kinds of problems earlier, rather than later. This class is designed to be of general utility, and I intend to make it standard practice for my applications, just how I already inherit from noncopyable as standard practice, unless I specifically need otherwise. Thank you, Ben Robinson

1 0

Re: [boost] Is there any interest in a base class which prevents construction during the static initialization phase?
by Ben Robinson 14 Jun '11

14 Jun '11

> > On Sun, Jun 12, 2011 at 4:51 PM, Ben Robinson <icaretaker(a)gmail.com> > wrote: > > Hello, > > > > Because the order of static initialization is undefined, numerous > difficult > > to detect problems can arise when multiple objects are initialized during > > the static initialization phase. ?This base class would guarantee that a > > class will never be unintentionally constructed during static > > initialization. ?This is the same philosophy behind how > boost::noncopyable > > guarantees that a class will never be unintentionally copied. > > What you probably mean is "initialization of objects with static > storage duration", which can be static and dynamic. All such objects > are first zero initialized. Then the ones that are initialized with a > constant expression are initialized, and this concludes the static > initialization phase. Then the dynamic initialization phase follows. > > Only the dynamic initialization phase can cause problems. > > However, the dynamic initialization phase can cause problems with any > object that uses it. That is, whether or not a compile error is > induced should only depend on whether or not a given object with > static storage duration is initialized during the dynamic > initialization phase. Deriving or not deriving from > nonstaticinitializable doesn't seem to have anything to do with this. > > Don't get me wrong, I agree that using objects with static storage > duration that are initialized dynamically is the source of many > problems, but it seems like it makes more sense to detect and report > such initialization with a lint-type utility rather than relying on a > programmer to derive from a type. > > Emil Dotchevski > Reverge Studios, Inc. > http://www.revergestudios.com/reblog/index.php?n=ReCode > > Emil, > Emil, Thank you for your feedback. You are correct in that I am referring to objects with static storage duration that are initialized dynamically. No compile error is generated if you unintentionally create an object this way, when you inherit from the proposed base class. Instead, the program will assert before nonstaticinitializable::enable_initialization() is called (which should be called as the first line of C++ code), usually in main(). Detecting this unintended behavior via an assert() before main(), is greatly preferred to debugging undefined behavior. In this way, both noncopyable, and nonstaticinitializable communicate intent to the compiler/program, which can then prevents unintended behavior, an objectively desirable quality. Lint like tools are always available, however I thought to detect this unintended behavior directly in the language, without requiring an additional platform specific tool. Since this base class prevents creating an "object with static storage duration that is initialized dynamically", I would welcome improved naming suggestions. :) Thank you, Ben Robinson

1 0

[heap][formal review]
by Thomas Klimpel 13 Jun '11

13 Jun '11

Hi, this is my actual review of Boost.Heap. I took part in this review, because I was interested in the results of Boost.Heap for my old heap test/benchmark (related to the fast marching algorithm). So I decided that trying to use Boost.Heap with the old test code was a good experiment for a review, allowing me to see how helpful the documentation is, how easy it is to use the heaps and how well they perform. - The documentation is easy to read and helpful with respect to the questions it tries to address. The main question it doesn't try to address is how to make effective use of Boost.Heap, i.e. which heap to use for which application and how to use it optimally. - Boost.Heap is easy to use, at least in principle. -- One inconvenience for me was the use of max-heaps instead of min-heaps. Well, one could argue that a priority_queue should return the elements with the highest priority first (but as Wikipedia says: "some conventions consider lower priorities to be higher"), and heap-sort uses a max-heap. Since these are the two application where stl uses a heap, it's clear why stl implements a max-heap. But the applications where it is beneficial to call increase or decrease directly normally use a min-heap. Now I have to call increase even so the key value actually has decreased... -- I was left a bit with the feeling that I hadn't made the most efficient use of Boost.Heap. For example, I quickly found out that calling update just with a handle (as I had implemented it first) was suboptimal for fibonacci_heap. -- The segmentation fault in pairing_heap was unexpected for me. Even more unexpected was Tim's response that it's actually expected. So I tried to inform me a bit. I found statements like "A pairing heaps is a type of heap data structure with relatively simple implementation and excellent practical amortized performance" and "Experimental studies indicate that pairing heaps actually outperform Fibonacci heaps", which are incompatible with pairing_heap segfaulting for a simple testcase (IMHO). My conclusion is that the statement "due to the recursive nature of this data structure, ... beware of stack overflows" is actually misleading. This implementation of pairing_heap actually has a known issue. As long as this issue is not fixed, the structure may be interesting for tests, but "production" use should be strongly discouraged. - The performance numbers for Boost.Heap were neither bad nor outstanding. -- The numbers for b_heap are not convincing -- The numbers for fibonacci_heap seem to be the best. -- The pairing_heap has a smaller compare count than fibonacci_heap, but actually performs worse than fibonacci_heap in this test. Considering statements like "Experimental studies indicate that pairing heaps actually outperform Fibonacci heaps", I wonder whether the implementation of pairing_heap could be improved so that it actually outperforms fibonacci_heap. -- The comparison with TStaticHeap and TSequentialHeap should be taken with a grain of salt. I had first just added fibonacci_heap to the test, which is a node based heap. The test case isn't very favorable for node based heaps. And for the other heaps, I used the same class template, so that .reserve isn't called (it doesn't exist for node based heaps), but the analog function is called for TStaticHeap. And the tuned TSequentialHeap uses "debatable"/"unusual" techniques. > What is your evaluation of the design? I guess it's OK. What makes me a bit nervous is the statement "The library is not targeted in any specific domain nor directly related to any specific libraries". A good interface often is the result from an abstraction over different applications. The other way (coming from the data structure/algorithm) risks bloating the interface with unnecessary functionality. For example, somebody asked during the review for "iteration over the heap in priority order". Is this really something that many applications requiring a heap will benefit from? I heavily doubt this. > What is your evaluation of the implementation? I haven't looked too deep into it, but I think it's OK. I'm not sure whether there isn't a bit too much code reuse and "one size fits all". Was it really possible to implement all the heaps in their optimal form with this approach? But I'm not expert enough to really judge this. I was a bit surprised how pairing_heap::merge_children was implemented (was it just a mistake?), but I don't believe that this is caused by the code reuse or the "one size fits all". It's possible that similar problem also exist in other functions, but that doesn't change the good overall impression. It's only natural that such problems are only brought up when the code is used by more people than just the initial author. > What is your evaluation of the documentation? The documentation is easy to read. It doesn't address the question how to make effective use of Boost.Heap, i.e. which heap to use for which application and how to use it optimally. One benefit of the library would be to educate the user about the different possibilities. An important thing here is worse case performance and amortized performance, why are different heaps needed at all, ... > What is your evaluation of the potential usefulness of the library? There are different use cases I can see: 1) You already have a heap in your software, but you want to see how good it performs with respect to what else is out there. 2) You need a heap as part of a more complex algorithm. 3) You need a priority queue for scheduling something. The library in its current form is actually really well suited for 1, because all the heaps have a very similar interface, which makes it easy to test many different heaps without much effort. The library is also quite useful for 2, even if it would be nice if the documentation would save me some of the required experimentation. I also fear that the uniform interface of the heaps sacrifices some optimality for some algorithms. - Take the fast marching algorithm as an example. I typically have one bulk with the arrival times and one bulk with the speeds. I'm not especially keen on having another bulk with "heap_t::handle_type", as that may double my memory consumption on a 64-bit system, if arrival times and speeds were of type float. - However, the alternative is giving up the uniform interface of the heaps, just for some very questionable savings for some special applications. Because for Dijkstra's algorithm, the memory consumption is dominated by the edges of the graph, so that I don't care about an additional array with "heap_t::handle_type" of the same size as the number of vertices of the graph. I have the impression that std::priority_queue is already sufficient for 3, so that Boost.Heap wouldn't be required for that use case. Overall, I think it is quite useful. > Did you try to use the library? With what compiler? > Did you have any problems? Yes, I used it. gcc-4.3.4 (cygwin), gcc-4.3.3 (win32), gcc-4.4.3 (ubuntu), gcc-4.5.2 (win32), MSVC-9, MSVC-10. There were some minor problems, but all the problems I actually reported have been fixed (except the unexpected segfault for pairing_heap). So may main problem was probably that I felt a bit left alone with respect to the question which heap to use and how to use it optimally. > How much effort did you put into your evaluation? > A glance? A quick reading? In-depth study? More effort than I had actually planed to spend, but I already knew from previous reviews that this would happen. I think I did a reasonably deep study from a user point of view. > Are you knowledgeable about the problem domain? Yes, at least from the user point of view. I have heard of binomial heaps, d_ary heaps and fibonacci heaps before. I didn't knew about b_heap, pairing_heap and skew_heap, but I knew that there are many different heap variants out there. For example I knew about the sequential heap described in "Fast Priority Queues for Cached Memory" by P. Sanders (which doesn't mean that TSequentialHeap is identical to the sequential heap described in that paper, but it isn't too different either). > Do you think the library should be accepted as a Boost library? No, the library should not be accepted unless - The current review either magically goes back on track and at least 3 other persons also submit a proper review, or another (mini?) review with proper participation is held later. - Either pairing_heap is fixed, or non-experimental (="production") use is strongly discouraged in the documentation. - Either a convincing example where b_heap outperforms the other heaps is presented, or it's use should be discouraged in the documentation. - The documentation says a bit more about the different heaps and their trade offs (amortized time <-> worst case), and generally tries to give recommendation to the user which heap will likely best fit his application, and which settings he should try (for example something like that arity<4> is a good compromise for a d_ary heap between cache locality and compare count). I used the negative form of "Yes, the library should be accepted under the following conditions", because I'm unhappy with how the review went. The announcement was sent out too late, without stating the dates of the review, much of the initial discussion was about the code collaborator tool, but I haven't seen any "real" review, despite that fact that there seems to be interest in the library. There were some discussions on Code Collaborator, and the tool was actually not bad in pointing to concrete problems in the actual code. Tim quickly addressed these, but a good review would have some discussions and actual opinions and suggestions. It is also unclear to me how well Boost.Heap performs with respect to boost/graph/detail/d_ary_heap.hpp. I could have tried to also include this heap in my heap test/benchmark, but as the review seemed to have silently died already, I wasn't motivated enough for doing this. Regards, Thomas

4 4

clang type traits
by Bryce Lelbach 13 Jun '11

13 Jun '11

John, Clang has supported GCC style type trait intrinsics (__is_pod, etc) for awhile. The <boost/type_traits/intrinsics.hpp> header doesn't detect this. May I fix this? -- Bryce Lelbach aka wash boost-spirit.com px.cct.lsu.edu github.com/lll-project

4 7

[Heaps] Review
by Phil Endecott 13 Jun '11

13 Jun '11

Dear All, Here is my review of the proposed Heaps library. What is your evaluation of the design? Satisfactory. If possible, I think it would be good to provide the new heaps with interfaces as close as possible to the std:: heap, i.e. as algorithms (push, pop, etc.) over arbitrary containers or ranges, as well as the current containers. This would allow: (a) Existing code using std::push|pop_heap could be converted to use one of the alternative designs with just some search-and-replace; (b) Portions of a container could be managed as heaps, with other portions unordered, sorted, etc.; (c) Heaps over raw memory (e.g. memory-mapped files) would be possible. (I posted this suggestion in an email a few days ago but haven't had any replies. It is possible that there is something that I have overlooked that makes this impractical.) What is your evaluation of the implementation? I found one bug, which Tim was able to fix quickly. Although I've not looked in detail at the code, what I have seen appears satisfactory. It does seem to lack either comments or much else in the way of internals-documentation, though. I am concerned about the performance of the B Heap. It seems to execute twice as many instructions as a "traditional" heap, and it's hard to concoct a situation where its improved memory access pattern makes up for that. Some more investigation of this is needed. My past exposure to "B" structures has mainly seen them used for on-disk data. How do cache, main memory, and disk access times compare these days? It would be great to see some real-application benchmarking of this. What is your evaluation of the documentation? It needs some expansion, but it's on the right lines. It suffers, from too many, commas. A table indicating the features and complexity of those features for each heap would be useful at the start. What is your evaluation of the potential usefulness of the library? Personally I currently have no need for those heaps with improved merge performance, and the B-heap doesn't help me because it is slower than the std:: heap. Despite this, I believe it is useful enough to warrant inclusion in Boost. Did you try to use the library? With what compiler? Did you have any problems? Yes, with gcc 4.* on Linux; one bug which Tim says has been fixed. How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? A few hours. Are you knowledgeable about the problem domain? Not especially, though I have used std heaps in a couple of applications. And finally, every review should answer this question: Do you think the library should be accepted as a Boost library? Yes. Regards, Phil.

2 1

[review] [heap] ending today
by Andrew Sutton 13 Jun '11

13 Jun '11

Today is the last day of the review of Tim Blechmann's Heap library. The review had been extended until today because of an unavoidably late announcement. If you commented on the library, please submit a formal review (i.e., a Yes/No vote). There have been a number of people expressing comments or asking questions, but not voting. I will be preparing a summary of the review over the course of the week so there is a little extra leeway if you absolutely cannot submit a formal review today. I would like to thank all of the reviewers who have have taken time to inspect and comment on Tim's work. I would also like to thank Tim for submitting his library for review and patiently answering our questions and addressing our comments. Andrew

1 0

[Heaps] benchmarks
by Phil Endecott 13 Jun '11

13 Jun '11

Dear All, I have done some quick benchmarks; the code can be found here: http://chezphil.org/tmp/bench.tgz This is a "work queue", i.e. it's a queue of boost::function<void(void)> "work items" with float priorities. It's similar to a real application with fast (burst) fill and gradual drain; the pattern here is 10 pushes and 1 pop, repeated until all the work has been added, and then all of the work is popped in sequence. The priorities are essentially random, and there are 100 000 items in total. Currently my real application uses a std::multimap. I've compared that with a std::vector using std::push|pop_heap, std::priority_queue using std::vector and std::deque, and the proposed heap::priority_queue and heap::b_heap. The columns below are median-of-3 runtimes in seconds for: 1. 50 runs on a 32-bit 3 GHz AMD Athlon II Linux system, using g++ 4.4.4 -O4. 2. 10 runs on a 32-bit 1.2 GHz VIA C7-M Linux syste, using g++4.4.2 -O4. 3. 5 runs on a 1.2 GHz ARMv5 Linux system, using g++ 4.4.2 -O4. std::multimap 3.20 3.69 3.37 std::vector + std::push|pop_heap 2.35 3.36 2.71 std::priority_queue<vector> 2.58 3.48 2.84 std::priority_queue<deque> 4.27 5.77 3.72 heap::priority_queue 2.49 3.37 2.74 heap::b_heap 5.14 7.62 5.82 I was unable to try the proposed d_ary_heap because I couldn't find a working syntax for the arity template parameter - any ideas anyone? The 3 implementations based on std::vector perform similarly, as expected. I'm a bit surprised that my one is fastest, but the difference is small. Also as expected the version using multimap is slower, though maybe not by as much as I had expected. I was expecting the b_heap to be faster, but it is not; it is substantially slower. What is going on there? Does it all come down to size of data, cache size, etc? Ideally, an "improved" implementation like this would be able to fall back to the naive implementation in cases where it does not function any better. Or maybe I'm using it wrongly. My understanding is that the fibonacci, binomial and other heaps only improve things when other operations e.g. merging are needed - is that correct? Regards, Phil.

4 11