Plantillas de expresiones y C ++ 11

Veamos un beneficio particular de las plantillas de expresión: las ET se pueden usar para evitar temporarios de tamaño vectorial en la memoria que se producen en operadores sobrecargados como:

template<typename T>
std::vector<T> operator+(const std::vector<T>& a, const std::vector<T>& b)
{
  std::vector<T> tmp;   // vector-sized temporary
  for_each(...);
  return tmp;
}

En C ++ 11, la declaración de retorno de esta función aplica la semántica de movimiento. Ninguna copia del vector. Eso es una victoria.

Sin embargo, si miro una expresión simple como

d = a + b + c;

Veo que la función anterior se llama dos veces (para ambosoperator+) mientras que la tarea final se puede hacer con semántica de movimiento.

En total se ejecutan 2 loops. Significa que apagué un temporal y lo volví a leer justo después. Para grandes vectores esto cae fuera de caché. Eso es peor que las plantillas de expresión. Pueden hacer todo en solo 1 bucle. Los ETs pueden ejecutar el código anterior equivalente a:

for(int i=0 ; i < vec_length ; ++i)
  d[i] = a[i] + b[i] + c[i];

Me preguntaba si las lambdas junto con la semántica de movimientos o cualquier otra característica nueva pueden funcionar tan bien como los ETs. ¿Alguna idea?

Editar:

Básicamente, utilizando la técnica ET, el compilador construye un árbol de análisis que se asemeja a la expresión algebraica con su sistema de tipos. Este árbol consta de nodos internos y nodos de hojas. Los nodos internos representan operaciones (suma, multiplicación, etc.) y los nodos de hoja representan referencias a los objetos de datos.

Traté de pensar en todo el proceso de cómputo a la manera de una máquina de pila: tomar una operación de una pila de operaciones y extraer los siguientes argumentos de la pila de argumentos y evaluar la operación. Ponga el resultado de nuevo en la pila esperando la operación.

Para representar estos dos objetos diferentes (pila de operaciones y pila de hojas de datos), agrupé unastd::tuple para las operaciones y unstd::tuple para los datos se deja en unastd::pair<>. Inicialmente utilicé unstd:vector pero eso dio lugar a gastos generales de ejecución.

Todo el proceso se divide en dos fases: la inicialización de la máquina de la pila, donde se inicializan la pila de la operación y el argumento. Y la fase de evaluación que se activa al asignar los contenedores emparejados al vector.

Creé una claseVec que tiene un privadoarray<int,5> (la carga útil) y que cuenta con un operador de asignación sobrecargado que toma la "expresión".

Lo globaloperator* está sobrecargado para todas las combinaciones de tomarVec y "expresión" para permitir el manejo correcto también en el caso donde tenemos más que soloa*b. (Note, cambié este ejemplo educativo a la multiplicación, básicamente para detectar rápidamente elimull en el ensamblador.)

Lo que se hace primero antes de que comience la evaluación es "extraer" los valores de los involucradosVec Objetos e inicializando la pila de argumentos. Eso fue necesario para no tener diferentes tipos de objetos alrededor: vectores indexables y resultados no indexables. Esto es lo que elExtractor es para. Lo bueno de nuevo: se utilizan plantillas Variadic que, en este caso, no generan sobrecarga en el tiempo de ejecución (todo esto se hace en tiempo de compilación).

Todo funciona. La expresión está bien evaluada (también agregué la adición, pero eso queda aquí para que se ajuste al código). Abajo puedes ver la salida del ensamblador. Solo compilación en bruto, exactamente como usted quiere que sea: En-par con la técnica ET.

Resultado. Las nuevas características de lenguaje de C ++ 11 ofrecen las plantillas variadas que (junto con la meta-programación de plantillas) abren el área de cálculo de tiempo de compilación. Mostré aquí cómo se pueden usar los beneficios de las plantillas variadas para producir código tan bueno como con la técnica ET tradicional.

#include<algorithm>
#include<iostream>
#include<vector>
#include<tuple>
#include<utility>
#include<array>



template<typename Target,typename Tuple, int N, bool end>
struct Extractor {
  template < typename ... Args >
  static Target index(int i,const Tuple& t, Args && ... args)
  {
    return Extractor<Target, Tuple,  N+1, 
             std::tuple_size<Tuple>::value == N+1>::
      index(i, t , std::forward<Args>(args)..., std::get<N>(t).vec[i] );
  }
};

template < typename Target, typename Tuple, int N >
struct Extractor<Target,Tuple,N,true>
{
    template < typename ... Args >
    static Target index(int i,Tuple const& t, 
            Args && ... args) { 
      return Target(std::forward<Args>(args)...); }
};

