[boost] Re: compile-time functions interface

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2003-02-02 16:44:29

On Sun, 02 Feb 2003 15:02:23 -0500, David Abrahams
<dave_at_[hidden]> 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_at_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_at_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_at_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_at_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_at_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_at_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_at_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_at_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_at_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_at_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_at_I#0I[#0H-
M"B`@("!T97-T97(\,3XZ.G9A;'5E("L@=&5S=&5R/#(^.CIV86QU93L-"@T*
#?0T*
`
end