10

我遇到了重新排序提供给结构构造函数的可变参数列表的需要。根据类型重新排序后，参数将存储为元组。我的问题是如何做到这一点，以便现代 C++ 编译器（例如g++-4.7）不会生成不必要的加载或存储指令。也就是说，当使用可变大小的参数列表调用构造函数时，它会根据参数类型的排序有效地将每个参数推送到位。

这是一个具体的例子。假设每个参数的基本类型（没有引用、右值引用、指针或限定符）是char、int或float。我怎样才能使它char首先出现所有基本类型的参数，然后是所有基本类型int的参数（最后留下基本类型的参数float）。在同类基本类型的子列表中，不应违反给定参数的相对顺序。

示例：foo::foo()使用 arguments 调用float a, char&& b, const float& c, int&& d, char e。元组元组是std::tuple<char, char, int, float, float>，它的构造如下tuple_type{std::move(b), e, std::move(d), a, c}：

考虑下面定义的结构，并假设元功能deduce_reordered_tuple_type已经实现。您将如何编写构造函数以使其按预期工作？如果您认为 , 的代码对deduce_reodered_tuple_type您有用，我可以提供；有点长。

template <class... Args> struct foo
{
    // Assume that the metafunction deduce_reordered_tuple_type is defined.
    typedef typename deduce_reordered_tuple_type<Args...>::type tuple_type;
    tuple_type t_;

    foo(Args&&... args) : t_{reorder_and_forward_parameters<Args>(args)...} {}
};

编辑 1 我上面描述的技术确实在数学框架中有应用，这些框架大量使用表达式模板、可变参数模板和元编程来执行积极的内联。假设您希望定义一个运算符，该运算符采用多个表达式的乘积，每个表达式都可以通过引用、对 const 的引用或右值引用传递。（在我的例子中，表达式是条件概率表，运算是因子乘积，但矩阵乘法之类的东西也适用。）

您需要访问每个表达式提供的数据才能评估产品。因此，您必须移动作为右值引用传递的表达式，将通过引用传递的表达式复制到 const，并获取通过引用传递的表达式的地址。使用我上面描述的技术现在带来了几个好处。

  1. 其他表达式可以使用统一的语法来访问该表达式的数据元素，因为所有繁重的元编程工作都是在类中预先完成的。
  2. 我们可以通过将指针组合在一起并将较大的表达式存储在元组末尾来节省堆栈空间。
  3. 实现某些类型的查询变得容易得多（例如检查存储在元组中的任何指针是否为给定指针起别名）。

非常感谢您的帮助！

4

2 回答 2

4

大家7月4日快乐！好的，给你。

事实证明，g++-4.7在 iniling 方面非常棒，并根据我的测试创建了相同的机器代码（重现结果的说明在代码下方）。

#include <iostream>
#include <tuple>
#include <typeinfo>
#include <type_traits>

template <class... Args>
struct sequence
{
    typedef std::tuple<Args...> tuple_type;
};

template <class U, class V>
struct sequence_cat;

template <class... U, class... V>
struct sequence_cat<sequence<U...>, sequence<V...>>
{
    typedef sequence<U..., V...> type;
};

template <class... V>
struct sequence_cat<void, sequence<V...>>
{
    typedef sequence<V...> type;
};

template <class... U>
struct sequence_cat<sequence<U...>, void>
{
    typedef sequence<U...> type;
};

template <>
struct sequence_cat<void, void>
{
    typedef void type;
};

template <class T>
struct undecorate
{
    typedef typename std::remove_reference<T>::type noref_type;
    typedef typename std::remove_pointer<noref_type>::type noptr_type;
    typedef typename std::remove_cv<noptr_type>::type type;
};

template <class T>
struct deduce_storage_type
{
    typedef T type;
};

template <class T>
struct deduce_storage_type<T&>
{
    typedef T* type;
};

template <class T>
struct deduce_storage_type<const T&>
{
    typedef T type;
};

template <class T>
struct deduce_storage_type<T&&>
{
    typedef T type;
};

template <class T, class... Args>
struct filter_type;

template <class T, class Arg, class... Args>
struct filter_type<T, Arg, Args...>
{
    static constexpr bool pred = 
    std::is_same<typename undecorate<Arg>::type, T>::value;

    typedef typename deduce_storage_type<Arg>::type storage_type;

    typedef typename
    std::conditional<
        pred,
        typename sequence_cat<
            sequence<storage_type>,
            typename filter_type<T, Args...>::type
        >::type,
        typename filter_type<T, Args...>::type
    >::type type;       
};

template <class T, class Arg>
struct filter_type<T, Arg>
{
    static constexpr bool pred =
    std::is_same<typename undecorate<Arg>::type, T>::value;

    typedef typename deduce_storage_type<Arg>::type storage_type;

    typedef typename
    std::conditional<pred, sequence<storage_type>, void>::type
    type;
};

template <class... Args>
struct deduce_sequence_type
{
    typedef typename filter_type<char, Args...>::type char_sequence;
    typedef typename filter_type<int, Args...>::type int_sequence;
    typedef typename filter_type<float, Args...>::type float_sequence;

