variant_sequence_benchmark.cpp

/* Performance measurements of a fast collection type for
* heterogeneous objects.
*
* Copyright (c) 2015 Jamboree
* Copyright 2015 Joaquin M Lopez Munoz.
* Distributed under 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)
*/

#include <algorithm>
#include <array>
#include <chrono>
#include <numeric> 
#include <tuple>

std::chrono::high_resolution_clock::time_point measure_start, measure_pause;

template<typename F>
double measure(F f)
{
    using namespace std::chrono;

    static const int              num_trials = 10;
    static const milliseconds     min_time_per_trial(200);
    std::array<double, num_trials> trials;
    static decltype(f())          res; /* to avoid optimizing f() away */

    for (int i = 0;i<num_trials;++i) {
        int                               runs = 0;
        high_resolution_clock::time_point t2;

        measure_start = high_resolution_clock::now();
        do {
            res = f();
            ++runs;
            t2 = high_resolution_clock::now();
        } while (t2 - measure_start<min_time_per_trial);
        trials[i] = duration_cast<duration<double>>(t2 - measure_start).count() / runs;
    }
    (void)res; /* var not used warn */

    std::sort(trials.begin(), trials.end());
    return std::accumulate(
        trials.begin() + 2, trials.end() - 2, 0.0) / (trials.size() - 4);
}

void pause_timing()
{
    measure_pause = std::chrono::high_resolution_clock::now();
}

void resume_timing()
{
    measure_start += std::chrono::high_resolution_clock::now() - measure_pause;
}

#include <boost/config.hpp>
#include <cstddef>
#include <map>
#include <memory>
#include <random>
#include <typeindex>
#include <type_traits>
#include <vector>

namespace variant_sequence_detail
{
    struct span
    {
        int which;
        std::size_t length;
    };

    using span_list = std::vector<span>;

    template<int N, class... T>
    struct match
    {
        static void get();
    };

    template<int N, class T, class... Ts>
    struct match<N, T, Ts...> : match<N + 1, Ts...>
    {
        using match<N + 1, Ts...>::get;

    static std::integral_constant<int, N> get(T)
    {
        return{};
    }
    };

    template<class F, int N>
    void entry_fn(F& f, std::size_t length)
    {
        f(std::integral_constant<int, N>{}, length);
    }

    template<class F, std::size_t... N>
    inline void visit_span(span const& s, F& f, std::integer_sequence<std::size_t, N...>)
    {
        using fn_ptr = void(*)(F&, std::size_t);
        static fn_ptr vtable[sizeof...(N)] = { &entry_fn<F, N>... };
        vtable[s.which](f, s.length);
    }

    template<class Seqs, std::size_t... N>
    inline auto get_begins(Seqs& seqs, std::integer_sequence<std::size_t, N...>)
    {
        return std::make_tuple(std::get<N>(seqs).begin()...);
    }

    template<class Seq, class F>
    inline bool for_each_seq(Seq& seq, F& f)
    {
        for (auto& e : seq)
            f(e);
        return true;
    }

    template<class Seqs, class F, std::size_t... N>
    inline void for_each_unordered(Seqs& seqs, F& f, std::integer_sequence<std::size_t, N...>)
    {
        std::initializer_list<bool>
        {
            for_each_seq(std::get<N>(seqs), f)...
        };
    }

    template<class Seqs, class F>
    inline void for_each(span_list const& spans, Seqs& seqs, F& f)
    {
        std::make_index_sequence<std::tuple_size<Seqs>::value> expand;
        auto visitor([&f, begins(get_begins(seqs, expand))](auto idx, std::size_t length) mutable
        {
            auto it = std::get<decltype(idx)::value>(begins);
            auto end = it + length;
            for (; it != end; ++it)
                f(*it);
            std::get<decltype(idx)::value>(begins) = end;
        });
        for (auto const& span : spans)
        {
            visit_span(span, visitor, expand);
        }
    }
}

template<class... T>
struct variant_sequence
{
    std::tuple<std::vector<T>...> _seqs;
    variant_sequence_detail::span_list _spans;

