C++0x の不動点コンビネータを std::ref で高速化する

元ネタ: iorateの日記「 C++0x不動点コンビネータ
http://d.hatena.ne.jp/iorate/20110729/1311949434


上の記事の不動点コンビネータは,再帰の度に毎回 std::function を生成しているため,かなり遅いですが,
std::function は, std::reference_wrapper で包まれた関数オブジェクトを渡された場合に
動的メモリ確保を省いて速度を改善することができるので,試しに std::ref で包んで,オリジナルと比較してみました.


ソースコード

#include <utility>
#include <functional>

namespace pezzi
{
  // ref 版
  struct fix1_t
  {
    template< class F >
    struct result
    {
      typedef result<F> self_type;
      
      F f;
      
      template< class... Args,
        class Result = decltype (
          std::declval<F const&>()(
            std::ref( std::declval<self_type const&>() ),
            std::declval<Args>()...
          )
        )
      >
      Result operator()( Args&&... args ) const
      {
        return f( std::ref(*this), std::forward<Args>(args)... );
      }
      
    };
    
    template< class F >
    constexpr auto operator()( F && f )
      -> result<typename std::decay<F>::type>
    {
      return { std::forward<F>(f) };
    }
    
  };
  constexpr fix1_t fix1 = {};
  
  // オリジナル
  struct fix2_t
  {
    template< class F >
    struct result
    {
      typedef result<F> self_type;
      
      F f;
      
      template< class... Args,
        class Result = decltype (
          std::declval<F const&>()(
            std::declval<self_type const&>(),
            std::declval<Args>()...
          )
        )
      >
      Result operator()( Args&&... args ) const
      {
        return f( *this, std::forward<Args>(args)... );
      }
      
    };
    
    template< class F >
    constexpr auto operator()( F && f )
      -> result<typename std::decay<F>::type>
    {
      return { std::forward<F>(f) };
    }
    
  };
  constexpr fix2_t fix2 = {};
  
} // namespace pezzi

#include <boost/progress.hpp>
#include <iostream>

int main()
{
  // boost::progress_timer t;
  
  // 竹内関数でテスト
  auto tarai_ = []( std::function<int (int, int, int)> f, int x, int y, int z ) { 
    return ( x <= y ) ? y : f( f( x-1, y, z ), f( y-1, z, x ), f( z-1, x, y ) );
  };
  
  auto tarai1 = pezzi::fix1( tarai_ );
  auto tarai2 = pezzi::fix2( tarai_ );
  
  {
    std::cout << "ref版:\n";
    boost::progress_timer t;
    std::cout << tarai1( 12, 6, 0 ) << '\n';
  }
  {
    std::cout << "オリジナル:\n";
    boost::progress_timer t;
    std::cout << tarai2( 12, 6, 0 ) << '\n';
  }
  
}


結果( gcc-4.6.1, -O3, Cygwin ):

ref版:
12
0.19 s

オリジナル:
12
5.27 s


std::ref 最強伝説.

// 実際には非参照の場合の std::function が遅いだけだと思いますが.