Re: Fusion-ifying proto parse trees

Joel de Guzman wrote:
> Eric Niebler wrote:
> > Joel de Guzman wrote:
> >
> > > Eric Niebler wrote:
> > >
> > > > Time taken to construct the ET and traverse it was measured. The 
> > > > winner by a wide margin is (3) segmented proto.
> > >
> > > Great! It would be nice if the 1) time taken to construct the ET
> > > and 2) the time to traverse it, are reported separately.
> >
> > What is it about Spirit's usage scenario that makes traversal time 
> > more important than ET construction time?
>
> You spend more time traversing the nodes than in the one-time-only
> construction. That's why. Consider a trivial parser:
>
>     parse(f,l, int_ >> *(',' >> int_));
>
> You construct the parser only once, but you traverse the parser nodes
> N times. And N can be significant in a lot of cases. Megabytes of
> stuff to parse is not unimaginable.


Oh, of course. Duh, I knew that. :-) In that case I tend to agree with 
you -- it's likely that the cost of the indirections would catch up to 
us in the long run.

I just reran the test with an interesting twist. Rather than use a 
segmented algorithm to traverse the proto parse tree directly, I added a 
2nd phase transformation to deep-copy and flatten the ET tree. So that's 
a zero-copy ET construction followed by a single deep-copy and flatten. 
That is benchmarked against Spirit2's incremental flattening during the 
first ET phase. Results below:

// MSVC8
Short test ...
80
80
Fusion list time         : 3.73274e-009
Flattened proto time     : 3.65824e-009
Long test ...
480
480
Fusion list time         : 2.86484e-006
Flattened proto time     : 9.06944e-007

// GCC
Short test ...
80
80
Fusion list time         : 3.77178e-07
Flattened proto time     : 2.77042e-07
Long test ...
480
480
Fusion list time         : 1.00708e-05
Flattened proto time     : 2.17819e-06


In all cases, flattening all at once with a proto 2nd phase is faster 
than the incremental flattening approach taken by Spirit2. And the 
larger the ET tree, the better a proto 2nd phase looks.

This is a promising direction. You get extra perf *and* the flat 
sequences you want, I get the simple and generic proto I want, and it 
doesn't require that we extend Fusion to support segmentation. (But we 
should, anyway. ;-)


--
Eric Niebler
Boost Consulting
www.boost-consulting.com
/*=============================================================================
    Copyright (c) 2006 Eric Niebler

    Use, modification and distribution is subject to the Boost Software
    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
==============================================================================*/

#define BOOST_PROTO_FUSION_V2
#define FUSION_MAX_LIST_SIZE 25

#ifdef _MSC_VER
// inline aggressively
# pragma inline_recursion(on) // turn on inline recursion
# pragma inline_depth(255)    // max inline depth
#endif

#include <iostream>
#include <boost/timer.hpp>
#include <boost/xpressive/proto/fusion.hpp>
#include <boost/fusion/sequence/container/list.hpp>
#include <boost/fusion/sequence/conversion/as_list.hpp>
#include <boost/fusion/sequence/view/joint_view.hpp>
#include "./for_each_s.hpp"
#include "./segmented_proto.hpp"

#include <boost/xpressive/proto/compiler/fold.hpp>

namespace test
{
    struct flatten_tag {};
}

namespace boost { namespace proto
{
    template<>
    struct compiler<right_shift_tag, test::flatten_tag>
      : reverse_fold_compiler<test::flatten_tag>
    {};

    template<>
    struct compiler<noop_tag, test::flatten_tag>
    {
        template<typename Node, typename State, typename Visitor>
        struct apply
        {
            typedef fusion::cons<Node, State> type;
        };

        template<typename Node, typename State, typename Visitor>
        static fusion::cons<Node, State>
        call(Node const &node, State const &state, Visitor &)
        {
            return fusion::cons<Node, State>(node, state);
        }
    };
}}

namespace test
{
    struct accumulator
    {
        accumulator(int &i_)
          : i(i_)
        {}

        template<typename T>
        void operator()(T const &t) const
        {
            this->i += arg(t);
        }

        int &i;
    };

    int const REPEAT_COUNT = 10;

    template<typename Fun>
    double time_for_each_s(Fun const &fun, int &j)
    {
        boost::timer tim;
        int i = 0;
        long long iter = 65536;
        long long counter, repeats;
        double result = 0;
        double run;
        do
        {
            tim.restart();
            for(counter = 0; counter < iter; ++counter)
            {
                i = 0;
                fun(i);
                static_cast<void>(i);
            }
            result = tim.elapsed();
            iter *= 2;
        } while(result < 0.5);
        iter /= 2;

        // repeat test and report least value for consistency:
        for(repeats = 0; repeats < REPEAT_COUNT; ++repeats)
        {
            tim.restart();
            for(counter = 0; counter < iter; ++counter)
            {
                i = 0;
                fun(i);
                j += i;
            }
            run = tim.elapsed();
            result = (std::min)(run, result);
        }
        std::cout << i << std::endl;
        return result / iter;
    }

