c++ - 编译时函数的运行时函数分支？

Question

考虑以下形式的编译时函数:

template <unsigned int Value>
constexpr unsigned int function() 
{
    // Just for the example, but it could be very complicated here
    return Value*Value;
}

如何使用模板元编程编写将调用正确编译时版本的运行时等价物，知道 value将永远在 [From, To[ 中区间:

template <unsigned int From, unsigned int To, /* Something here */>
constexpr unsigned int function(const unsigned int value)
{
    // Something here
}

分支到正确的版本应该尽可能快。

例如function<0, 32>(6) (运行时版本)应该调用 function<6>() (编译时版本)。

编辑:解释:我为什么要这样做？这个功能(实际用例)需要尽可能快( super 计算问题)。通过在编译时提供参数，我可以生成非常高效的代码。如果我只是将值从模板参数移动到函数参数，代码会慢 10 到 100 倍。但实际上，此参数的可能值范围并不大(例如 0 和 32 之间):因此在运行时分支到正确的编译时版本会更有效。

Answer 1

最简单的方法是设置递归级联if/recurse链。

#define RETURNS(X) -> decltype(X) { return (X); }

template<unsigned From, unsigned To, typename Target>
struct CallIf {
  constexpr auto operator()( unsigned N )
    RETURNS( (N==From)?Target::template func<From>():CallIf<From+1, To, Target>()( N ) );
};
template<unsigned From, typename Target>
struct CallIf<From, From+1, Target> {
  constexpr auto operator()( unsigned N )
    RETURNS( Target::template func<From>() );
};

struct Func {
  template<unsigned V>
  constexpr unsigned func() const {
    return function<V>();
  }
};

或类似的东西，并依靠编译器折叠 if 链降到一个。 (如果你知道返回类型，你可以去掉那个烦人的 RETURNS 宏，或者如果你有 C++1y 特性，你也可以这样做)。

现在，您可能想将此与在 value 上执行二进制搜索的版本进行比较在该范围内，使用类似的递归调用案例。同样，您可以通过检查和设置编译时值中的位来实现。

template<unsigned From, unsigned To, typename Target>
struct CallIf {
  enum { Mid = From + (To-From)/2 }; // avoid overflow risk
  constexpr auto operator()( unsigned N )
    RETURNS( (N>=Mid)?CallIf<Mid, To, Target>()(N):CallIf<From,Mid,Target>()(N) );
};

对于宽度为 1 的情况具有相同的特化。

另一种方法是设置一个 static function<V> 的调用数组然后在运行时执行数组取消引用:

template<unsigned...> struct indexes {};
template<unsigned Min, unsigned Max, unsigned... Is> struct make_indexes:make_indexes<Min, Max-1, Max-1, Is...> {};
template<unsigned Min, unsigned... Is> struct make_indexes<Min, Min, Is...>:indexes<Is...> {};

template<unsigned From, unsigned To, typename Target>
struct CallIf {
  template<unsigned... Is>
  unsigned Invoke( indexes<Is...>, unsigned N ) const {
    typedef unsigned(*target)();
    static target ts[] = { &(function<Is>)... };
    return ts[N-From]();
  };
  unsigned operator()( unsigned N ) const {
    return Invoke( make_indexes<From, To>(), N );
  }
};

虽然我不确定如何制作上面的 constexpr至少在 C++11 中很容易，我跳过了返回类型推导。

以上都没有经过测试或编译，因此很可能需要一些修复。但核心概念会起作用。特化可能需要一些工作:做 <From, From+1终止是我在实践中没有做过的事情:如果这导致问题，你可以做 <From, Width基于助手，专注于 Width=1 .

我个人称这种技术(体现在上面的 CallIf 类型中)为“魔法开关”，我们将运行时有效并“神奇地”使其成为编译时值。我之所以提到这一点，是因为您可能会通过谷歌搜索 Yakk 和“魔术开关”(以及站点:stackoverflow.com)找到我在堆栈溢出时谈论它的其他变体，其中一些变体已经过编译并附有实时示例。

最后，虽然最后一个版本(手动跳转表)可能是最快的，但如果您经常调用它以致于此调用的速度很关键，您可能不仅要考虑包装调用站点，还要考虑包装在一个神奇的开关中围绕它的算法:更早地进行调度。但是，如果您只是在最后一刻才获得索引，并且您可以使用非 constexpr调用，它应该工作。注意 static将为每个 Function 创建数组和 To和 From用过。