Re: [boost] If boost::fusion is the hammer, then what's the nail?

From: Joel de Guzman (joel_at_[hidden])
Date: 2006-12-15 17:04:13

Gennadiy Rozental wrote:
> "David Abrahams" <dave_at_[hidden]> wrote in message 
> news:87lkl93hlx.fsf_at_pereiro.luannocracy.com...
>> "Gennadiy Rozental" <gennadiy.rozental_at_[hidden]> writes:
>>
>>> This is not clear cut. I do not see in theory why any boost::variant 
>>> based
>>> algorithm couldn't be optimized to almost the same code (module type
>>> switching). On the other hand excessive usage of tuples will cause
>>> appropriate code bloat, eventually leading to code slow down.
>> Not clear cut at all.  When operating on a sequence where all the
>> types are different, the version with variant will be both slower and
>> larger.
> 
> I love these performance "estimations"
> 
> Do you have any numbers to sustain this?

Yes. Dan posted some in my answer to your post in the fusion
review sometime ago. You must've missed it. Here it is again
(see attached). Here's the link to Dan's post:

     http://tinyurl.com/yawqs3

You must've missed it.

We see speed differences as much as 20X. In addition to speed,
notice the variant size too.

Regards,
-- 
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net

/*=============================================================================
    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 FUSION_MAX_VECTOR_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 <algorithm>
#include <vector>
#include <boost/timer.hpp>
#include <boost/fusion/sequence.hpp>
#include <boost/fusion/algorithm.hpp>
#include <boost/variant.hpp>

namespace test
{
    struct accumulator : boost::static_visitor<>
    {
        accumulator(int &i_)
        : i(i_)
        {}

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

        int &i;
    };

    struct variant_accumulator
    {    
        variant_accumulator(int &i_)
        : i(i_)
        {}

        template <typename Variant>
        void operator()(Variant const& v) const
        {
            boost::apply_visitor( accumulator(i), v );
        }

        int &i;
    };

    int const REPEAT_COUNT = 10;

    template<typename T>
    double time_for_each_variant(T const &t, 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;
                std::for_each(t.begin(), t.end(), variant_accumulator(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;
                std::for_each(t.begin(), t.end(), variant_accumulator(i));
                j += i;
            }
            run = tim.elapsed();
            result = (std::min)(run, result);
        }
        std::cout << i << std::endl;
        return result / iter;
    }

    template<typename T>
    double time_for_each_fusion(T const &t, 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;
                boost::fusion::for_each(t, accumulator(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;
                boost::fusion::for_each(t, accumulator(i));
                j += i;
            }
            run = tim.elapsed();
            result = (std::min)(run, result);
        }
        std::cout << i << std::endl;
        return result / iter;
    }

    int test_short()
    {
        int j = 0;
        typedef int T0;
        typedef char T1;
        typedef short T2;
        typedef long T3;
        typedef boost::fusion::vector<T0,T1,T2,T3> fusion_vector_type;
        fusion_vector_type const l(3,42,6,29);

        double fusion_time =
            time_for_each_fusion( l, j );
        
        typedef boost::variant<T0,T1,T2,T3> variant_type;
        std::vector<variant_type> v;
        v.push_back(3);
        v.push_back(42);
        v.push_back(6);
        v.push_back(29);

        double variant_time =
            time_for_each_variant( v, j );

        std::cout << "Fusion vector size                                : " << sizeof(fusion_vector_type) << std::endl;
        std::cout << "Variant vector size (includes vector size + data) : " << (sizeof(variant_type)*4)+sizeof(v) << std::endl;

        std::cout << "Fusion vector time         : " << fusion_time << std::endl;
        std::cout << "Variant time               : " << variant_time << std::endl;

        return j;
    }

    int test_long()
    {
        int j = 0;
        typedef int T0;
        typedef char T1;
        typedef short T2;
        typedef long T3;
        boost::fusion::vector<T0,T1,T2,T3,T0,T1,T2,T3,T0,T1,T2,T3,T0,T1,T2,T3,T0,T1,T2,T3,T0,T1,T2,T3> 
        const l(
            3,42,6,29
           ,3,42,6,29
           ,3,42,6,29
           ,3,42,6,29
           ,3,42,6,29
           ,3,42,6,29);

        double fusion_time =
            time_for_each_fusion( l, j );

        typedef boost::variant<T0,T1,T2,T3> variant_type;
        std::vector<variant_type> v;
        for (int i = 0; i < 6; ++i)
        {
            v.push_back(3);
            v.push_back(42);
            v.push_back(6);
            v.push_back(29);
        }

        double variant_time =
            time_for_each_variant( v, j );

        std::cout << "Fusion vector time         : " << fusion_time << std::endl;
        std::cout << "Variant time               : " << variant_time << std::endl;

        return j;
    }
}

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

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

    return i + j;
}