5

F考虑一个带constexpr size_t参数的函数对象I

struct F
{
    template <size_t I>
    constexpr size_t operator()(size <I>) const { return I; }
};

包裹在 typesize <I>中，其中（为简洁起见）

template <size_t N>
using size = std::integral_constant <size_t, N>;

当然，我们可以I直接传递，但我想强调它是 constexpr，将其用作模板参数。函数F在这里是虚拟的，但实际上它可以做各种有用的事情，比如从I元组的第 th 元素中检索信息。F假定无论I. I可以是任何整数类型，但假定为非负数。

问题

给定一个constexpr size_t值，I我们可以调用F

F()(size <I>());

现在，如果我们想F用非 consteprsize_t值调用i怎么办？考虑以下：

constexpr size_t L = 10;
idx <F, L> f;
for (size_t i = 0; i < L; ++i)
    cout << f(i) << " ";

（我为什么需要这个？为了给出一些上下文，我实际上是在尝试将复合迭代器构建到一个容器视图中，该视图表示一系列“连接”（连接）异构容器。这将能够说出类似join(a, b) = c;where数组join(a, b)和c长度相等。但是，i迭代器状态是不是这样constexpr，但子迭代器存储在元组中，需要通过constexpr索引访问。个体value_type的大致一致，因此连接视图可以采用它们的 common_type类型，但是子容器和子迭代器是不同的类型。）

解决方案

在这里，我提出了 struct idx <F, L>，它为此目的调整函数F，假设输入参数小于L. 这实际上可以很好地编译输出

0 1 2 3 4 5 6 7 8 9

这是一个活生生的例子。

idx通过递归地将输入分解i为二进制表示并重建 constexpr 对应项来工作N：

template <typename F, size_t L, size_t N = 0, bool = (N < L)>
struct idx
{
    template <size_t R = 1>
    inline constexpr decltype(F()(size <0>()))
    operator()(size_t I, size <R> = size <R>()) const
    {
        return I%2 ? idx <F, L, N+R>()(--I/2, size <2*R>()) :
               I   ? idx <F, L, N  >()(  I/2, size <2*R>()) :
               F()(size <N>());
    }
};

其中R表示2当前迭代的幂。为了避免无限的模板实例化，对 进行了专门化N >= L，返回F()(size <0>())一个虚拟值：

template <typename F, size_t L, size_t N>
struct idx <F, L, N, false>
{
    template <size_t R>
    inline constexpr decltype(F()(size <0>()))
    operator()(size_t I, size <R>) const { return F()(size <0>()); }
};

事实上，这种方法是更常见的带有布尔参数的成语的概括：

bool b = true;
b ? f <true>() : f <false>();

其中f是一个将 abool作为模板参数的函数。在这种情况下，很明显所有两个可能的版本f都被实例化了。

问题

尽管这可行，并且它的运行时复杂性可能是对数i，但我担心编译时的影响，例如：

  • 有多少idx和 它的组合template operator()被实例化，以便在运行时为i编译时未知的任何输入工作？（我再次理解“所有可能”，但有多少？）

  • 真的可以内联operator()吗？

  • 是否有任何“更容易”编译的替代策略或变体？

  • 我应该忘记这个想法作为纯代码膨胀的实例吗？

笔记

以下是我针对不同值测量的编译时间（以秒为单位）和可执行文件大小（以 KB 为单位）L：

 L      Clang(s)    GCC(s)    Clang(KB)    GCC(KB)
 10       1.3       1.7          33         36
 20       2.1       3.0          48         65
 40       3.7       5.8          87        120
 80       7.0      11.2         160        222
160      13.9      23.4         306        430
320      28.1      47.8         578        850
640      56.5     103.0        1126       1753

因此，尽管它在 中看起来大致呈线性L，但它相当长且大得令人沮丧。

尝试强制operator()内联失败：可能被 Clang 忽略（可执行文件更大），而 GCC 报告recursive inlining.

在可执行文件上运行nm -C，例如 for L = 160，显示511/1253不同版本的operator()（使用 Clang/GCC）。这些都是为了N < L，所以看起来终止的专业化N >= L确实被内联了。

附言。我会添加标签code-bloat，但系统不会让我。

4

4 回答 4

3

我称这种技术为魔法开关。

我所知道的最有效的方法是建立自己的跳跃表。