    template<class U>
    void push_back(U u)
    {
        using variant_sequence_detail::match;
        constexpr int idx = decltype(match<0, T...>::get(std::declval<U>()))::value;
        std::get<idx>(_seqs).push_back(std::forward<U>(u));
        if (!_spans.empty())
        {
            auto& last = _spans.back();
            if (last.which == idx)
            {
                ++last.length;
                return;
            }
        }
        _spans.push_back({ idx, 1 });
    }

    template<class F>
    void for_each(F&& f)
    {
        variant_sequence_detail::for_each(_spans, _seqs, f);
    }

    template<class F>
    void for_each(F&& f) const
    {
        variant_sequence_detail::for_each(_spans, _seqs, f);
    }

    template<class F>
    void for_each_unordered(F&& f)
    {
        std::make_index_sequence<sizeof...(T)> expand;
        variant_sequence_detail::for_each_unordered(_seqs, f, expand);
    }

    template<class F>
    void for_each_unordered(F&& f) const
    {
        std::make_index_sequence<sizeof...(T)> expand;
        variant_sequence_detail::for_each_unordered(_seqs, f, expand);
    }
};

#include <functional>
#include <iostream>
#include <boost/variant.hpp>

struct struct1
{
    struct1(int n) :n(n) {}
    int f(int x)const { return x*n; }

    int n;
};

struct struct2
{
    struct2(int n) :n(n) {}
    int f(int x)const { return x + n; }

    int unused, n;
};

struct struct3
{
    struct3(int n) :n(n) {}
    int f(int x)const { return x - n; }

    int unused, n;
};

template<typename Collection>
struct fill
{
    void operator()(Collection& c, unsigned int n)const
    {
        n /= 3;
        while (n--) {
            c.push_back(struct1(n));
            c.push_back(struct2(n));
            c.push_back(struct3(n));
        }
    }
};

template<typename Collection>
struct fill_sorted
{
    void operator()(Collection& c, unsigned int n)const
    {
        n /= 3;
        for (int i = n;i--;)c.push_back(struct1(n));
        for (int i = n;i--;)c.push_back(struct2(n));
        for (int i = n;i--;)c.push_back(struct3(n));
    }
};


struct visitor :boost::static_visitor<void>
{
    visitor(int& res) :res(res) {};

    template<typename T>
    void operator()(const T& x)const
    {
        res += x.f(1);
    }

    int& res;
};

template<typename Collection>
struct run_for_each_het
{
    typedef int result_type;

    result_type operator()(const Collection& c)const
    {
        int res = 0;
        c.for_each(visitor(res));
        return res;
    }
};

template<typename Collection>
struct run_for_each_het_unordered
{
    typedef int result_type;

    result_type operator()(const Collection& c)const
    {
        int res = 0;
        c.for_each_unordered(visitor(res));
        return res;
    }
};

template<typename Collection>
struct run_for_each_variant
{
    typedef int result_type;

    result_type operator()(const Collection& c)const
    {
        typedef typename Collection::value_type value_type;
        int     res = 0;
        visitor visit(res);
        std::for_each(
            c.begin(), c.end(),
            [&](const value_type& v) {boost::apply_visitor(visit, v);});
        return res;
    }
};

template<
    template<typename> class Tester,
    template<typename> class Filler,
    typename Collection
>
double measure_test(unsigned int n)
{
    Collection         c;
    Filler<Collection> f;
    f(c, n);
    double t = measure(std::bind(Tester<Collection>(), std::cref(c)));
    return (t / n)*10E6;
}

int main()
{
    typedef variant_sequence<struct1, struct2, struct3>              collection_t1;
    typedef std::vector<boost::variant<struct1, struct2, struct3>> collection_t2;

    static unsigned int ns[] = { 1000,10000,100000,10000000 };

    std::cout << "variant_sequence(no-order);variant_sequence;variant_sequence(sorted);vector_variant;" << std::endl;
    std::cout << "for_each:" << std::endl;
    for (auto n : ns) {
        std::cout <<
            n << ";" <<
            measure_test<run_for_each_het_unordered, fill, collection_t1>(n) << ";" <<
            measure_test<run_for_each_het, fill, collection_t1>(n) << ";" <<
            measure_test<run_for_each_het, fill_sorted, collection_t1>(n) << ";" <<
            measure_test<run_for_each_variant, fill, collection_t2>(n) << ";" << std::endl;
    }
}