c++ - 可変長パラメーターの並べ替え

Question

構造体のコンストラクターに提供されるパラメーターの可変長リストを並べ替える必要があることに遭遇しました。型に基づいて並べ替えられた後、パラメーターはタプルとして格納されます。私の質問は、最新の C++ コンパイラ (例: g++-4.7) が不要なロードまたはストア命令を生成しないようにする方法です。つまり、コンストラクターが可変サイズのパラメーターのリストで呼び出されると、パラメーターの型の順序付けに基づいて、各パラメーターを適切な場所に効率的にプッシュします。

これが具体的な例です。すべてのパラメーターの基本型 (参照、右辺値参照、ポインター、または修飾子を除く) がchar、int、または のいずれかであると仮定しますfloat。char基本型のすべてのパラメーターが最初に表示され、その後に基本型のすべてのパラメーターが続くようにするにはどうすればよいですか(基本型のパラメーターを最後intに残します)。floatパラメーターが指定された相対的な順序は、同種の基本型のサブリスト内で違反されるべきではありません。

例:foo::foo()は引数付きで呼び出されますfloat a, char&& b, const float& c, int&& d, char e。タプル tupe は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. 特定のタイプのクエリの実装がはるかに簡単になります (たとえば、タプルに格納されているポインターのいずれかが特定のポインターのエイリアスであるかどうかを確認します)。

ご助力ありがとうございます！

Answer 1

皆様、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 他の誰かが私が持っているものよりもエレガントなものを投稿するまで、私は自分の答えを受け入れるつもりです.

Answer 2

これを試す時間はありませんが、転送された引数を並べ替えるときにコンパイラが大量の移動を生成している場合std::forward_as_tupleは、転送することをお勧めします。タプルは具体的なレイアウトを持つデータ構造であり、それを構築することで、コンパイラーは必要な順序ですべてを一度にメモリーに入れるようになります。

一方、引数をレジスターにプロモートし、単純な関数のスタックをバイパスする可能性は低くなります。また、タプルが純粋な値としてのみ使用される (参照が取得されない) 限り、実際には何も保証されません。 as-if ルールの下では、そのメンバーがアドレスを持つ必要がないためです。

ポインターをグループ化し、より大きな式をタプルの末尾に格納することで、スタック スペースを節約できます。

左辺値参照は ABI によってポインターとして実装されますが、それらをデータ値としてグループ化するように指定します。ネイティブの受け渡しセマンティクスに準拠したい場合は、右辺値参照を左辺値参照と同じように扱う必要があります。(クラス型のみを移動すると仮定します。) したがって、パラメーターを値とポインターのカテゴリに並べ替えてから、それらを基本型で並べ替えたいため、並べ替えの問題は述べられているよりも少し複雑です。

並べ替えアルゴリズム自体については、入力パックからポップして出力タプルのセット、キュー スタイルにプッシュし、出力タプルをstd::tuple_cat. これは実装が最も簡単で、安定しており、コンパイラの一般的なケースの最適化にヒットするはずです。TMPはそのようには機能しないため、メモリ内で実行することを目的としたアルゴリズムを実装しないでください。

並べ替えの結果を、パラメーターを への引数に並べ替える関数に変換することについては、よくわかりforward_as_tupleません。おそらく、インデックスを処理する必要があります。

これらすべてにコミットする前に、そのメリットに見合うだけの価値があることを十分に確認してください。