    #define EXPR1 (lit(3) >> lit(42)) >> (lit(6) >> lit(29))
    #define EXPR2 EXPR1 >> EXPR1 >> EXPR1 >> EXPR1 >> EXPR1 >> EXPR1

    namespace spirit2
    {
        typedef boost::proto::unary_op<int, boost::proto::noop_tag> int_;

        template<typename List>
        struct sequence
        {
            sequence(List const &e)
              : elements(e)
            {}

            List elements;
        };

        template<>
        struct sequence<boost::fusion::cons<int_> >
        {
            explicit sequence(int i)
              : elements(int_(i))
            {}

            boost::fusion::cons<int_> elements;
        };

        typedef sequence<boost::fusion::cons<int_> > lit;

        template<typename List1, typename List2>
        struct compose
        {
            typedef sequence<
                typename boost::fusion::result_of::as_list<
                    boost::fusion::joint_view<List1 const, List2 const>
                >::type
            > type;
        };

        template<typename List1, typename List2>
        typename compose<List1, List2>::type
        operator >> (sequence<List1> const &list1, sequence<List2> const &list2)
        {
            return typename compose<List1, List2>::type(
                boost::fusion::as_list(
                    boost::fusion::joint_view<List1 const, List2 
const>(list1.elements, list2.elements)
                )
            );
        }
    }

    template<typename Expr>
    typename boost::proto::compile_result<Expr, boost::fusion::nil, 
boost::mpl::void_, flatten_tag>::type
    flatten(Expr const &expr)
    {
        boost::mpl::void_ nil;
        return boost::proto::compile(expr, boost::fusion::nil(), nil, 
flatten_tag());
    }

    struct spirit_short
    {
        void operator ()(int &i) const
        {
            using namespace spirit2;
            boost::fusion::for_each_s((EXPR1).elements, accumulator(i));
        }
    };

    struct proto_short
    {
        void operator ()(int &i) const
        {
            using namespace boost::proto;
            boost::fusion::for_each_s(EXPR1, accumulator(i));
        }
    };

    struct segmented_proto_short
    {
        void operator ()(int &i) const
        {
            using namespace boost::proto;
            boost::fusion::for_each_s(make_segmented_view(EXPR1), 
accumulator(i));
        }
    };

    struct flatten_proto_short
    {
        void operator ()(int &i) const
        {
            using namespace boost::proto;
            boost::fusion::for_each_s(test::flatten(EXPR1), accumulator(i));
        }
    };

    struct spirit_long
    {
        void operator ()(int &i) const
        {
            using namespace spirit2;
            boost::fusion::for_each_s((EXPR2).elements, accumulator(i));
        }
    };

    struct proto_long
    {
        void operator ()(int &i) const
        {
            using namespace boost::proto;
            boost::fusion::for_each_s(EXPR2, accumulator(i));
        }
    };

    struct segmented_proto_long
    {
        void operator ()(int &i) const
        {
            using namespace boost::proto;
            boost::fusion::for_each_s(make_segmented_view(EXPR2), 
accumulator(i));
        }
    };

    struct flatten_proto_long
    {
        void operator ()(int &i) const
        {
            using namespace boost::proto;
            boost::fusion::for_each_s(test::flatten(EXPR2), accumulator(i));
        }
    };

    int test_short()
    {
        int j = 0;

        double list_time =
            time_for_each_s( spirit_short(), j );

        //double non_segmented_time =
        //    time_for_each_s( proto_short(), j );

        //double segmented_time =
        //    time_for_each_s( segmented_proto_short(), j );

        double flatten_proto_time = 
            time_for_each_s( flatten_proto_short(), j );

        std::cout << "Fusion list time         : " << list_time << std::endl;
        //std::cout << "Non-segmented proto time : " << non_segmented_time << 
std::endl;
        //std::cout << "Segmented proto time     : " << segmented_time << 
std::endl;
        std::cout << "Flattened proto time     : " << flatten_proto_time << 
std::endl;

        return j;
    }

    int test_long()
    {
        int j = 0;

        double list_time =
            time_for_each_s( spirit_long(), j );

        //double non_segmented_time =
        //    time_for_each_s( proto_long(), j );

        //double segmented_time =
        //    time_for_each_s( segmented_proto_long(), j );

        double flatten_proto_time = 
            time_for_each_s( flatten_proto_long(), j );

        std::cout << "Fusion list time         : " << list_time << std::endl;
        //std::cout << "Non-segmented proto time : " << non_segmented_time << 
std::endl;
        //std::cout << "Segmented proto time     : " << segmented_time << 
std::endl;
        std::cout << "Flattened proto time     : " << flatten_proto_time << 
std::endl;

        return j;
    }
}

struct display_type
{
    template<typename T>
    void operator ()(T const &t) const
    {
        std::cout << typeid(T).name() << std::endl;
    }
};

int main()
{
    int i = 0, j = 0;
    
    std::cout << "Short test ... \n";
    i = test::test_short();

    std::cout << "Long test ... \n";
    j = test::test_long();

    //using namespace boost::proto;
    //lit(1)(1,2,3);

    return i + j;
}