template < typename ... Vs > 
std::tuple<typename std::remove_reference<Vs>::type::type_t...>
extract(int i , const std::tuple<Vs...>& tpl)
{
  return Extractor<std::tuple<typename std::remove_reference<Vs>::type::type_t...>,
           std::tuple<Vs...>, 0,
           std::tuple_size<std::tuple<Vs...> >::value == 0>::index(i,tpl);
}


struct Vec {
  std::array<int,5> vec;
  typedef int type_t;

  template<typename... OPs,typename... VALs>
  Vec& operator=(const std::pair< std::tuple<VALs...> , std::tuple<OPs...> >& e) {
    for( int i = 0 ; i < vec.size() ; ++i ) {
      vec[i] = eval( extract(i,e.first) , e.second );
    }
  }
};




template<int OpPos,int ValPos, bool end>
struct StackMachine {
  template<typename... OPs,typename... VALs>
  static void eval_pos( std::tuple<VALs...>& vals , const std::tuple<OPs...> & ops )
  {
    std::get<ValPos+1>( vals ) =
      std::get<OpPos>(ops).apply( std::get<ValPos>( vals ) , 
                  std::get<ValPos+1>( vals ) );
    StackMachine<OpPos+1,ValPos+1,sizeof...(OPs) == OpPos+1>::eval_pos(vals,ops);
  }
};

template<int OpPos,int ValPos>
struct StackMachine<OpPos,ValPos,true> {
  template<typename... OPs,typename... VALs>
  static void eval_pos( std::tuple<VALs...>& vals , 
            const std::tuple<OPs...> & ops )
  {}
};



template<typename... OPs,typename... VALs>
int eval( const std::tuple<VALs...>& vals , const std::tuple<OPs...> & ops )
{
  StackMachine<0,0,false>::eval_pos(const_cast<std::tuple<VALs...>&>(vals),ops);
  return std::get<sizeof...(OPs)>(vals);
}




struct OpMul {
  static int apply(const int& lhs,const int& rhs)  {
    return lhs*rhs;
  }
};

std::pair< std::tuple< const Vec&, const Vec& > , std::tuple<OpMul> >
operator*(const Vec& lhs,const Vec& rhs)
{
  return std::make_pair( std::tuple< const Vec&, const Vec& >( lhs , rhs ) , 
             std::tuple<OpMul>( OpMul() ) );
}

template<typename... OPs,typename... VALs>
std::pair< std::tuple< const Vec&, VALs... > , std::tuple<OPs...,OpMul> >
operator*(const Vec& lhs,const std::pair< std::tuple< VALs... > , std::tuple<OPs...> >& rhs)
{
  return std::make_pair( std::tuple_cat( rhs.first , std::tuple< const Vec& >(lhs)  ) , 
             std::tuple_cat( rhs.second , std::tuple<OpMul>( OpMul() )  ) );
}

template<typename... OPs,typename... VALs>
std::pair< std::tuple< const Vec&, VALs... > , std::tuple<OPs...,OpMul> >
operator*(const std::pair< std::tuple< VALs... > , std::tuple<OPs...> >& lhs,
      const Vec& rhs)
{
  return std::make_pair( std::tuple_cat( lhs.first , std::tuple< const Vec& >(rhs)  ) , 
             std::tuple_cat( lhs.second , std::tuple<OpMul>( OpMul() ) ) );
}

int main()
{
  Vec d,c,b,a;


  for( int i = 0 ; i < d.vec.size() ; ++i ) {
    a.vec[i] = 10+i;
    b.vec[i] = 20+i;
    c.vec[i] = 30+i;
    d.vec[i] = 0;
  }

  d = a * b * c * a;

  for( int i = 0 ; i < d.vec.size() ; ++i ) 
    std::cout << d.vec[i] << std::endl;
}

Ensamblador generado cong++-4.6 -O3 (Tuve que poner un poco de dependencia de tiempo de ejecución en la inicialización del vector para que el compilador no calcule todo el tiempo de compilación y realmente vea elimull instaructions)

imull   %esi, %edx
imull   32(%rsp), %edx
imull   %edx, %esi
movl    68(%rsp), %edx
imull   %ecx, %edx
movl    %esi, (%rsp)
imull   36(%rsp), %edx
imull   %ecx, %edx
movl    104(%rsp), %ecx
movl    %edx, 4(%rsp)
movl    72(%rsp), %edx
imull   %ecx, %edx
imull   40(%rsp), %edx
imull   %ecx, %edx
movl    108(%rsp), %ecx
movl    %edx, 8(%rsp)
movl    76(%rsp), %edx
imull   %ecx, %edx
imull   44(%rsp), %edx
imull   %ecx, %edx
movl    112(%rsp), %ecx
movl    %edx, 12(%rsp)
movl    80(%rsp), %edx
imull   %ecx, %edx
imull   %eax, %edx
imull   %ecx, %edx
movl    %edx, 16(%rsp)

Respuestas a la pregunta(2)

Su respuesta a la pregunta