usando - ejercicios ciclo for c++

¿Plantilla de un bucle ''para'' en C++?

Question

Tengo un fragmento de C ++ a continuación con un tiempo for ejecución for bucle,

for(int i = 0; i < I; i++)
  for (int j = 0; j < J; j++)
    A( row(i,j), column(i,j) ) = f(i,j);

El fragmento se llama repetidamente. Los límites del bucle ''I'' y ''J'' se conocen en tiempo de compilación (I / J son del orden de 2 a 10). Me gustaría desenrollar los bucles de alguna manera usando plantillas. El cuello de botella principal son las funciones row () y column () y f (). Me gustaría reemplazarlos con metaprogramas equivalentes que se evalúen en tiempo de compilación, usando la row<i,j>::enum trucos de row<i,j>::enum .

Lo que realmente me encantaría es algo que eventualmente resuelve el bucle en una secuencia de declaraciones como:

A(12,37) = 0.5;
A(15,23) = 0.25;
A(14,45) = 0.25;

Pero me gustaría hacerlo sin destrozar demasiado la estructura. Algo en el espíritu de:

TEMPLATE_FOR<i,0,I>
  TEMPLATE_FOR<j,0,J>
     A( row<i,j>::value, column<i,j>::value ) = f<i,j>::value

¿Puede boost :: lambda (o algo más) ayudarme a crear esto?

Answer 1

Echa un vistazo a los metaprogramas de plantillas y las implementaciones de tipo burbuja .

Answer 2

Esta es la forma de hacerlo directamente:

template <int i, int j>
struct inner
{
  static void value()
  {
    A(row<i,j>::value, column<i,j>::value) = f<i,j>::value;
    inner<i, j+1>::value();
  }
};

template <int i> struct inner<i, J> { static void value() {} };

template <int i>
struct outer
{
  static void value()
  {
    inner<i, 0>::value();
    outer<i+1>::value();
  }
};

template <> struct outer<I> { static void value() {} };

void test()
{
  outer<0>::value();
}

Puede pasar de A través como parámetro a cada uno de los value s si es necesario.

Aquí hay una manera con plantillas variadas que no requieren I y J codificadas:

#include <utility>

template <int j, class Columns>
struct Inner;

template <class Columns, class Rows>
struct Outer;

template <int j, int... i>
struct Inner<j, std::index_sequence<i...>>
{
  static void value() { (A(column<i, j>::value, row<i, j>::value), ...); }
};


template <int... j, class Columns>
struct Outer<std::index_sequence<j...>, Columns>
{
  static void value() { (Inner<j, Columns>::value(), ...); }
};

template <int I, int J>
void expand()
{
  Outer<std::make_index_sequence<I>, std::make_index_sequence<J>>::value();
}

void test()
{
  expand<3, 5>();
}

(fragmento con el ensamblaje generado: https://godbolt.org/g/DlgmEl )

Answer 3

No soy un fanático de la meta-programación de plantillas, así que querrás tomar esta respuesta con una pizca de sal. Pero, antes de invertir tiempo en este problema, me preguntaba lo siguiente:

1. ¿Mi bucle for un cuello de botella?
2. ¿Desenrollarlo va a hacer alguna diferencia? Fácilmente probado por mano enrollando y midiendo.

En muchos compiladores / CPU, la versión "en bucle" puede ofrecer un mejor rendimiento debido a los efectos de caché.

Recuerde: mida primero, optimice más tarde, si es que lo hace.

Answer 4

Nunca he tratado de hacer esto, así que tome esta idea con un grano de sal ...

Parece que podrías usar Boost.Preprocessor para realizar el desenrollado del bucle (específicamente las macros BOOST_PP_FOR y BOOST_PP_FOR_r ) y luego usar plantillas para generar la expresión constante real.

Answer 5

Podrías usar Boost MPL .

Un ejemplo de desenrollado de bucle se encuentra en esta página mpl :: for_each .

for_each< range_c<int,0,10> >( value_printer() );

No parece que todo se haya evaluado en el momento de la compilación, pero puede ser un buen punto de partida.

Answer 6

Puedes usar Boost.Mpl para implementar todo esto en tiempo de compilación, pero no estoy seguro de que sea más rápido. (Mpl esencialmente reimplementa todos los algoritmos STL como plantillas de metaprogramación en tiempo de compilación)

El problema con este enfoque es que terminas desenrollando e insertando una gran cantidad de código, lo que puede sacudir el caché de instrucciones y consumir el ancho de banda de memoria que podría haberse guardado. Eso puede producir código enorme, inflado y lento.

Probablemente preferiría confiar en el compilador para alinear las funciones que tienen sentido. Siempre que las definiciones de las funciones de row y column sean visibles desde el bucle, el compilador puede alinear las llamadas trivialmente y desenrollar tantas iteraciones como considere beneficioso.

Answer 7

Si está dispuesto a modificar un poco la sintaxis, puede hacer algo como esto:

template <int i, int ubound>
struct OuterFor {
    void operator()() {
        InnerFor<i, 0, J>()();
        OuterFor<i + 1, ubound>()();
    }
};

template <int ubound>
struct OuterFor <ubound, ubound> {
    void operator()() {
    }
};

En InnerFor, i es el contador de bucles externos (constante de tiempo de compilación), j es el contador de bucles internos (inicialmente 0 - también constante de tiempo de compilación), por lo que puede evaluar la fila como una plantilla de tiempo de compilación.

Es un poco más complicado, pero como dices, row (), col () y f () son tus partes complicadas de todos modos. Al menos probarlo y ver si el rendimiento vale la pena. Puede valer la pena investigar otras opciones para simplificar las funciones de la fila (), etc.

Answer 8

Un buen compilador debería hacer desenrollar por ti. Por ejemplo, en la compilación gcc con la opción -O2 se activa el desenrollado de bucle.

Si intenta hacerlo usted mismo manualmente, a menos que mida las cosas con cuidado y realmente sepa lo que está haciendo, es probable que termine con un código más lento. Por ejemplo, en su caso con el desenrollamiento manual, es probable que evite que el compilador pueda realizar un intercambio de bucles o una optimización de stripmine (busque --floop-interchange y -floop-strip-mine en los documentos de gcc )

Answer 9

Yo diría que es una falsa buena idea.

En C ++ esto: row<i,j>::value
significa que tendrá tantas funciones diferentes de row<>() como i * j. No desea esto porque aumentará el tamaño del código y hará un montón de errores de caché de instrucciones.

Observé esto cuando estaba haciendo funciones de plantilla para evitar una sola comprobación booleana.

Si es una función corta simplemente enlíneala.

Answer 10

f tendría que devolver un double , que no se puede hacer en tiempo de compilación.