使非constexpr积分值适应非类型模板参数,并使代码膨胀

Question

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

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

包裹在一个类型中size <I>,其中(为简洁起见)

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

当然,我们可以I直接传递,但我想通过使用它作为模板参数强调它是constexpr.函数F在这里是虚拟的,但实际上它可以做各种有用的东西,比如从I元组的元素中检索信息.F假定具有相同的返回类型,无论如何I.I可以是任何整数类型,但假设是非负的.

问题

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

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

现在,如果我们想F用非constepr size_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;地方数组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>();

where f是一个以bool模板为参数的函数.在这种情况下,很明显所有两个可能的版本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内联.

PS.我会添加标签,code-bloat但系统不会让我.

Answer 1

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

据我所知，最有效的方法是构建自己的跳转表。

// 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也可能有用。

活生生的例子