Reordenando los parámetros variables

Question

Me he encontrado con la necesidad de reordenar una lista variada de parámetros que se suministra al constructor de una estructura. Después de ser reordenados en función de sus tipos, los parámetros se almacenarán como una tupla. Mi pregunta es cómo se puede hacer para que un compilador moderno de C++ (por ejemplo, g++-4.7) no genere instrucciones innecesarias de carga o almacenamiento. Es decir, cuando se invoca al constructor con una lista de parámetros de tamaño variable, empuja de manera eficiente cada parámetro en función de un orden sobre los tipos de parámetros.

Aquí hay un ejemplo concreto. Suponga que el tipo de base de cada parámetro (sin referencias, referencias de valores r, punteros o calificadores) es char, int o float. ¿Cómo puedo hacer para que todos los parámetros del tipo base char aparezcan primero, seguidos de todos los del tipo base int (que deja los parámetros del tipo base float pasado). El orden relativo en el que se dieron los parámetros no se debe violar dentro de las sublistas de tipo base homogéneo.

Ejemplo: foo::foo() se llama con argumentos float a, char&& b, const float& c, int&& d, char e. La tupla tupe es std::tuple<char, char, int, float, float>, y está construida así: tuple_type{std::move(b), e, std::move(d), a, c}.

Considere la estructura definida a continuación y suponga que la metafunción deduce_reordered_tuple_type ya está implementada. ¿Cómo escribirías el constructor para que funcione según lo previsto? Si cree que el código para deduce_reodered_tuple_type le sería útil, puedo proporcionarlo; es un poco largo.

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)...} {} 
}; 

Editar 1 La técnica que se ha descrito anteriormente no tener aplicaciones en marcos matemáticos que hacen un uso intensivo de las plantillas, plantillas de expresión variadic y metaprogramming con el fin de llevar a cabo procesos en línea agresiva. Supongamos que desea definir un operador que tome el producto de varias expresiones, cada una de las cuales se puede pasar por referencia, referencia a const o referencia de valor r. (En mi caso, las expresiones son tablas de probabilidad condicionales y la operación es el factor producto, pero algo así como la multiplicación de matrices también funciona adecuadamente.)

Necesita acceder a los datos proporcionados por cada expresión para evaluar el producto . En consecuencia, debe mover las expresiones pasadas como referencias rvalue, copiar las expresiones pasadas por referencia a const, y tomar las direcciones de las expresiones pasadas por referencia. Usar la técnica que describo arriba ahora ofrece varios beneficios.

1. Otras expresiones pueden usar una sintaxis uniforme para acceder a los elementos de datos de esta expresión, ya que todo el trabajo de metaprogramación de trabajos pesados ​​se realiza de antemano, dentro de la clase.
2. Podemos ahorrar espacio en la pila agrupando los punteros y almacenando las expresiones más grandes hacia el final de la tupla.
3. La implementación de ciertos tipos de consultas se vuelve mucho más fácil (por ejemplo, verificar si alguno de los punteros almacenados en la tupla alía un puntero dado).

Muchas gracias por su ayuda!

Answer 1

Feliz 4 de julio a todos! OK aquí tienes.

Resulta que g++-4.7 es bastante asombroso al ingresar y crea un código de máquina idéntico según mis pruebas (las instrucciones para reproducir los resultados están debajo del código).

#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; 
} 

Para reproducir los resultados, haga lo siguiente (suponiendo que tiene instalado 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 

Las únicas diferencias que noté fueron cosas como los nombres de las etiquetas; de lo contrario, el código de máquina generado era idéntico.

Editar 1 Voy a aceptar mi propia respuesta hasta que alguien más publique algo más elegante que lo que tengo.

Answer 2

no tengo tiempo para experimentar con esto, pero si su compilador está generando demasiados movimientos cuando permutando argumentos enviados, recomendaría el reenvío a través std::forward_as_tuple.La tupla es una estructura de datos con un diseño concreto, y su construcción alienta al compilador a poner cosas en la memoria de una vez, en el orden que desee.

Por otro lado, es menos probable que promueva argumentos para registros y omita la pila para funciones simples. Y nada está realmente garantizado siempre que la tupla solo se use como un valor puro (no se toma ninguna referencia), porque bajo la regla de si-y-no es necesario que sus miembros tengan ninguna dirección.

Podemos ahorrar espacio en la pila agrupando los punteros y almacenando las expresiones más grandes hacia el final de la tupla.

Las referencias de Lvalue se implementan como punteros por la ABI pero usted especificó agruparlas como valores de datos. Las referencias de Rvalue se deben tratar de la misma manera que las referencias de valor l si se quiere adherir a la semántica de aprobación nativa. (Supongo que solo moverá tipos de clases). Por lo tanto, el problema de clasificación es un poco más complicado que el indicado, porque desea ordenar los parámetros en categorías de valor y de puntero, y luego ordenarlos por tipo de base.

En cuanto al algoritmo de clasificación en sí, trataría simplemente de extraer del paquete de entrada y empujar a un conjunto de tuplas de salida, estilo de cola, y luego catenar las tuplas de salida con std::tuple_cat. Esa será la más simple de implementar, estable y debería alcanzar las optimizaciones de caso común del compilador. No implemente un algoritmo destinado a ejecutarse in situ en la memoria porque TMP no funciona así.

En cuanto a la traducción de los resultados de clasificación en la función que permuta los parámetros en los argumentos a forward_as_tuple, no estoy tan seguro. Probablemente tendrá que lidiar con índices.

Desea estar muy seguro de que el beneficio vale la pena antes de comprometerse con todo esto.