// first, index list boilerplate.  Does log-depth creation as well
// needed for >1000 magic switches:
template<unsigned...Is> struct indexes {typedef indexes<Is...> type;};
template<class lhs, class rhs> struct concat_indexes;
template<unsigned...Is, unsigned...Ys> struct concat_indexes<indexes<Is...>, indexes<Ys...>>{
    typedef indexes<Is...,Ys...> type;
};
template<class lhs, class rhs>
using ConcatIndexes = typename concat_indexes<lhs, rhs>::type;

template<unsigned min, unsigned count> struct make_indexes:
    ConcatIndexes<
        typename make_indexes<min, count/2>::type,
        typename make_indexes<min+count/2, (count+1)/2>::type
    >
{};
template<unsigned min> struct make_indexes<min, 0>:
    indexes<>
{};
template<unsigned min> struct make_indexes<min, 1>:
    indexes<min>
{};
template<unsigned max, unsigned min=0>
using MakeIndexes = typename make_indexes<min, max-min>::type;

// This class exists simply because [](blah){code}... `...` expansion
// support is lacking in many compilers:
template< typename L, typename R, unsigned I >
struct helper_helper {
    static R func( L&& l ) { return std::forward<L>(l)(size<I>()); }
};
// the workhorse.  Creates an "manual" jump table, then invokes it:
template<typename L, unsigned... Is>
auto
dispatch_helper(indexes<Is...>, L&& l, unsigned i)
-> decltype( std::declval<L>()(size<0>()) )
{
  // R is return type:
  typedef decltype( std::declval<L>()(size<0>()) ) R;
  // F is the function pointer type for our jump table:
  typedef R(*F)(L&&);
  // the jump table:
  static const F table[] = {
    helper_helper<L, R, Is>::func...
  };
  // invoke at the jump spot:
  return table[i]( std::forward<L>(l) );
};
// create an index pack for each index, and invoke the helper to
// create the jump table:
template<unsigned Max, typename L>
auto
dispatch(L&& l, unsigned i)
-> decltype( std::declval<L>()(size<0>()) )
{
  return dispatch_helper( MakeIndexes<Max>(), std::forward<L>(l), i );
};

这需要一些静态设置，但运行时非常快。

一个有界的断言i也可能是有用的。

活生生的例子

于 2014-02-21T19:25:31.703 回答
1

如果您的解决方案对最大可能值有上限（例如 256），您可以使用宏魔法和 switch 语句来简化它：

#define POS(i) case (i): return F<(i)>(); break;
#define POS_4(i) POS(i + 0) POS(i + 1) POS(i + 2) POS(i + 3)
#define POS_16(i) POS_4(i + 0) POS_4(i + 4) POS_4(i + 8) POS_4(i + 12)

int func(int i)
{
    switch(i)
    {
        POS_16(0)
    }
}

另一种可能的解决方案是（使用 C++11）使用可变参数模板：

template<int I>
struct FF
{
    static int f() { return I; }
};


template<typename... I>
int func(int i)
{
    constexpr int (*Func[])() = { I::f... };
    return Func[i]();
}

int main(int argc, char** argv)
{
    func<FF<0>,FF<1>>(1);
}
于 2014-02-21T19:35:53.093 回答
0

我将在这里采取明显的立场，并询问“我想强调它是constexpr通过将其用作模板参数”是否值得这个成本，如果：

struct F
{
    constexpr size_t operator()(size_t i) const { return i; }
    template <size_t I>
    constexpr size_t operator()(size <I>) const { return (*this)(I); }
};

不会是一个更简单的解决方案。

于 2014-02-21T19:25:02.993 回答
0

这不完全是一个答案，我的问题仍然存在，但我找到了一种解决方法，可以显着提高编译速度。这是问题中给出的解决方案的一个小调整，其中参数R从operator()外部移动到结构idx，终止条件现在包括R和N：

template <
    typename F, size_t L,
    size_t R = 1, size_t N = 0, bool = (R < 2 * L && N < L)
>
struct idx //...

整个代码在这个新的实例中给出。

这种方法显然减少了大量不必要的专业化组合R。编译时间和可执行文件大小急剧下降。例如，我能够在 10.7/18.7 秒内使用 Clang/GCC for L = 1<<12(4096) 编译，生成 220/239 KB 的可执行文件。在这种情况下，nm -C显示 546/250 版本的operator().

于 2014-02-21T19:34:25.157 回答