heap/tools/heap_benchmarks.hpp

/*=============================================================================
    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 <algorithm>
#include <vector>

#include "high_resolution_timer.hpp"
#include <boost/foreach.hpp>

#include <boost/heap/heap_merge.hpp>

#if defined( __GNUC__ ) && ( !defined __INTEL_COMPILER )
#    define no_inline __attribute__( ( noinline ) )
#else
#    define no_inline
#endif

typedef std::vector< int > test_data;

const int num_benchmarks = 1;

inline test_data make_sequential_test_data( int size )
{
    test_data v( size );
    for ( int i = 0; i != size; ++i )
        v[ i ] = i;
    return v;
}

inline test_data make_test_data( int size )
{
    test_data v = make_sequential_test_data( size );
    std::random_shuffle( v.begin(), v.end() );
    return v;
}

const int max_data = 20;

test_data const& get_data( int index )
{
    static std::vector< test_data > data;
    if ( data.empty() )
        for ( int i = 0; i != num_benchmarks; ++i )
            data.push_back( make_test_data( ( 1 << ( max_data + 1 ) ) + 1024 ) );

    return data[ index ];
}


#define DEFINE_BENCHMARKS_SELECTOR( SUFFIX )   \
    struct make_##SUFFIX                       \
    {                                          \
        template < typename heap >             \
        struct rebind                          \
        {                                      \
            typedef run_##SUFFIX< heap > type; \
        };                                     \
    };


template < typename pri_queue >
void fill_heap( pri_queue& q, int index, int size, int offset = 0 )
{
    test_data const& data = get_data( index );

    for ( int i = 0; i != size + 1; ++i ) {
        q.push( data[ i ] );
        int top = q.top();
        q.pop();
        q.push( top );
    }
}

template < typename pri_queue, typename handle_container >
void fill_heap_with_handles( pri_queue& q, handle_container& handles, int index, int size, int offset = 0 )
{
    test_data const& data = get_data( index );

    for ( int i = 0; i != size + 1; ++i ) {
        handles[ i ] = q.push( data[ i ] );

        if ( i > 0 ) {
            typename pri_queue::handle_type last = handles[ i - 1 ];
            int                             val  = *last;
            q.erase( last );
            handles[ i - 1 ] = q.push( val );
        }
    }
}


template < typename pri_queue >
struct run_sequential_push
{
    run_sequential_push( int size ) :
        size( size )
    {}

    void prepare( int index )
    {
        q.clear();
        fill_heap( q, index, size );
    }

    no_inline void operator()( int index )
    {
        test_data const& data = get_data( index );

        for ( int i = 0; i != 16; ++i )
            q.push( data[ ( 1 << max_data ) + i ] );
    }

    pri_queue q;
    int       size;
};

DEFINE_BENCHMARKS_SELECTOR( sequential_push )

template < typename pri_queue >
struct run_sequential_pop
{
    run_sequential_pop( int size ) :
        size( size )
    {}

    void prepare( int index )
    {
        q.clear();
        fill_heap( q, index, size );
    }

    no_inline void operator()( int index )
    {
        for ( int i = 0; i != 16; ++i )
            q.pop();
    }

    pri_queue q;
    int       size;
};

DEFINE_BENCHMARKS_SELECTOR( sequential_pop )

template < typename pri_queue >
struct run_sequential_increase
{
    run_sequential_increase( int size ) :
        size( size ),
        handles( size )
    {}

    void prepare( int index )
    {
        q.clear();
        fill_heap_with_handles( q, handles, index, size );
    }

    no_inline void operator()( int index )
    {
        test_data const& data = get_data( index );
        for ( int i = 0; i != 16; ++i )
            q.increase( handles[ i ], data[ i ] + ( 1 << max_data ) );
    }

    pri_queue                                      q;
    int                                            size;
    std::vector< typename pri_queue::handle_type > handles;
};

DEFINE_BENCHMARKS_SELECTOR( sequential_increase )

template < typename pri_queue >
struct run_sequential_decrease
{
    run_sequential_decrease( int size ) :
        size( size ),
        handles( size )
    {}

    void prepare( int index )
    {
        q.clear();
        fill_heap_with_handles( q, handles, index, size );
    }

    no_inline void operator()( int index )
    {
        test_data const& data = get_data( index );
        for ( int i = 0; i != 16; ++i )
            q.decrease( handles[ i ], data[ i ] + ( 1 << max_data ) );
    }

    pri_queue                                      q;
    int                                            size;
    std::vector< typename pri_queue::handle_type > handles;
};

DEFINE_BENCHMARKS_SELECTOR( sequential_decrease )

template < typename pri_queue >
struct run_merge_and_clear
{
    run_merge_and_clear( int size ) :
        size( size )
    {}

    void prepare( int index )
    {
        q.clear();
        r.clear();

        fill_heap( q, index, size );
        fill_heap( r, index, size, size );
    }

    no_inline void operator()( int index )
    {
        boost::heap::heap_merge( q, r );
    }

    pri_queue q, r;
    int       size;
};

DEFINE_BENCHMARKS_SELECTOR( merge_and_clear )

template < typename pri_queue >
struct run_equivalence
{
    run_equivalence( int size ) :
        size( size )
    {}

    void prepare( int index )
    {
        q.clear();
        r.clear();
        s.clear();

        fill_heap( q, index, size );
        fill_heap( r, index, size, size );
        fill_heap( s, index, size );
    }

    no_inline bool operator()( int index )
    {
        return ( q == r ) ^ ( q == s );
    }

    pri_queue q, r, s;
    int       size;
};

DEFINE_BENCHMARKS_SELECTOR( equivalence )


template < typename benchmark >
inline double run_benchmark( benchmark& b )
{
    boost::high_resolution_timer timer;
    std::vector< double >        results;

    for ( int i = 0; i != num_benchmarks; ++i ) {
        b.prepare( i );
        timer.restart();
        b( i );
        double t = timer.elapsed();
        results.push_back( t );
    }

    return results.at( results.size() / 2 ); // median
}