On Sun, 02 Feb 2003 15:02:23 -0500, David Abrahams <[EMAIL PROTECTED]> wrote:
[...] >My point is this: the only thing that would make argument_type >worthwhile, i.e. the ability to do higher-order functional >programming, really requires that metafunctions have a consistent >polymorphic interface (i.e. type arguments and results). So if you >really insist that static_log2 will not take a type argument, that's >fine, but don't waste your time trying to get argument_type to work. > >You're not operating in a generic world, because there's no way to >generalize the neccessary default argument to arbitrary metafunctions >with that form. You might as well settle for static_log2_arg_type >instead. Yes, your point is very clear and you are undoubtedly right. I've done some quick tests with the current implementation of static_log2 and it turns out that, even with the most optimistic assumptions, compile times increase remarkably as soon as you use a type argument. And there are problems with broken compilers as well. Just to clarify it: the core of the current implementation is the following template // Core algorithm // template<unsigned long x, int n = initial_value> struct static_log2_impl { enum {cn = (1ul<<n <= x) * n}; BOOST_STATIC_CONSTANT(int, value = cn + (static_log2_impl<(x>>cn),n/2>::value)); }; template<> struct static_log2_impl<1ul,0> { BOOST_STATIC_CONSTANT(int, value = 0); }; I've left out the definition of initial_value, for simplicity. Basically the core is a binary search: for instance, if you have 32 bits unsigned longs you start from n = 16, then you see whether your number x is >= 65536. If so, then the logarithm is 16 + the logarithm of x/65536, otherwise you simply go on. This is repeated for n=8, n=4, etc. up to n = 0. It's easy to prove that, if you choose the initial n correctly, you always end up with the first argument = 1 and the second one = 0; thus to terminate recursion you don't need a partial specialization template <unsigned long x> struct static_log2_impl<x, 0> { BOOST_STATIC_CONSTANT(int, value = 0); }; That's of course important for our faithful broken compilers. If I understand you correctly, having a type argument requires PTS instead. Regardless of that consideration, I tried quickly changing the code to this: template< typename T, T v > struct integral_c { BOOST_STATIC_CONSTANT(T, value = v); typedef integral_c<T, v> type; typedef T value_type; }; // Core algorithm // template<typename x, int n = initial_value> struct static_log2_impl { enum { cn = (( x::value >> n) > 0) * n }; enum { value = cn + static_log2_impl < integral_c<typename x::value_type, (x::value >> cn)>, n/2 >::value }; // terminates recursion (uses PTS) template<typename T> struct static_log2_impl<integral_c<T, 1>, 0> { BOOST_STATIC_CONSTANT(int, value = 0); }; // User interface: simply forwards to static_log2_impl // template<unsigned long x> struct static_log2 { BOOST_STATIC_CONSTANT(int, value = (detail::static_log2_impl< integral_c<unsigned long, x> >::value)); }; template<> struct static_log2<0ul> {}; Note that I haven't included any of the pachydermic boost headers, I have just defined integral_c myself. Also, note that this is just a hacked up implementation and that I operated on the argument only, the result is still *not* a type. In other words I have made just a part of the changes that are needed, so the timings I will have with this are likely to be lower than the "real ones". Well, the attached test yielded: // original version: $ ./bash_test.sh real 0m34.672s user 0m10.610s sys 0m22.601s // new version, with type argument $ ./bash_test.sh real 0m39.096s user 0m14.970s sys 0m22.720s Of course, defining integral_c yourself is not enough because it needs compiler workarounds, so in practice you should include the boost header. Doing that, timings go to: $ ./bash_test.sh real 0m42.624s user 0m15.710s sys 0m22.921s Also, if you have to cope with simulating PTS the amount of code to include increases. Well, this was enough to discourage me to do the complete transformation :-/ So I agree that your arguments are very well put, and that from a meta-programming perspective the value-based approach is weak, but abandoning it, in this case, would mean incurring in other problems and give up both simplicity and speed. However, it's likely that I'm missing something, and that there are ways to make the "good way" as efficient as the naive one. You are by far more expert than me with template metaprogramming, so I'll leave to you the last word. Genny. begin 644 bash_test.sh M(R$@+V)I;B]B87-H#0H-"F9U;F-T:6]N('1E<W0@>PT*("`@("!G*RL@+B]T M97-T+F-P<`T*("`@("!G*RL@+B]T97-T+F-P<`T*("`@("!G*RL@+B]T97-T M+F-P<`T*("`@("!G*RL@+B]T97-T+F-P<`T*("`@("!G*RL@+B]T97-T+F-P M<`T*("`@("!G*RL@+B]T97-T+F-P<`T*("`@("!G*RL@+B]T97-T+F-P<`T* M("`@("!G*RL@+B]T97-T+F-P<`T*("`@("!G*RL@+B]T97-T+F-P<`T*("`@ F("!G*RL@+B]T97-T+F-P<`T*#0I]#0H-"G1I;64@=&5S=`T*#0IP ` end begin 644 test.cpp M(VEN8VQU9&4@(F)O;W-T+V-O;F9I9RYH<'`B#0H-"B-I;F-L=61E(")S=&%T M:6-?;&]G,BYH<'`B#0H-"B-D969I;F4@3$]',B`@8F]O<W0Z.G-T871I8U]L M;V<R#0H-"@T*=&5M<&QA=&4\:6YT(&D^#0IS=')U8W0@=&5S=&5R('L-"B`@ M0D]/4U1?4U1!5$E#7T-/3E-404Y4*&EN="P-"B`@("`@("`@("`@("`@("`@ M("`@("`@('9A;'5E(#T-"B`@("`@("`@("`@("`@("`@("`@("`@($Q/1S(\ M:2LH,3P\,"D^.CIV86QU92`K#0H@("`@("`@("`@("`@("`@("`@("`@("!, M3T<R/&DK*#$\/#$I/CHZ=F%L=64@*PT*("`@("`@("`@("`@("`@("`@("`@ M("`@3$]',CQI*R@Q/#PR*3XZ.G9A;'5E("L-"B`@("`@("`@("`@("`@("`@ M("`@("`@($Q/1S(\:2LH,3P\,RD^.CIV86QU92`K#0H@("`@("`@("`@("`@ M("`@("`@("`@("!,3T<R/&DK*#$\/#0I/CHZ=F%L=64@*PT*("`@("`@("`@ M("`@("`@("`@("`@("`@3$]',CQI*R@Q/#PU*3XZ.G9A;'5E("L-"B`@("`@ M("`@("`@("`@("`@("`@("`@($Q/1S(\:2LH,3P\-BD^.CIV86QU92`K#0H@ M("`@("`@("`@("`@("`@("`@("`@("!,3T<R/&DK*#$\/#<I/CHZ=F%L=64@ M*PT*("`@("`@("`@("`@("`@("`@("`@("`@3$]',CQI*R@Q/#PX*3XZ.G9A M;'5E("L-"B`@("`@("`@("`@("`@("`@("`@("`@($Q/1S(\:2LH,3P\.2D^ M.CIV86QU92`K#0H@("`@("`@("`@("`@("`@("`@("`@("!,3T<R/&DK*#$\ M/#$P*3XZ.G9A;'5E("L-"B`@("`@("`@("`@("`@("`@("`@("`@($Q/1S(\ M:2LH,3P\,3$I/CHZ=F%L=64@*PT*("`@("`@("`@("`@("`@("`@("`@("`@ M3$]',CQI*R@Q/#PQ,BD^.CIV86QU92`K#0H@("`@("`@("`@("`@("`@("`@ M("`@("!,3T<R/&DK*#$\/#$S*3XZ.G9A;'5E("L-"B`@("`@("`@("`@("`@ M("`@("`@("`@($Q/1S(\:2LH,3P\,30I/CHZ=F%L=64@*PT*("`@("`@("`@ M("`@("`@("`@("`@("`@3$]',CQI*R@Q/#PQ-2D^.CIV86QU92`K#0H@("`@ M("`@("`@("`@("`@("`@("`@("!,3T<R/&DK*#$\/#$V*3XZ.G9A;'5E("L- M"B`@("`@("`@("`@("`@("`@("`@("`@($Q/1S(\:2LH,3P\,3<I/CHZ=F%L M=64@*PT*("`@("`@("`@("`@("`@("`@("`@("`@3$]',CQI*R@Q/#PQ."D^ M.CIV86QU92`K#0H@("`@("`@("`@("`@("`@("`@("`@("!,3T<R/&DK*#$\ M/#$Y*3XZ.G9A;'5E("L-"B`@("`@("`@("`@("`@("`@("`@("`@($Q/1S(\ M:2LH,3P\,C`I/CHZ=F%L=64@*PT*("`@("`@("`@("`@("`@("`@("`@("`@ M3$]',CQI*R@Q/#PR,2D^.CIV86QU92`K#0H@("`@("`@("`@("`@("`@("`@ M("`@("!,3T<R/&DK*#$\/#(R*3XZ.G9A;'5E("L-"B`@("`@("`@("`@("`@ M("`@("`@("`@($Q/1S(\:2LH,3P\,C,I/CHZ=F%L=64@*PT*("`@("`@("`@ M("`@("`@("`@("`@("`@3$]',CQI*R@Q/#PR-"D^.CIV86QU92`K#0H@("`@ M("`@("`@("`@("`@("`@("`@("!,3T<R/&DK*#$\/#(U*3XZ.G9A;'5E("L- M"B`@("`@("`@("`@("`@("`@("`@("`@($Q/1S(\:2LH,3P\,C8I/CHZ=F%L M=64@*PT*("`@("`@("`@("`@("`@("`@("`@("`@3$]',CQI*R@Q/#PR-RD^ M.CIV86QU92`K#0H@("`@("`@("`@("`@("`@("`@("`@("!,3T<R/&DK*#$\ M/#(X*3XZ.G9A;'5E("L-"B`@("`@("`@("`@("`@("`@("`@("`@($Q/1S(\ M:2LH,3P\,CDI/CHZ=F%L=64I.PT*?3L-"@T*#0II;G0@;6%I;B@I#0I[#0H- M"B`@("!T97-T97(\,3XZ.G9A;'5E("L@=&5S=&5R/#(^.CIV86QU93L-"@T* #?0T* ` end _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost