heap/tools/throughput_benchmarks.cpp

/*=============================================================================
    Copyright (c) 2010 Tim Blechmann

    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)
=============================================================================*/

#include <iomanip>
#include <iostream>


#include "../../../boost/heap/binomial_heap.hpp"
#include "../../../boost/heap/d_ary_heap.hpp"
#include "../../../boost/heap/fibonacci_heap.hpp"
#include "../../../boost/heap/pairing_heap.hpp"
#include "../../../boost/heap/skew_heap.hpp"

#include "heap_benchmarks.hpp"

using namespace std;

template < typename benchmark_selector >
void run_benchmarks_immutable( void )
{
    for ( int i = 4; i != max_data; ++i ) {
        for ( int j = 0; j != 8; ++j ) {
            int size = 1 << i;
            if ( j % 4 == 1 )
                size += 1 << ( i - 3 );
            if ( j % 4 == 2 )
                size += 1 << ( i - 2 );
            if ( j % 4 == 3 )
                size += ( 1 << ( i - 3 ) ) + ( 1 << ( i - 2 ) );
            if ( j >= 4 )
                size += ( 1 << ( i - 1 ) );

            cout << size << "\t";
            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 2 > > >::type benchmark_functor;
                benchmark_functor                                                    benchmark( size );
                double result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 2 >, boost::heap::mutable_< true > > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 4 > > >::type benchmark_functor;
                benchmark_functor                                                    benchmark( size );
                double result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 4 >, boost::heap::mutable_< true > > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 8 > > >::type benchmark_functor;
                benchmark_functor                                                    benchmark( size );
                double result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 8 >, boost::heap::mutable_< true > > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind< boost::heap::binomial_heap< long > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind< boost::heap::fibonacci_heap< long > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind< boost::heap::pairing_heap< long > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef
                    typename benchmark_selector::template rebind< boost::heap::skew_heap< long > >::type benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef
                    typename benchmark_selector::template rebind< boost::heap::skew_heap< long > >::type benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }
            cout << endl;
        }
    }
}

template < typename benchmark_selector >
void run_benchmarks_mutable( void )
{
    for ( int i = 4; i != max_data; ++i ) {
        for ( int j = 0; j != 8; ++j ) {
            int size = 1 << i;
            if ( j % 4 == 1 )
                size += 1 << ( i - 3 );
            if ( j % 4 == 2 )
                size += 1 << ( i - 2 );
            if ( j % 4 == 3 )
                size += ( 1 << ( i - 3 ) ) + ( 1 << ( i - 2 ) );
            if ( j >= 4 )
                size += ( 1 << ( i - 1 ) );

            cout << size << "\t";
            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 2 >, boost::heap::mutable_< true > > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 4 >, boost::heap::mutable_< true > > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::d_ary_heap< long, boost::heap::arity< 8 >, boost::heap::mutable_< true > > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind< boost::heap::binomial_heap< long > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind< boost::heap::fibonacci_heap< long > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind< boost::heap::pairing_heap< long > >::type
                                  benchmark_functor;
                benchmark_functor benchmark( size );
                double            result = run_benchmark( benchmark );
                cout << result << '\t';
            }

            {
                typedef typename benchmark_selector::template rebind<
                    boost::heap::skew_heap< long, boost::heap::mutable_< true > > >::type benchmark_functor;
                benchmark_functor                                                         benchmark( size );
                double result = run_benchmark( benchmark );
                cout << result << '\t';
            }
            cout << endl;
        }
    }
}

int main()
{
    cout << fixed << setprecision( 12 );

    cout << "sequential push" << endl;
    run_benchmarks_immutable< make_sequential_push >();

    cout << endl << "sequential pop" << endl;
    run_benchmarks_immutable< make_sequential_pop >();

    cout << endl << "sequential increase" << endl;
    run_benchmarks_mutable< make_sequential_increase >();

    cout << endl << "sequential decrease" << endl;
    run_benchmarks_mutable< make_sequential_decrease >();

    cout << endl << "merge_and_clear" << endl;
    run_benchmarks_immutable< make_merge_and_clear >();

    cout << endl << "equivalence" << endl;
    run_benchmarks_immutable< make_equivalence >();
}