    typedef typename
    sequence_cat<
        char_sequence,
        typename sequence_cat<
            int_sequence,
            float_sequence
        >::type
    >::type type;
};

template <class T>
struct get_storage_type
{
    static T apply(T t) { return t; }
};

template <class T>
struct get_storage_type<T&>
{
    static T* apply(T& t) { return &t; }
};

template <class T>
struct get_storage_type<const T&>
{
    static T apply(const T& t) { return t; }
};

template <class T>
struct get_storage_type<T&&>
{
    static T&& apply(T&& t) { return std::move(t); }
};

template <class T, class Arg>
struct equals_undecorated_type
{
    static constexpr bool value =
    std::is_same<typename undecorate<Arg>::type, T>::value;
};

template <bool Pred, bool IsNextVoid, class T, class... Args>
struct filter_parameter_impl;

template <class T, class Arg1, class Arg2, class... Args>
struct filter_parameter_impl<false, false, T, Arg1, Arg2, Args...>
{
    typedef typename filter_type<T, Arg2, Args...>::type sequence_type;
    typedef typename sequence_type::tuple_type tuple_type;

    static constexpr bool pred = equals_undecorated_type<T, Arg2>::value;

    static constexpr bool is_next_next_void =
    std::is_same<typename filter_type<T, Args...>::type, void>::value;

    static tuple_type apply(Arg1&&, Arg2&& arg2, Args&&... args)
    {
        return filter_parameter_impl<
            pred, is_next_next_void, T, Arg2, Args...
        >::apply(
            std::forward<Arg2>(arg2),
            std::forward<Args>(args)...
        );
    }
};

template <class T, class Arg1, class Arg2, class... Args>
struct filter_parameter_impl<false, true, T, Arg1, Arg2, Args...>
{
    static void apply(Arg1&&, Arg2&&, Args&&...) {}
};

template <class T, class Arg1, class Arg2, class... Args>
struct filter_parameter_impl<true, false, T, Arg1, Arg2, Args...>
{
    typedef typename
    filter_type<T, Arg1, Arg2, Args...>::type
    sequence_type;

    typedef typename sequence_type::tuple_type tuple_type;

    static constexpr bool pred = equals_undecorated_type<T, Arg2>::value;

    static constexpr bool is_next_next_void =
    std::is_same<typename filter_type<T, Args...>::type, void>::value;

    static tuple_type apply(Arg1&& arg1, Arg2&& arg2, Args&&... args)
    {
        return std::tuple_cat(
            std::make_tuple(get_storage_type<Arg1>::apply(arg1)),
            filter_parameter_impl<
                pred, is_next_next_void, T, Arg2, Args...
            >::apply(
                std::forward<Arg2>(arg2),
                std::forward<Args>(args)...
            )
        );
    }
};

template <class T, class Arg1, class Arg2, class... Args>
struct filter_parameter_impl<true, true, T, Arg1, Arg2, Args...>
{
    typedef typename filter_type<T, Arg1>::type sequence_type;
    typedef typename sequence_type::tuple_type tuple_type;

    static tuple_type apply(Arg1&& arg1, Arg2&&, Args&&...)
    {
        return std::make_tuple(get_storage_type<Arg1>::apply(
            std::forward<Arg1>(arg1)
        ));
    }
};

template <class T, class Arg1, class Arg2>
struct filter_parameter_impl<false, false, T, Arg1, Arg2>
{
    typedef typename filter_type<T, Arg2>::type sequence_type;
    typedef typename sequence_type::tuple_type tuple_type;

    static tuple_type apply(Arg1&&, Arg2&& arg2)
    {
        return std::make_tuple(get_storage_type<Arg2>::apply(
            std::forward<Arg2>(arg2)
        ));
    }
};

template <class T, class Arg1, class Arg2>
struct filter_parameter_impl<false, true, T, Arg1, Arg2>
{
    static void apply(Arg1&&, Arg2&&) {}
};

template <class T, class Arg1, class Arg2>
struct filter_parameter_impl<true, false, T, Arg1, Arg2>
{
    typedef typename filter_type<T, Arg1>::type sequence_type;
    typedef typename sequence_type::tuple_type tuple_type;

    static tuple_type apply(Arg1&& arg1, Arg2&& arg2)
    {
        return std::make_tuple(
            get_storage_type<Arg1>::apply(std::forward<Arg1>(arg1)),
            get_storage_type<Arg2>::apply(std::forward<Arg2>(arg2))
        );
    }
};

template <class T, class Arg1, class Arg2>
struct filter_parameter_impl<true, true, T, Arg1, Arg2>
{
    typedef typename filter_type<T, Arg1, Arg2>::type sequence_type;
    typedef typename sequence_type::tuple_type tuple_type;

    static tuple_type apply(Arg1&& arg1, Arg2&&)
    {
        return std::make_tuple(
            get_storage_type<Arg1>::apply(std::forward<Arg1>(arg1))
        );
    }
};

template <class T, class... Args>
struct filter_parameter;

