- Boost - lists.boost.org

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<I> 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<I> 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)=&5R871O<B Z#0H@ M(" @8F]O<W0Z.D5Q=6%L:71Y0V]M<&%R86)L93Q)/BP-"B @("!B;V]S=#HZ M0V]P>4-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 << i << ' '; } error: operands to ?: have different types 'const boost::foreach_detail_::rvalue_probe<boost::assign_detail::generic_list<int> >' 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