template <class T, class Arg, class... Args>
struct filter_parameter<T, Arg, Args...>
{
    typedef typename filter_type<T, Arg, Args...>::type sequence_type;

    typedef typename std::conditional<
        std::is_same<sequence_type, void>::value,
        void,
        typename sequence_type::tuple_type
    >::type tuple_type;

    static constexpr bool pred = equals_undecorated_type<T, Arg>::value;

    static constexpr bool is_next_void =
    std::is_same<typename filter_type<T, Args...>::type, void>::value;

    static tuple_type apply(Arg&& arg, Args&&... args)
    {
        return filter_parameter_impl<
            pred, is_next_void, T, Arg, Args...
        >::apply(std::forward<Arg>(arg), std::forward<Args>(args)...);
    }
};

template <bool Is1Void, bool Is2Void, bool Is3Void, class... Args>
struct get_tuple_impl;

template <class... Args>
struct get_tuple_impl<false, false, false, Args...>
{
    typedef typename deduce_sequence_type<Args...>::type sequence_type;
    typedef typename sequence_type::tuple_type tuple_type;

    static tuple_type apply(Args&&... args)
    {
        return std::tuple_cat(
            filter_parameter<char, Args...>::apply(
                std::forward<Args>(args)...
            ),
            filter_parameter<int, Args...>::apply(
                std::forward<Args>(args)...
            ),
            filter_parameter<float, Args...>::apply(
                std::forward<Args>(args)...
            )
        );
    }
};

template <class... Args>
struct get_tuple
{
    typedef typename deduce_sequence_type<Args...>::type sequence_type;

    typedef typename std::conditional<
        std::is_same<sequence_type, void>::value,
        void,
        typename sequence_type::tuple_type
    >::type tuple_type;

    static constexpr bool is1void =
    std::is_same<typename filter_type<char, Args...>::type, void>::value;
    static constexpr bool is2void =
    std::is_same<typename filter_type<int, Args...>::type, void>::value;
    static constexpr bool is3void =
    std::is_same<typename filter_type<float, Args...>::type, void>::value;

    static tuple_type apply(Args&&... args)
    {
        return get_tuple_impl<is1void, is2void, is3void, Args...>::
            apply(std::forward<Args>(args)...);
    }
};

template <class... Args>
struct foo
{
    typedef typename deduce_sequence_type<Args...>::type sequence_type;
    typedef typename sequence_type::tuple_type tuple_type;

    tuple_type t_;

    foo(Args&&... args) : t_{} {}
};

int main()
{
    char a = 5;
    const int b = 6;
    float c = 7;
    int d = 8;
    float e = 9;
    char f = 10;

    auto x = get_tuple<char&, const int&, float&, int&, float&&, char&>::
        apply(a, b, c, d, std::move(e), f);
    //std::tuple<char*, char*, int, int*, float*, float> x{&a, &f, b, &d, &c, std::move(f)};

    std::cout << typeid(x).name() << std::endl;

    return 0;
}

为了重现结果，请执行以下操作（假设您已安装 g++-4.7）。

g++ -std=c++11 -Wall -Ofast -march=native variadic_reorder.cpp -S -o with_templates.s
// Comment out the line in main, and comment the line containing auto x, as well as the line below it.
g++ -std=c++11 -Wall -Ofast -march=native variadic_reorder.cpp -S -o without_templates.s
vimdiff with_templates.s without_templates.s

我注意到的唯一区别是标签名称之类的东西。否则，生成的机器代码是相同的。

编辑 1 我将接受我自己的答案，直到其他人发布比我所拥有的更优雅的东西。

于 2012-07-04T10:06:54.437 回答
1

我没有时间对此进行试验，但是如果您的编译器在排列转发参数时生成了太多动作，我建议通过std::forward_as_tuple. 元组是具有具体布局的数据结构，构建它会鼓励编译器按照您想要的顺序将所有内容一次全部放入内存。

另一方面，它不太可能将参数提升到寄存器并绕过简单函数的堆栈。只要元组仅用作纯值（不进行引用），就没有任何保证，因为在 as-if 规则下，它的成员不需要任何地址。

我们可以通过将指针组合在一起并将较大的表达式存储在元组末尾来节省堆栈空间。

左值引用由 ABI 实现为指针，但您指定将它们分组为数据值。如果要遵守本机传递语义，则应将右值引用视为与左值引用相同。（我假设你只会移动类类型。）所以排序问题比所说的稍微复杂一些，因为你想将参数排序为值和指针类别，然后按基类型对它们进行排序。

至于排序算法本身，我会尝试从输入包中弹出并推送到一组输出元组，队列样式，然后将输出元组与std::tuple_cat. 这将是最简单的实现，稳定的，并且应该达到编译器的常见情况优化。不要实现旨在在内存中就地运行的算法，因为 TMP 不能那样工作。

至于将排序结果转换为将参数置换为参数的函数forward_as_tuple，我不太确定。您可能必须处理索引。

在承诺所有这些之前，您要非常确定这些好处是值得的。

于 2012-07-03T07:29:52.023 回答